1일 1커밋 !

Hash Table

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조입니다. image

  • Value : 저장하고자 하는 정보. 최종적으로 저장소(bucket, slot)에 hash와 매칭되어 저장됩니다.
  • key : 고유한 값. Hash function의 input입니다. Key값 그대로 최종 저장소에 저장되면 ,다양한 길이의 저장소를 미리 구성해 두어야 하기 떄문에 hash function으로 값을 바꿔 저장합니다.
  • Hash function : key를 자료를 저장할 위치를 나타내는 고정된 길이의 hash로 변경합니다. 이때 서로다른 key가 같은 hash가 되는 경우가 있습니다. 이를 Hash Collison 이라 불리며, Hash Collision 발생확률을 최대한 줄이는 Hash function을 만들어야 합니다. Hash Collision을 해결하는 방법에는 chaining 기법 과 open address hash 방식이 있습니다.

Hash Table의 삽입, 삭제, 검색

일반적으로 해시태이블의 삽입, 삭제, 검색의 시간복잡도는 O(1)입니다. Key는 고유하며, Hash Function의 결과로 나온 hash와 value를 저장소에 삽입/삭제/검색 하면 되기 때문입니다.

하지만, 이는 Hash Collision을 고려하지 않았을떄의 결과입니다. 최악의 경우는 O(n)으로 Hash Collision이 발생하여 모든 bucket의 value를 찾아 봐야하는 경우가 해당합니다.

Hash Collision

입력 값이 달라도 해시 값은 같을 수 있기 때문에 충돌의 가능성은 늘 존재합니다. 충돌 문제를 해결하기 위해 다음과 같은 방법을 주로 사용합니다.

Open addressing

충돌이 발생할 경우, 해시 테이블의 다른 자리에 대신 저장하는 방법입니다. 따라서 Open addressing 방식에서는 하나의 해시에 하나의 값이 매칭됩니다. Open Addressing는 위에서 언급한 비어있는 해시를 찾는 규칙에 따라 다음과 같이 구분할 수 있습니다. 선형 탐색(Linear Probing): 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장 제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장 이중 해시(Double Hashing): 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장

Chaining

Linked list를 이용해서 충돌을 해결하는 방법입니다. (주로 사용할 방법) 자료 저장시, 저장소(bucket)에서 충돌이 일어나면 해당 값을 기존 값과 연결시키는 기법입니다. image 위 이미지의 경우, hello를 저장할 때 충돌이 일어나 기존의 samsung에 연결시켰습니다. 이때 Linked List 자료구조를 이용해 다음에 저장할 자료를 기존 자료 다음에 위치시킵니다.

  • 장점
    • 한정된 저장소(Bucket)를 효율적으로 사용할 수 있습니다.
    • 상대적으로 적은 메모리를 사용합니다
  • 단점
    • 한 Hash에 자료들이 계속 연결될 수 있으며, 이때 검색 효율이 떨어집니다.

적절한 Hash Table size

보통 소수나 2의 거듭제곱(2^m)을 사용합니다.

테이블의 크기로 소수를 사용 할 경우, 충돌이 적지만 느린 % 연산자를 사용해야 합니다. 해시 함수가 아주 고르게 분포하는(무작위에 가까운) 값들을 출력해준다면 테이블의 크기가 소수인지는 별로 중요하지 않습니다. 하지만 출력 값이 고르지 않다면 어떨까요? 예를 들어 해시 값이 15, 30, 45, 60, 75, 90, …처럼 15의 배수가 굉장히 많이 나오는 상황에서 해시 테이블의 크기가 30이라면 0번 버킷과 15번 버킷에만 많은 데이터가 저장됩니다. 테이블의 크기가 s이고 해시 함수가 x의 배수만 출력한다면, 실질적인 테이블의 크기는 s / gcd(s, x)과 같습니다. 따라서 이런 편향된 해시 값이 많은 경우에 효율적인 테이블의 크기는 자신을 제외한 모든 수와 서로소인 소수입니다.

C++의 Unordered Associative Containers는 소수를 사용합니다.

연관배열 구조(associative array) : 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.

반면에 2의 거듭제곱을 활용 할 경우, bit masking을 통해 나머지를 빠르게 계산을 할 수 있지만 m개의 하위 bit를 그대로 사용하기 때문에 hash function이 하위 bit을 고르게 분포 시키지 못한다면 많은 충돌이 발생하게 됩니다.

Java에선 hashMap의 size를 2의 거듭제곱을 사용하고 있습니다.

다만, 소수나 2의 거듭제곱이나 당락에 영향을 줄 만큼 큰 영향은 없습니다.

업데이트:

댓글남기기

참고