해시 테이블이란 검색하고자 하는 키 값을 입력받아서 해쉬 함수를 돌려서 반환받은 HashCode를 배열의 index로 환산해서 데이터에 접근하는 방식의 자료 구조이다.
F(key) -> HashCode -> Index -> Value
이때, 해시 함수는 어떠한 특정한 데이터를 이용해서 입력받은 키 값으로 그 값이 얼마나 큰지에 상관없이 동일한 해시 코드를 만들어준다.
그리고 해시 테이블의 가장 큰 장점은 검색 속도가 매우 빠르다는 점이다. O(1). 왜냐하면, 해시 코드의 값 자체가 배열의 인덱스로 활용되기 때문에 해시 코드로 배열의 위치에 다이렉트로 접근할 수 있기 때문이다.
그러나 해시 테이블도 고민이 있다. 바로 hash algorithm이 좋지 않을 경우, 한 배열의 인덱스에 여러 개의 값이 할당될 때이다. 즉, 서로 다른 키들을 넣었는데, 무한한 문자열에 비해 유한한 해쉬 코드로 인해 동일한 코드가 반환이 되거나, 서로 다른 해시 알고리즘이 서로 다른 해시 코드를 만들어냈는데, 배열 방이 한정되어 있어서 같은 방에 배정받을 수도 있다.
이 때, 문제가 바로 충돌이 일어난다는 것이다. 이렇게 충돌이 일어나면 검색 시간이 O(1)에서 최악의 경우 O(N)까지 걸릴 수도 있다.
그래서 이러한 충돌을 방지하기 위한 좋은 해시 알고리즘을 만드는 일이 중요한 것이다.
그럼 한번 해시 테이블을 구현해보자.
먼저 키를 입력받고, hash code를 반환하자. 이때, 각 문자를 아스키 코드 값으로 변환해서 해시코드를 만든다.
그리고 이를 배열방의 인덱스로 변환하는 함수로 구현해보자.
그리고 해시 테이블의 충돌을 고려하여, 체이닝 기법을 사용하여 같은 배열 방에 값이 여러 개 들어오는 경우에는 LinkedList로 이어준다.
