해쉬 테이블은 key와 value 쌍을 저장하는 자료구조로서 DB의 기초가 되는 매우 중요한 자료구조이다. 해쉬 테이블의 개략적인 구조는 아래 그림과 같다. (구글에서 찾은 그림)
보다시피 세로로는 버킷(bucket)이라는 공간들이 배열 형태로 존재하고, 이 bucket에는 링크드 리스트가 주렁 주렁 달려있다. 해쉬 테이블의 가장 큰 장점은 검색이 매우 빠르다는 것이다. 해쉬 테이블에 자료의 삽입 및 검색은 다음 그림을 보자. 간단한 전화번호부 자료구조이다. (위키피디아에서 찾은 그림)
예를 들어, "John Smith"라는 key로 "+1-555-1234"라는 전화 번호를 저장하고 싶다. 먼저 해쉬 테이블은 주어진 key 값을 해쉬 함수 (hash function)을 통해 특정한 값으로 변환을 한다. 위 그림에서는 873이 되겠다. 그러면 바로 배열에 접근하듯이 873번 버킷에 접근을 한다. 만약 해쉬 값이 1000이 넘는다면 % modulo 연산자로 나머지 값을 취해 이 데이터가 위치할 버킷의 인덱스를 찾는다. 이 버킷에 이제 데이터를 싱글 링크드 리스트 형태로 저장을 하면 된다. 왜냐면, 위의 그림과 같이 "Sandra Dee"라는 key의 해쉬 값도 873으로 "John Smith"와 충돌(collision)이 일어나게 된다. 따라서 이런 충돌을 피하기 위해 같은 해쉬 값을 가지는 데이터는 리스트로 저장을 한다.
검색과 삭제의 방법도 같다. 주어진 키의 해쉬 값을 계산 한 뒤, 원하는 버킷으로 찾아가서, 버킷에 달려있는 데이터 노드와 비교를 하여 (선형 탐색) 원하는 데이터를 찾는 것이다.
따라서 검색에 필요한 시간 중 버킷까지 찾아가는 시간은 해쉬 테이블의 크기가 얼마가 되었든 동일하다. 그러나 만약 해쉬 테이블에 너무 많은 데이터가 있어 충돌이 많이 일어난 경우, 즉, 버킷에 긴 리스트가 달려있는 경우에는, 탐색하는데 시간이 소요되게 된다.
이론적인 해쉬 테이블의 검색 속도는 O(1+n/m)으로 표현한다. 여기서 m은 slot의 개수, n은 원소의 개수로 n/m은 흔히 load factor로 표현이 된다. 그러나 리스트는 평균적으로 그렇게 길지 않으므로 흔히 탐색은 상수시간 O(1)이 걸린다고 말한다. (정말로 최악의 경우에 모든 키의 해쉬 값이 하나로만 나온다면 검색 속도는 리스트와 같아진다.)
추가 및 삭제도 모두 상수시간 O(1)이 걸린다. 그림과 같이 주어진 이름으로 전화번호를 찾아야하는 사전과 같은 구조에서는 해쉬 테이블이 가장 좋다.
그러나 하나 주의해야할 것은, 해쉬 테이블에 저장된 데이터는 순서를 예측할 수 없다. 그림에서 해쉬 테이블에 저장된 모든 데이터를 출력한다고 할 때, 이는 정렬되지 않은 값이다. 왜냐면 주어진 키의 해쉬 값에 따라 정렬이 되는데 이는 일반적으로 예측할 수 없기 때문이다. 따라서 위의 그림에서 사람 이름으로 정렬해서 출력하고 싶다면, 어쩔 수 없이 모든 데이터를 한번 정려를 해야한다.
Time complexity
- O(1): 현재 배열의 크기와 상관없이 언제나 같은 시간이 걸린다는 뜻이다. 배열 마지막에 새로운 원소를 넣는 작업의 경우, 배열의 크기를 알고 있기 때문에 for 순환 없이 바로 작업을 수행할 수 있다.
- O(n): 주어진 작업을 완료하기 위해서는 최악의 경우, 현재 배열의 길이만큼 탐색을 해야한다. 정렬되지 않은 배열에서 특정 원소를 찾는 것은 최악의 경우 모든 원소를 다 뒤져 봐야하므로 배열의 길이에 비례하는 시간이 걸린다.
- O(log n): 만약 배열의 원소들이 정렬이 되어있다면 이진탐색기법을 활용할 수 있다. 이 경우 연산 회수가 길이의 로그에 비례함을 알 수 있다. 왜냐면 한 번 수행할 때 마다 탐색해야할 데이터의 크기가 반으로 줄기 때문이다. 정확하게는 base가 2인 로그이지만 흔히 log로 표현한다. (밑이 10인 상용로그나 e인 자연로그는 아님을 주의)
오픈소스SW 라이선스 .pdf
