[자료구조] 해시 테이블

key-value 데이터를 어떻게 효율적으로 관리할 수 있을까?

Direct Access Table을 활용해 각 주소를 key로 활용하여 각각의 주소에 value값을 저장한다면, O(1)으로 저장하고 O(1)으로 불러올 수도 있다. 하지만 이는 데이터공간의 낭비가 일어날 수 있다. (key를 숫자로 생각하면 1, 3, 20000의 key가 있다고 생각했을때, 19997의 낭비공간이 발생)

그에 따라 제시된 것이 Hash Table이다. 이는 '해시함수'를 활용하여 값을 저장한다.

해시함수 : 특정값을 원하는 범위의 자연수로 변경해주는 함수. 원하는 범위를 정하면, 해시함수를 활용하여 적절한 위치에 key값과 value값을 모두 저장한다.

해시함수의 조건

1. 결정론적이어야 된다.
2. 원하는 범위의 자연수 하나하나가 리턴될 확률이 최대한 비슷해야 된다.
3. 빨리 계산을 할 수 있어야 된다.

해시함수를 만드는 방법의 예

1. 나누기 방법 : 테이블의 크기로 key를 나누고, 그나머지를 활용
2. 곱하기 방법 : 0<a<1 인 아무 값을 key를 곱한 다음, 그 결과값에 배열의 크기를 곱한다.

파이썬에서의 해시함수

파이썬에는 내부함수로 해시함수 hash() 가 있다. 이는 정수값을 제외한 다른 자료형의 데이터(소수, 문자열 등)을 일정 숫자로 대응시켜준다. 이 숫자는 특정 범위에 속해있지는 않지만, 매우 빠르며 일대일 대응이 된다. 따라서 정수형이 아닌 타입의 값을 특정 정수로 대응되도록 해준다.이는 불변타입의 값에만 사용이 가능하다. (불변타입 값의 예로는 불린형, 정수형, 소수형, 튜플, 문자열 등이 있다.)

Data Chaining

해시 함수를 통해 생성된 값이 겹친다면 이를 어떻게 해결하고 저장할까?

첫번째 해결책으로 chaining이 있다. 각 겹치는 인덱스에 값을 링크드리스트로서 저장하는 방법이다. (각 key와 value를 노드로서 연결하며 저장한다.) 이렇게 하면 겹치는 부분이 있어도 정상적으로 값들이 저장된다.

탐색또한 이를 활용하는데, 해시값이 겹친 것이 얼마나 있을지 모르므로, n개의 데이터를 해시테이블에 넣었을 때 최악의 경우는 O(n)만큼의 탐색시간이 필요하다. (선형탐색)

삽입은 겹치는 값이 있으면 기존값을 덮어씌우고(아예 key값 자체가 같은 경우), 아닐경우 해당 인덱스의 제일 마지막에 삽입되는 방식으로 작동한다. 삽입도 결국은 탐색을 하다가 최종적으로 값을 바꿔주거나 추가하는 작업이 필요한 것인데, 이는 어차피 O(1)이므로 탐색과 마찬가지로 O(n)만큼의 시간복잡도가 필요하다.

삭제의 경우도 탐색과 같은 과정은 거친 뒤 최종적으로 값을 지워주는 과정만 필요하므로 O(n)만큼의 시간복잡도가 필요하다.

다만 지금까지 살펴본 케이스들은 모든 데이터들의 해시 함수 결과값이 겹친다는 매우 극단적인 경우이다. 따라서 사실상 링크드 리스트의 길이의 평균(average_length)에 비례한다고 할 수 있다.이는 'key - value 쌍 수(데이터 수) / 해시 테이블에 사용하는 배열 인덱스 수' 로 구할 수 있다. 이를 각각 n, m으로 표현하면 시간복잡도는 O(n/m)이라고 할 수 있는 것이다. 그런데 이 때 '해시 테이블을 사용할 때는 만드는 배열의 길이를 데이터 수와 최대한 맞춘다.' 라는 규범을 적용하면 결국 시간복잡도는 O(1)이라고 할 수 있겠다.

다만 혼란을 줄이기 위해 정리하자면 '해시 테이블의 탐색,삽입,삭제는 평균적으로는 O(1), 최악의 경우에는 O(n)이 소요된다.' 라고 말할 수 있다.

Open Addressing.

충돌을 해결하기 위한 또다른 방법으로는 Open Addressing이 있다. 해시함수 결과값이 겹치는 주소 대신 그냥 다른 비어있는 주소에 넣어주는 방법이다.

비어있는 주소를 찾는 방법으로는 충돌이 일어난 주소부터 다음으로 1씩 인덱스를 더하며 비어있는지 확인하는 '선형탐사(Linear probing)', 제곱씩 인덱스를 더해주면서 확인하는 '제곱탐사(Quadratic Probing)' 가 있다.
(선형탐사 : +1 , +1, +1, ... / 제곱탐사 : +1, +4, +9, ...)

open addressing에서 탐색은 먼저 해시함수의 결과값에 따른 주소에서 탐사방법에 따라 이동하면서 일치하는 값을 찾아 존재여부확인한다. 중간에 빈 인덱스를 만나면 그것은 그만큼은 저장이 안되었다는 뜻이므로 탐색을 종료한다.

삭제도 비슷한 과정을 거치지만 주의해야 한다. open addressing을 통해 저장된 값이 여러개 있을때 그 사이의 중간값 하나가 그냥 사라지면, 탐색을 시도할 때 그만큼 저장이 안되었다고 인식하여 탐색을 종료할 수 있기 때문이다. 따라서 삭제된 위치에 "DELETED" 와 같은 표식을 남겨준다.

---

탐사는 최악의 경우 O(n)의 시간복잡도가 요구된다. (n만큼 겹쳐있을 수 있으므로) 따라서 탐사과정이 필요한 삽입, 탐색, 삭제 모두 O(n)의 시간복잡도가 가진다고 할 수 있겠다. (각각이 필요한 부가적과정은 O(1)의 시간복잡도를 갖는다. 따라서 무시된다.)

다만 마찬가지로 평균 시간복잡도를 생각해보면 조금 다르다.

'load factor'(= 해시테이블에 데이터가 차있는 정도 = 데이터양/테이블크기)를 a라고 두었을때, 1/1-a가 평균적으로 인덱스를 탐사하는 양이라고 생각할 수 있다. (예를 들어 100개 중 90개 차있으면 보통 10개정도 찾으면 하나는 빈 인덱스가 될 수 있으므로)

그런데 이때 해시테이블이 반정도 차있다고 가정하면, load factor a는 0.5가 되어 기댓값은 그냥 2보다 같거나 작아진다. 따라서 시간복잡도를 그냥 O(1)이라고 할 수도 있겠다.

결국 탐사가 O(1)의 시간복잡도를 가진다면, 그가 필요한 삽입,탐색,삭제 역시도 O(1)의 시간복잡도를 가진다고 할 수 있겠다.

즉, chaining을 사용하든 open addressing을 사용하든 해시 테이블의 삽입,탐색,삭제는 매우 효율적이다.