해시테이블 (hash table)

key를 value에 대응시키는 자료구조.

연결 리스트와 해시 코드 함수를 이용하면 간단하게 구현할 수 있음.

키와 값을 해시테이블에 넣는 과정

1. 키의 해시 코드 계산. (키는 보통 int, long. 키는 무한하나 int는 유한하기 때문에 서로 다른 키가 해시코드를 가리킬 수 있음)

2. hash(key)%array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구함(같은 인덱스를 가리킬 수도 있음)

3. 배열의 각 인덱스에 키와 값으로 이루어진 연결리스트가 존재. 키와 값을 해당 인덱스에 저장(충돌을 대비해 연결리스트 이용).

충돌이 많은 최악의 경우는 O(N) [N은 키의 갯수]

잘 구현된 경우엔 O(1)

-----

문자열(키)을 정숫값(해시 코드)로 치환해 문제를 해결하는 방법은 주로 진법을 많이 사용한다.

FAB라는 문자가 있으면 6*26^2 + 1*26^1 + 2*26^0 의 값이 해시 코드가 되는 셈.

물론 해시값이 너무 커지면 곤란하니 적당히 큰 수로 %연산을 거쳐 사용.

그러므로 충돌이 발생한다.

-----

충돌을 제어하는 방법은 위에서 말한 체이닝.

각 인덱스를 리스트로 구성하고, 데이터가 추가될 때마다 노드를 추가한다.

즉, 어떤 키가 해시 테이블에 존재하는지를 알고 싶다면 해당 키의 해시값에 해당하는 버킷이 가진 노드를 모두 순회한다.

한 쪽에 데이터가 편중되는 최악의 경우가 올 수 있으므로 해시 함수를 어떻게 구성하는가가 매우 중요한 핵심이 된다.

-----

c++에서는 STL에 unordered_set<자료형> 을 제공한다.

#include<unordered_set>시 사용 가능.

ex)

unordered_set<string> hash;
string key;
cin>>key;
 
hash.insert(key);
hash.count(key); // 있으면 1 출력. 없으면 0.
hash.erase(key);

-----

그냥 stl 안쓰는 코드도 해볼 것.

==================

(참조)

코딩 인터뷰 완전 분석

codeground note