[DS] 해쉬 테이블(Hash Table)이란?

해시테이블이 필요한 이유

일반적인 Key - Value 의 Map 자료구조에서

탐색의 소요시간은 모든 Key 를 순차적으로 순회하기 때문에 O(n) 이다.

• 2차원 배열로 첫번째 컬럼은 key 를 담고, value 를 담을 때 다음과 같이 만들 수 있다.

해시테이블은, Key 를 해싱해 인덱스로 삼기때문에, Key 자체가 인덱스가 되기때문에 랜덤액세스가 가능하다. 따라서 탐색의 시간복잡도가 O(1) 이다.

또한, key 자체가 인덱스가 되기 때문에 2차원 배열을 굳이 만들 필요없이 1차원 배열만 사용하므로 메모리 사용면으로도 효율적이다.

해시 맵의 단점은 다음과 같다.

• 해시 충돌: 같은 해시 값을 가진 서로 다른 키가 있을 경우, 해시 충돌이 발생합니다. 이를 해결하기 위해 체이닝(chaining)이나 오픈 어드레싱(open addressing)과 같은 기법이 사용되지만, 충돌이 빈번하게 발생하는 경우 해시맵의 성능이 저하될 수 있습니다.