해싱(hashing) / 해시 테이블(Hash Table)

 

해시 테이블은 키와 해시함수, 그리고 버킷이라는 데이터를 저장하는 장소로 이루어짐. 

• 키(key) - 고유한 값, 해싱함수의 인자값
• 해시 함수(hash function) - 키를 입력받은 후 키에 맞는 데이터가 저장 된 위치값을 반환(이 과정을 해싱이라고 함). 
• 버킷(bucket) - 해시 함수를 통해 생성된 해시 값을 고유 주소(키)로 사용하며 키에 맞는 값(value)의 한 쌍으로 저장하는 장소.

 

해시 테이블은 데이터가 키-값의 한 쌍으로 이루어져있기 때문에 삽입, 삭제, 검색 등의 과정에서 모두 O(n)의 시간복잡도를 가짐.

키값이 순차적으로 생성되는 것은 아니므로 순서나 관계가 있는 배열에서 사용하는 것은 적합하지 않으며 해시충돌이 일어날 수 있음.

 

 

해시 충돌(hash collision)

해시 충돌이란 다른 키값을 입력했으나 같은 해시값이 반환되는 경우를 말함. 

해결방법은 Chaining과 Open Addressing(개방 주소법)의 방법이 있음.

https://twpower.github.io/160-hash-table-implementation-in-cpp-en

 

 

+) 읽어보기

[자료구조]해싱, 해시 테이블 그리고 Java HashMap

 

[Algorithm](EN) Hash table implementation in C/C++