자료구조 hash

해시 테이블(Hash Table)

해시 테이블은 연관배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조이다.

연관배열 구조(associative array)란,

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

연관배열 구조는 다음의 명령을 지원한다.

• 키(key)와 값(value)이 주어졌을 때, 연관 배열에 그 두 값(key & value)을 저장하는 명령
• 키(key)가 주어졌을 때, 연관되는 값(value)을 얻는 명령
• 키(key)와 새로운 값(value)이 주어졌을 때, 원래 키에 연관된 값(value)을 새로운 값(value)으로 교체하는 명령
• 키(key)가 주어졌을 때, 그 키(key)에 연관된 값(value)을 제거하는 명령

위의 명령은 해시테이블에서도 동일하게 적용이 된다.

 

해시 테이블의 구조(Hash Table Data Structure)

 

 

해시 테이블은 키(Key), 해시함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어져 있다.

키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭되어 저장소에 저장이 된다.

• 키(key) : 고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다. 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.
• 해시함수(Hash Function) : 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
• 해시(Hash) : 해시 함수(Hash Function)의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭되어 저장된다.
• 값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

 

 

Search(검색)

키(key)로 값(value)를 찾아내는 과정은 Deletion 과정과 비슷한다. 1) 키로 hash를 구한다. 2) hash로 값(value)를 찾는다.

Search Big-O

저장 단계의 시간복잡도는 O(1)이다. 키(key)는 고유하며 해시함수(hash function)의 결과로 나온 해시(hash)에 매칭되는 값(value)를 찾으면 되기 때문이다. 이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
하지만, 최악의 경우 O(n)이 될 수 있다. 해시 충돌로 인해 모든 bucket의 value들을 찾아봐야 하는 경우도 있기 때문이다. 이에 관해서도 해시충돌과 함께 후술하겠다.

Hash Collision(해시 충돌)

해시테이블은 Insertion, Deletion, Search 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있기 때문에 자료구조의 효율성 측면에서 매우 우수하다고 볼 수 있다. 하지만 이런 장점만 있는 것일까?

해시(hash)를 이용한 자료구조 방식에 필연적으로 나타날있는 문제들이 있고 해결방법을 제시한다

 

. 열린 어드레싱 방법 (Open Addressing Method)

 

선형 조사법(Linear Probing)

: 충돌이 발생했을때 그 옆자리가 비어있는지 살펴보고, 비어있을 경우 그 자리에 대신 저장하는 방식

 

[이미지 출처 : http://faculty.cs.niu.edu/]

 

쉽게 옆자리가 비어있으면, 그 옆자리로..

그 옆자리가 이미 있으면 그 옆자리로..계속 식으로 이동하게 되는 것 입니다.

계산이 단순하다는 장점이 있지만, 검색에 시간이 많이 소요되고, 테이블 내에 데이터들이 일정한 키 값으로 모이는 현상이 발생합니다.

 

이차 조사법 (Quadratic Probing)

: 선형 조사법이 n칸 옆을 검사한다면, 이자 조사법은  

 칸 옆을 검사하는 것입니다.

 

 

[이미지 출처 : http://faculty.cs.niu.edu/]

 

 

이렇게 된다면, 일정한 키 값으로 모이는 현상은 방지하겠지만, 모든 공간을 다 검사하지는 않게 되겠지요.

 

이중 해시(Double Hash)

: 처음에는 하나의 해시 함수를 사용하다가 충돌이 발생하면, 두번째 해시 함수를 사용하여 해시 값을 가지는 것 입니다.

 

 

[이미지 출처 : http://faculty.cs.niu.edu/]

 

재해싱(Rehasing)

: 해시 테이블의 크기를 늘리고 새로운 해시 테이블의 크기에 맞추어 다시 모든 데이터를 해싱하는 방법입니다.

다시 배치가 되는것은 좋지만 상당히 많은 비용이 발생하겠지요..

 

2. 닫힌 어드레싱 방법 (Closed Addressing Method)

 

체이닝

: 해시 테이블 자체는 포인터 배열로 만들고, 같은 버켓의 해당하는 데이터들을 체인형식으로 만들어(링크드 리스트) 연결하는 방식입니다.

이 경우 삽입 삭제가 용이 하지만 따로 동적인 공간을 할당 해야 하는 문제가 발생합니다.