[DS] Hashing

1. hash table

 

hash table은 hashing을 통해서 데이터를 저장하는 데이터 구조이다. hashing은 내부적으로 hash function 을 사용하여서 key와 value를 mapping 하여 hash table에 저장하여 데이터 구조를 형성하는 것을 의미한다. hash table에 데이터의 key와 value가 mapping 되어 저장되기 때문에 탐색에서 average case에 대해서 시간 복잡도가 O(1)이 된다. collision이 발생하는 경우에는 O(1)의 시간 복잡도를 보장할 수 없다. 그렇기 때문에 hash table에서의 성능은 hash function과 collision 발생 시의 정책에 따라 달라진다.

 

다음 예제는 hash table의 크기가 6이고 hash function이 'H(x) = x % 10' 인 경우의 hashing 구조이다. 리스트에 들어있는 11부터 15의 값들은 각각 hash function H(x)를 거쳐서 계산된 key 값을 인덱스로 hash table에 저장된다.

 

 

 

2. hash function

 

해시함수는 데이터를 hash table에 저장할 때 key에 대한 index를 구하는 함수, 알고리즘이다. 해시함수가 데이터의 key를 통해서 반환한 데이터의 고유 식별 값을 hashcode라고 한다. 하지만 때로 서로 다른 데이터가 같은 hashcode를 가지게 되는 경우가 있다.

 

위의 예시의 경우에는 각 값들이 겹치지 않고 hash table에 저장되었다. 만약에 리스트의 값 중에 21이 있었다면 어떻게 되었을까? 21의 경우 해시함수의 결과가 11과 같은 1이기 때문에 이미 값이 들어있는 칸의 인덱스를 키로 가지게 된다. 이처럼 서로 다른 데이터가 같은 key 값을 중복되게 가지게 되는 경우를 collision 이라고 한다. hash function 구현할 때는 이런 collision 을 어떻게 처리할 것인지에 대한 고민이 필요하다.

 

 

3. Collision 해결법

 

collision을 해결하는 궁극적인 방법은 1대1로 hash function 을 작성하는 것이다. 하지만 key에 따라 1대1로 해시함수를 작성하는 것은 불가능에 가까울 뿐 아니라 그렇게 되는 경우 해시 테이블의 크기가 너무 커지기 때문에 비효율적이다. 이를 해결하기 위한 방법중 대표적인 방법은 separate chainig과 open addressing 방법이 있다.

 

1) separate chaining

 

collision을 해결하는 대표적인 방법 중 하나로 해시 테이블의 각 cell을 linked list로 구현해서 중복되는 값들을 chain 처럼 이어서 저장하는 방법이다. 같은 hash code를 가지는 값들은 해당 cell에 linked list로 이어서 저장이 된다.

 

일반적으로 open addressing 방법보다 빠르고 간단하다. 또한 linked list로 연결되기 때문에 해시 테이블이 꽉차서 저장하지 못하는 경우는 발생하지 않는다. 또한 각각의 cell 이 linked list로 구현되어 있기 때문에 삽입과 삭제는 간단하다.

 

하지만 적은 데이터들을 저장하 때는 linked list를 구현하는 것 자체에 overhead가 발생할 수 있다. 또한 같은 인덱스에 중복이 많이 발생해서 linked list가 길어지는 경우 탐색의 시간이 O(N)을 넘어서는 worst case가 발생한다.

 

2) open addressing

 

collision이 발생하면 비어있는 다른 cell을 찾아서 저장하는 방법이다. 다른 cell을 찾는 방법으로는 다음과 같은 방법들이 있다.

• linear probing: collision 발생시 해시 테이블에서 순차적으로 cell들을 탐색해서 비어있는 곳을 찾는다.
• quadratic probing: 기본 해시함수에 2차 함수를 사용하여 비어있는 cell을 찾는다.
• double hashing probing: 보조 해시함수를 사용하여 새로운 hashcode를 찾는다.

open addressing 방법을 통해서 새로운 인덱스를 탐색할 수 있지만 결국 해시 테이블의 크기가 정해져 있기 때문에 worst case의 경우 다시 처음의 위치로 돌아오게 될 수 있다.

 

※ separate chaining vs open address

 

두 방식 모두 worst case의 경우에는 모든 데이터를 확인해야 하는 경우가 발생할 수 있다. 하지만 open address 방식은 한 해시 테이블의 연속된 공간에 데이터를 저장하기 때문에 separate chaining에 비해 캐시 효율이 좋다. 따라서 데이터의 개수가 적을 때는 open address 방식이 유리하다.

 

반면 open address 방식은 계속해서 배열의 칸을 사용하기 때문에 테이블의 확장, 크기가 빠르게 늘어난다. 그렇기 때문에 메모리 적인 부분에서는 separate chaining 방식이 유리하다.

 

 

[reference]

- https://www.geeksforgeeks.org/hashing-data-structure/