Hash

jaehun_dev·2022년 10월 21일

목록 보기

4/5

Hash

Hash는 key-value 쌍으로 데이터를 저장하는 자료구조다. key값이 해싱 알고리즘으로 배열의 index로 변환되어 접근된다. 따라서 collision이 없을 경우 O(1)의 접근 속도를 가진다.
해싱 알고리즘으로 생성된 key에 대한 index는 고유하기 때문에, 다른 데이터에 의해 채워지거나 다른 데이터를 shift할 필요가 없기 때문에 추가적인 비용 없이 O(1)로 작업 가능하다.

Hash 함수

key를 배열의 index로 변환해주는 함수이다. Hash 함수로 인하여 반환되는 데이터의 고유 숫자 값들을 'Hash Code'라 한다. 그러나 해시코드로 나올 수 있는 숫자의 범위가 매우 크며, 이를 전부 배열로 할당하기에는 한계가 있다. 따라서 해시 코드를 적절한 범위 내로 변환하는 것이 중요하다.
일반적으로 해시 함수는 키의 일부분이 아닌 전체를 참조하여 해시 코드를 만드는 것이 좋다. 또한 충돌을 어떻게 최소화하고, 어떻게 처리할 것인가가 중요하다. key-hash code를 1대1로 대응하도록 하는 것은 거의 불가능하며, 그렇게 하더라도 메모리를 너무 차지하여 일반적인 배열과 차이가 없어진다.

Hash 함수의 예시

h(k) = k mod m. m이 소수인 경우 좋은 방법
h(k) = floor(m*(kA - floor(kA))). (0<A<1). 느리지만 m의 값에 큰 영향을 받지 않는다.
Universal Hashing: 같은 버킷에 key값이 몰리는 것을 방지하기 위해 매번 다른 해시 함수를 사용하는 것

충돌(Collision)

적절한 범위 내로 해시 코드를 설정한다면, 서로 다른 key가 같은 해시코드로 변환되는 경우가 발생할 수 있는데, 이를 충돌(Collision)이라 한다. 충돌이 많아지면 추가적인 탐색이 필요해지기 때문에 탐색의 시간복잡도가 O(n)에 가까워진다. 따라서 충돌을 방지하고 잘 처리하는 것이 Hash 함수에게 중요하다. 이러한 충돌을 해결하기 위한 여러 방법이 있다.

해시 버킷?

버킷이란 데이터를 저장하는 공간이다.

Open Address (개방 주소법)

충돌이 발생하면 데이터를 저장할 다른 버킷을 탐색한다. 최악의 경우 전체 버킷을 탐색했음에도 데이터를 저장할 빈 버킷을 찾지 못할 수 있다.
삭제가 어렵다는 단점이 있다. 삭제를 할 경우 충돌로 인해 뒤에 저장된 데이터의 검색이 되지 않을 수 있기 때문에, 삭제된 자리에 Dummy Node의 삽입을 해야한다. (삭제되어 값이 없을 경우 탐색을 종료하기 때문에)
개방 주소법을 수행하는 방법의 예시는 다음과 같다.
1️⃣ Linear Probing: 순차 탐색으로 빈 버킷을 찾는다.
문제점: primary clustering. 충돌 시 뒤의 버킷에 데이터를 넣는 형식으로 수행하다보면, 데이터들이 특정 위치에만 밀집할 수 있다. 이로 인해 충돌이 계속 발생되고 탐색 시간이 매우 늘어날 수 있다.

2️⃣ Quadratic Probing: 고정 폭으로 이동하는 선형 탐사와 달리 탐색의 폭이 제곱수로 늘어난다. 예를 들어, 12 -> 22 -> 32 크기로 이동하며 빈 버킷을 탐색한다.
문제점: secondary clustering. 처음 해시값이 똑같아 충돌이 날 경우 이후로도 계속 똑같이 probe하여 충돌이 발생한다.

3️⃣ Double Hashing Probing: 2개의 해시함수를 적용한 결과를 이용한다. 1차 해시함수 적용 후 충돌 시 2차 해시함수를 이용한다. 예를 들어, 해시함수 h와 d가 있다.
h(key) = key%13
d(key) = 7-(key%7)
hash_code = (h(key) + jxd(key))%13
이 때, j는 몇 번째 반복인지를 뜻한다. h를 이용하여 해시코드 도출 후, 실패하면 d를 추가로 적용한 hash_code를 도출한다. 실패 시 j를 1씩 증가시키며 새로운 hash_code를 계산한다.
문제점: 위 두 가지 방법들에 비해 연산량이 많다.

Separate Chaining (분리 체인법)

각 버킷에 데이터를 직접 넣는 것이 아닌, 데이터들을 저장하는 리스트나 트리 등의 포인터를 저장하는 방식. Java7의 HashMap에 해당 방식을 사용된다. 연결리스트 또는 트리를 통해 구현 가능하다.
키의 삭제 시, 연결리스트 또는 트리에서 노드의 제거만 하면 된다.
보조해시함수: Key의 해시 값을 변경하여 해시 충돌 가능성을 줄인다.

Linked List: 버킷들을 데이터 하나가 아닌, 연결리스트로 만든다. 충돌이 발생하더라도 Linked List에 노드를 추가하여 값을 계속하여 추가하기 때문에, 데이터 삽입을 위한 다른 버킷을 탐색할 필요가 없다. 데이터를 탐색할 때에는, 해당 key에 대한 index의 버킷이 가진 리스트를 선형 탐색하여야 한다.
Red-Black Tree: Linked List 대신 트리를 사용한다. 하나의 버킷에 할당되는 데이터가 적을 시 연결 리스트를 사용하는 것이 좋다. (최악의 경우에 대해 성능 차이가 거의 없지만 메모리 측면에서 연결 리스트가 좋다.) 그러나 하나의 버킷에 많은 데이터가 저장될 시 BST를 활용하여 탐색 시간을 줄일 수 있다. 트리를 사용할 경우 평균, 최악에서의 시간복잡도가 O(log N)이다.

자바의 경우 연결리스트/레드블랙트리 선택의 기준이 버킷의 노드, 즉 데이터의 개수다. 데이터가 6개 이하라면 연결리스트, 8개 이상이라면 트리를 사용한다.

7개가 기준에 없는 이유?
예를 들어 노드가 6개에서 7개가 됐을 때 바로 트리로 전환한다고 하면, 노드가 사라져 6개가 됐을 때 연결리스트로 다시 전환해야 한다. 이렇게 되면 노드의 추가/삭제에 따라 너무 잦은 switching 비용이 발생하기 때문에, 6->7개로 증가할 때, 또는 8->7개로 감소할 때에는 그 형태를 변환하지 않고 일종의 여유를 남겨둔다.

Resizing

개방주소법의 경우, 고정 크기 배열을 사용하기 때문에, 해당 크기를 초과하여 데이터를 넣기 위해서는 배열의 확장이 요구된다. 분리 체인법의 경우에도 리스트의 크기가 너무 커진다면 선형 탐색 시간이 길어지기 때문에 버킷 개수의 확장이 요구된다. 이를 Resizing이라 한다.