[알고리즘|자료구조] 해시란? | 해시법(hasing)

---

 

해시법(hasing)

 

데이터를 저장할 위치인 '인덱스'를 간단한 연산으로 구하는 것이다. 이렇게 구한 인덱스를 '해시값'이라고 한다. 마치 인덱스처럼 해시값을 통해서 데이터를 다룰 수 있게 된다. 

 

ㅡ 즉, 해시값은 데이터에 접근할 때 사용한다.

ㅡ 데이터 검색, 추가, 삭제 효율이 있다.

 

 

 

해시는 배열의 단점을 커버한다

 

배열에서는 (추가, 삭제로 인한)요소 이동에 필요한 복잡도(time-complexity)가 O(n)이다(꽤 무거움). 배열 요소를 추가, 삭제할 때마다 하나씩 앞으로(뒤로) 쭉 밀어서 자리를 만드는 것을 다들 알 것이다. 

 

해시에서는 (추가, 삭제로 인해)요소가 이동하더라도 다른 배열 요소들을 앞뒤로 옮기지 않아도 된다.

 

 

 

ㅡ 그럼 어떤 원리로 해시의 요소를 재정렬할 필요가 없는 것일까?

 

  다른 배열과 달리 인덱스가 '해시값'이기 때문이다. 앞에서부터 차례차례 인덱스번호 0,1,2, ...가 아니라, 저장된 키 값에 따라서 특정 해시값을 만들어내어 그것을 인덱스로 사용하는 것이다. 그럼 값을 추가, 삭제할 때도 해당 해시값을 통해 접근하게된다. 이로써 데이터를 삭제할 때는 그 해시값에 해당하는 키만 쏙 제거하면 그만이고, 데이터를 추가할 때는 그 해시값에 그 키 값을 해당시키면 된다. 배열 요소 순서에 맞춰 인덱스를 다시 쭉 부여할 필요가 없다는 것이다.

 

이렇게 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열이 바로 해시테이블(hash table)이다.

해시 테이블의 요소는 버킷(bucket)이라고 부른다.

 

 

---

연산을 통해 키 값에 따라 해시값을 만들어낸다고 했는데, 

서로 다른 키 값의 해시값이 중복으로 만들어지면 어떡하나? - "충돌"

 

  그렇다. 키값과 해시값의 대응관계가 1:1은 아니다. 서로 다른 키값이 같은 해시값을 가질 수도 있다. 이렇게 되면 '저장할 버킷이 중복되는 것'인데, 이 현상을 충돌(collision)이라고 한다. 

 

그래서 해시 함수가 중요하다. 가능하면 해시함수가 중복된 해시값을 최대한 만들지 않도록, 고르게 분포된 해시값을 만들어야 한다. 즉, 해시 테이블을 크게 만들면 충돌을 최소화할 수 있다.

 

  충돌이 발생하지 않는다는 것은 인덱스(해시값)과 키값이 1:1이라는 말이다. 즉, 시간 복잡도는 O(1)이다. 너무 좋지 않은가! 하지만 해시 테이블을 크게하면 메모리를 쓸데없이 많이 차지할 수 있다. 아쉽게도 시공간의 트레이드오프가 존재하는 것이다. 

 

 

 

---

 

충돌에 대한 대처

 

두 가지 대처방법이 있다.

 

1. 체인법 (오픈 해시법)

2. 오픈 주소법

 

 

 

   체인법 (chaining, open hasing)

 

같은 해시 값을 갖는 데이터를 연결리스트에서 체인모양으로 연결하는 방법이다. 

 

각 버킷에 저장되는 값은 해당 인덱스(해시값)에 저장된 '첫번째 노드'에 대한 참조이다.

개별 버킷은 Node<K,V>라는 클래스로 나타내어진다. 이때, K와 V는 각각 키값과 데이터의 자료형이다.

이 클래스에는 세 가지 필드가 존재한다. "key(키값), data(데이터), (next)(체인의 다음 노드에 대한 참조)"이다.

 

ㅡ 키값(key)과 데이터(data)는 독립적이므로, 데이터를 키로 설정할 수도 있고, 데이터가 아닌 것을 키로 설정할 수도 있다. 

ㅡ 필드 next에는 '체인에 있는 다음 노드에 대한 참조'가 대입된다. 즉, 또다른 Node(K,V) 말이다. 다음 노드가 없으면 null이다.

 

 

Node<K,V> 클래스에는 세 가지 메서드가 있다.

getKey, getValue : key, data를 그대로 반환한다.

hashCode : key의 해시 값을 반환한다. 

 

 

 

 

   오픈 주소법 (open addressing, closed hashing, linear probing)

  또 다른 해시법이다. 이 해시법에서는 충돌이 발생했을 때 재해시(rehashing)를 하여 비어 있는 버킷을 찾아낸다. 서로 다른 데이터가 같은 인덱스(해시값)를 가질 수 있는 체인법과는 달리, 해시값 하나에 데이터 하나만 연관된다. 그리하여 닫힌 해시법(closed hashig)이라고도 한다. 또한, 빈 버킷을 만날 때까지 재해시한다. 그리하여 선형 탐사법(linear probing)이라고도 한다.