[자료구조]Hash, Hashing, Hash Table

자료구조(Data-Structure)

• 처리하고자 하는 데이터의 효율적인 접근 및 조작을 가능하게 해주는 저장 및 관리방식입니다.

도서관의 책들이 잘 정리되어 있으면 우리는 우리가 원하는 책을 쉽게 찾을 수 있습니다. 하지만 뒤죽박죽 되어 있는 책들 중에 우리가 원하는 책을 찾으려면 시간이 꽤 오래 걸립니다.

자료구조도 이와 같습니다. 자료구조를 잘 선택하면 사용하는 메모리를 최소화할 수 있으며 시, 공간적으로 효율성을 확보할 수 있습니다. 

오늘은 Hash Table 자료구조에 대해 포스팅 하겠습니다.  

 

 

해시 테이블(Hash Table)

해시 테이블은 해시 함수를 이용해서 key를 고정된 크기의 값으로 변환한 후 해시 함수 결과 값을 인덱스에 key - value를 저장하는 방법입니다. 기본 연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있습니다. 

시간복잡도는 일반적인 경우(충돌이 없는 경우) O(1) 이고 최악의 경우(모든 경우에 충돌이 발생하는 경우) O(n) 입니다.

 

 

해시 테이블의 구조

• 키(key) : 고유한 값이며 해시함수의 input값입니다. 
• 해시 함수(Hash function) :  데이터의 효율적인 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 최대한 줄이는 함수를 만드는 것이 중요합니다.
  • 해시함수의 종류 : MD1, MD4, MD5, SHS, SHA-1, HAS-160 등이 있습니다.
• 해시(Hash) : 해시 함수(Hash Function)의 output값입니다. 저장소(bucket, slot)에서 값(value)과 매칭 되어 저장됩니다. 
• 값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능합니다.

 

충돌해결 - 해시 테이블의 구조 개선

Chaining

체이닝이란 충돌이 발생했을 때 이를 동일한 버킷(Bucket)에 저장하는데 이를 연결 리스트 형태로 저장하는 방법을 말합니다.

위 그림을 보면 John Smith 와 Sandra Dee 의 인덱스가 152 로 충돌이 일어났을때 Sandra Dee 를 John Smith 뒤에 연결함으로써 충돌을 처리하는 것을 말합니다.

 

Open Addressing

해시함수로 얻은 해시값에 따라서 데이터와 키값을 저장하지만 동일한 주소에 다른 데이터가 있을 경우 다른 주소도 이용할 수 있게 하는 기법입니다. Open Addressing을 사용할 경우 해시테이블은 1개의 해시와 1개의 값(value)가 매칭되어 있는 형태로 유지됩니다. 

위 그림을 보면 John Smith 와 Sandra Dee 의 인덱스가 152 로 충돌이 일어났을때 Sandra Dee 153에 저장함으로써 충돌을 해결합니다. 충돌이 일어났을 때 비어있는 해시를 찾는 과정은 다동일해야합니다. 비어 있는 해시를 찾는 규칙은 다음과 같습니다. 

 

• 선형 탐색(Linear Probing) : n개의 해시를 건너뛰어 비어있는 해시에 데이터를 저장합니다.
• 제곱 탐색(Quadratic Probing) : 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장합니다.
• 이중 해시(Double Hashing) : 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장합니다.