해쉬 테이블(Hash Table)

참고 : https://youtu.be/6Z6L4TgjPk8

해쉬 알고리즘 & 충돌

O(1)(최대 : O(n))

1. Different Keys → Same Code

해쉬 알고리즘은 때론 서로 다른 key 값들로 동일한 해쉬 코드를 만들 때가 있다.

key 값은 문자열이고, 가지수는 무한하지만 해쉬 코드는 유한하다.

즉, 중복될 수 밖에 없다.

2. Different Code → Same Index

또한, 다른 해쉬 코드를 얻었지만 '배열 방'은 한정되어 있으므로, 

같은 방에 배정될 수 있다.

→ 위의 2가지 다 Collision 발생.

아래의 코드는 한 가지 예시일 뿐 이고,

좋지 못 한 해쉬 알고리즘이다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<vector<string> > v;
 
int getHashCode(string key)
{
    int HashCode = 0;
    for (auto i : key) HashCode += i;
    return HashCode;
}
 
int ConvertToIndex(int HashCode) { return HashCode % v.size(); }
 
int main(void)
{
    v.resize(3);
 
    vector<string> name = { "sung", "jin", "hee", "min" };
 
    for (auto i : name)
        v[ConvertToIndex(getHashCode(i))].push_back(i);
 
    for (int i = 0; i < v.size(); i++)
    {
        printf("%d번 방 : ", i);
        for (auto n : v[i])
            cout << n << " ";
        printf("\n");
    }
 
    return 0;
}