[알고리즘] 해시 테이블 (Hash Table)

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

해시 테이블

 

 

C# dictionary = C++ map (X)          
C# dictionary = C++ unordered_map

 

MAP 

• 균형 이진 트리로 만들어져 있어서 트리 구조로 관리한다. ex. Red-Black Tree
• 추가/탐색/삭제  O(logN)
• 시간복잡도는 O(logN)이다. Hash Map 보다 느리다.

 

HASH MAP (Unordered Map)

• 메모리를 내주고 속도를 취하는 방식이다. 살은 내주고 뼈를 취한다!
• 빠르게 데이터를 찾을 수 있다.
• 충돌이 일어나지 않는다고 가정하면 Hash Map이 Map보다 훨씬 빠르다.
• 추가/탐색/삭제 0(1)
• 시간복잡도는 O(logN)
• 아파트 우편함
  [201][202][203][204][205]
  [101][102][103][104][105]
  
  1 ~ 999 user (userId = 1 ~999)
  [1][2][3][][][][][999]

 

map vs hash map(C++11 표준 unordered_map) 차이 알기!

---

테이블 방식의 구현

 

장점

• 키를 알면, 데이터를 단번에 찾을 수 있다.

단점

• int32_max (3억~)
• 살을 내주는 것도 정도껏 내줘야지.. 이건 메모리 부하가 너무 심하다
• 메모리도 무한은 아니다.

void TestTable() {     struct User     {         int userId = 0; // 1~999         string username;     };       vector<User> users;     users.resize(1000);       // 777번 유저 정보 세팅     users[777] = User{ 777, "Rookiss" };       // 777번 유저 이름은?     string name = users[777].username;     cout << name << endl; } Colored by Color Scripter

cs

 

---

 

해시 테이블 방식의 구현

 

보안에 이용되는 경우가 대표적이다.

아이디와 패스워드를 서버에 저장할 때 패스워드는 해시 방식으로 전환해서 DB에 저장한다.
ID: rookiss + PW: qwer1234
ID: rookiss + PW: hash(qwer1234) -> sdaf123!@asdfasdf1234

DB [rookiss][sdaf123!@asdfasdf1234]

비밀번호 찾기 -> 아이디 입력 / 폰 인증 -> 새 비밀번호를 입력하세요

비밀번호가 기억나지 않아 찾을시에 비밀번호를 알려주는 대신 새 비밀번호를 설정하는 이유는 DB에 해시로 전환된 패스워드만 있고 진짜 패스워드는 없기 때문이다.

 

충돌 문제 발생 시 충돌이 발생한 자리를 대신해서 다른 빈자리를 찾아나서면 된다. 

 

선형 조사법(Linear Probing)

hash(key) + 1 -> hash(key) + 2

 

이차 조사법 (Quadratic Probing)

hash(key) + 1^2 -> hash(key) + 2^2

 

 

void TestHash()
{
    struct User
    {
        int userId = 0; // 1~int32_max
        string username;
    };
 
    vector<User> users;
    users.resize(1000);
 
    const int userId = 123456789;
    int key = (userId % 1000);   // hash < 고유번호
 
    // 123456789번 유저 정보 세팅
    users[key] = User{ userId, "Rookiss" };
 
    // 123456789번 유저 이름은?
    User& user = users[key];
    if (user.userId == userId)
    {
        string name = user.username;
        cout << name << endl;
    }
}

---

 

해시 테이블 체이닝 방식의 구현

 

void TestHashTableChaining()
{
    struct User
    {
        int userId = 0; // 1~int32_max
        string username;
    };
 
    vector<vector<User>> users;
    users.resize(1000);
 
    const int userId = 123456789;
    int key = (userId % 1000);   // hash < 고유번호
 
    // 123456789번 유저 정보 세팅
    users[key].push_back(User{ userId, "Rookiss" });
    users[789].push_back(User{ 789, "Fake ID" });
 
    // 123456789번 유저 이름은?
    vector<User>& bucket = users[key];
    for (User& user : bucket)
    {
        if (user.userId == userId)
        {
            string name = user.username;
            cout << name << endl;
        }
    }
}

 

 

 

 

---

 

전체코드

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
 
void TestTable()
{
    struct User
    {
        int userId = 0; // 1~999
        string username;
    };
 
    vector<User> users;
    users.resize(1000);
 
    // 777번 유저 정보 세팅
    users[777] = User{ 777, "Rookiss" };
 
    // 777번 유저 이름은?
    string name = users[777].username;
    cout << name << endl;
}
 
void TestHash()
{
    struct User
    {
        int userId = 0; // 1~int32_max
        string username;
    };
 
    vector<User> users;
    users.resize(1000);
 
    const int userId = 123456789;
    int key = (userId % 1000);   // hash < 고유번호
 
    // 123456789번 유저 정보 세팅
    users[key] = User{ userId, "Rookiss" };
 
    // 123456789번 유저 이름은?
    User& user = users[key];
    if (user.userId == userId)
    {
        string name = user.username;
        cout << name << endl;
    }
}
 
void TestHashTableChaining()
{
    struct User
    {
        int userId = 0; // 1~int32_max
        string username;
    };
 
    vector<vector<User>> users;
    users.resize(1000);
 
    const int userId = 123456789;
    int key = (userId % 1000);   // hash < 고유번호
 
    // 123456789번 유저 정보 세팅
    users[key].push_back(User{ userId, "Rookiss" });
    users[789].push_back(User{ 789, "Fake ID" });
 
    // 123456789번 유저 이름은?
    vector<User>& bucket = users[key];
    for (User& user : bucket)
    {
        if (user.userId == userId)
        {
            string name = user.username;
            cout << name << endl;
        }
    }
}
 
int main()
{
    TestTable();
    TestHash();
    TestHashTableChaining();
}