HashTable 기초

HashTable 자료구조는 insert, delete, find에 O(1) 시간 복잡도를 갖는다. Sort는 안된다.

 

Hash function은 어떠한 input 값을 정수 output으로 바꾸는 함수이다. 다른 input에 같은 output을 return 할 수 있으며 이런 상황을 hash 충돌이라고 한다.

예를 들어 Hash function -> 은 "Apple" -> 23438881, "Banana" ->759342, "aadf" -> 759342 처럼 input을 정수로 return하며 "Banana"와 "aadf"는 hash 충돌 상태이다.

 

Hash 충돌이 발생해도 HashTable 만드는데는 문제 없는데, 값을 array 공간에 각 index마다 linked list로 구성하면 되기 때문이다.

 

HashTable을 이용해 Two Sum 문제를 풀어보자

위처럼 값과 인덱스를 hash table에 저장하여 문제를 풀 수 있다.