Hash Collision 발생시 Open Addressing 방법은 Separate Chaining 방식에 비해 어떤 장점을 가질까?

해시를 공부하다 보면 해시 충돌(Hash Collision)에 대해 공부할 수 밖에 없다.

 

물론 해시 함수를 만들 때 input과 output이 항상 1:1로 고정할 수 있으면 좋겠지만, output을 저장할 곳에 대한 물리적인 조건을 고려할 수밖에 없기 때문이다.

 

예를 들어, input이 들어올 수 있는 경우의 수는 100만가지인데, 정작 저장할 원소의 수는 10개라고 하자. 그러면 해시 충돌을 막기 위해 (input과 output을 1:1로 고정하기 위해) 배열의 크기로 100만으로 잡으면 이건 엄청난 낭비이다.

 

따라서 보편적으로 해시를 만들 때, 해시 함수를 적용한 output에 저장하는 테이블의 크기(m, 버켓의 크기)으로 나머지 연산을 수행해서 저장하도록 만든다.

- output = hash(input) % m

 

Java에서 테이블을 처음에 작게 잡고, put 과정에서 resize하는 것도 위와 같은 메모리적인 이유라고 생각한다.

Java HashMap에서 테이블 역할을 수행하는 table 필드

 

그런데 n이 작으면 해시 충돌 발생 가능성은 높아질 수밖에 없다. 그 과정에서 대표적인 해시 충돌 알고리즘에 대해 공부하게 되었고, 대표적인 알고리즘 2가지 중 어떤 것이 더 좋은지 조사를 해보았다.

 

1. Separate Chaining : Java에서 채택한 방식이다. 충돌 발생시 entry를 만들고 list 혹은 tree로 관리한다. Java의 경우 충돌 횟수가 적으면 linked list(탐색 속도 : O(N))로 관리하다가 충돌 횟수가 많아지면 red-black tree(탐색 속도 : O(logN))로 변환시킨다.

출처 : https://en.wikipedia.org/wiki/Hash_table

 

위에서 table의 타입이 T[]가 아니라, Node[]인 이유도 next에 대한 pointer를 가져야 할 수도 있기 때문인 것 같다.

 

2. Open Addressing : Python에서 채택한 방식이다. 충돌 발생시 다음 칸(Linear Probing)으로 밀어넣는다. 따라서 탐색할 때 output이 null이 아니라면 이어진 모든 값들을 검색해야 값을 찾을 수 있을 수도 있다. (O(M). M은 충돌한 원소들의 cluster 크기)

출처 : https://en.wikipedia.org/wiki/Hash_table

 

Open Addressing의 경우 delete 연산이 수행되었을 때 유의해야 한다. 충돌 cluster는 모여있는 걸 기준으로 만들어 지는데, 중간이 비면 다른 cluster라고 인식된다. 따라서 cluster의 마지막 원소를 빈 공간으로 이동시켜야 한다.

 

만약 multi thread 환경이라면 이런 과정에서 lock 경합이 길어질 수 있을 것 같다는 생각이 들어 Separate Chaining 방식이 좋다고 생각했다. 구현도 간편하고, 충돌이 많이 발생하더라도 다른 칸을 차지하지 않기 때문에 전체 테이블에 영향을 적게 준다고 생각했기 때문이다.

 

그런데, Python에서 이 방식을 채택한 데에는 어떠한 이유가 있을 것이라 생각해 궁금증이 들어 이유들을 조사해 보았다.

 

1. CPU cache hit

 

출처 : https://en.wikipedia.org/wiki/Hash_table

 

기본적으로 Open Addressing 방식은 한 배열 안에 원소들이 들어 있다. 이 말은 메모리 상에 인접하게 원소들이 위치하고 있다는 의미이다. 따라서 CPU에서 작업하기 위해 메모리에서 레지스터로 데이터를 퍼갈 때 캐시를 더 잘 활용할 수 있다.

 

이에 반해 Separate Chaining 방식은 참조를 사용한다. 따라서 데이터들에 대해서 접근하려면 random access가 필요하다는 말이고, 캐시 미스율이 더 높다.

 

재밌는 점은 load factor가 커지면 chaining 방식에서 캐시 미스가 더 적다는 점이다. 여기서 load factor란 버킷 수(m, 테이블의 전체 크기)를 버킷에 들어있는 원소 수(n)로 나눈 값이다. load factor = n / m

 

따라서 위에서 생각했던 충돌이 많이 발생했을 때 chaining 방식이 효율이 더 좋다는 건 사실일지도 모르겠다.

 

2. resize

 

Separate Chaining은 resize할 때 충돌된 Node들에 대해 전부 재배치해야 하는데 이 과정이 좀 복잡하다.

 

Java HashMap의 resize() 중 일부

 

next가 있으면 모두 조회해서 전부 재배치하고 있다. Python의 경우 어떻게 되어 있는지 보려고 했으나...

 

 

빌트인이 전부 JNI처럼 다른 언어로 작성되어 있는 것 같다... 그래서 어떻게 되어있는지 볼 수 없어 아쉽다.

 

+) 생각해 보니, Open Addressing도 resize()했을 때 해시 적용 후 output이 달라지기 때문에 collision 발생한 것들을 재배치하는 건 똑같은 것 같다. 그러나, 이런 생각도 했던 걸 남겨놓기 위해 내용은 그대로 남긴다.

 

참조

- chained-hash-tables-vs-open-addressed-hash-tables : https://stackoverflow.com/questions/2556142/chained-hash-tables-vs-open-addressed-hash-tables

- Hash table - Wikipedia https://en.wikipedia.org/wiki/Hash_table