[자료구조] 해시(Hash), 해시테이블(Hash table),해싱(hashing) 이란?

개념

해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)이라고 한다.

해시 테이블은 다음과 같은 총 5개[키(key), 해시함수(hash function), 해시(hash), 값(value), 저장소(bucket,slot)]로 이루어진다.

 

• 키(key) : 고유한 값이며, 해시 함수의 input이 된다. 

• 해시함수(Hash function) : 키(key)를 해시(hash)로 바꿔주는 역할을 한다.

• 해시(hash) : 해시 함수(hash function)의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭되서 저장된다.

• 값(value) : 저장소(bucket,slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

# 해시함수는 해시값의 개수보다 많은 키값을 해시값으로 변환하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 것은 해시충돌이라고 말한다. 다음 사진은 John Smith와 Sandra Dee가 02라는 동일한 해시값을 볼 수 있는 해시충돌의 사진이다.

 

출처 : 위키피디아

해시테이블

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)를 키와 함꼐 저장하는 자료구조를 해시테이블(hash table)이라고 한다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다. 해시 테이블의 기본 연산은 삽입, 삭제, 탐색(search)이다. 

출처 : 위키피디아

 

해시테이블 장점

적은 리소스로 많은 데이터를 효율적으로 관리하기 위함이다. 예로써 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(key)들을 유한한 개수의 해쉬값(value)로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있다. 해시는 데이터 엑세스(삽입, 삭제, 탐색)시 계산복잡성을 O(1)로 지향한다.

 

다른 자료구조와 비교하게 되면 이진탐색트리와 그것에 대한 변형의 경우에는 메모리를 효율적으로 사용할 수 있지만,

데이터 탐색에 소요되는 계산복잡성이 O(log n)이다. 또한 배열(Array)의 경우에는 계산 복잡성은 O(1)이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말할 수 없다.

 

또한 인풋 데이터가 다양하지만 아웃풋의 데이터를 동일한 길이로 만들 수 있어 '데이터 축약'의 기능도 수행할 수 있다.

 

기본 연산

1. insertion(저장)

   • 해시 함수(Hash Function)으로 키(key)를 해시(hash)로 변경해야한다. 

   • 저장 단계의 시간 복잡도는 O(1)이다.

   • 키는 고유하며 해시함수의 결과로 나온 해시와 값을 저장소에 넣는다.

   • 최악의 경우 시간 복잡도가 O(n)가 될 수 있다. 그이유는 해시 충돌로 인해 모든 bucket이 value들을 찾아봐야하는 경우도 있기 때문이다.

2. Deletion(삭제)

   • 저장되어 있는 값을 삭제할 때 저장소에서 해당 key와 매칭되는 value를 찾아서 삭제한다.

   • 시간복잡도 O(1)

   • key는 고유하며 해시함수의 결과로 나온 해시에 매칭되는 value를 삭제하면 된다.

   • 최악의 경우 위와 동일하다.

3. Search(검색)

   • key로 value를 찾아내는 과정은 Deletion과정과 비슷하다.

   • key로 hash 구하기->hash로 value 찾기

   • 시간복잡도는 O(1)

   • 최악의 경우 위와 동일하다.

앞서 계속 말한 해쉬충돌(hash collision)은 어떤 식으로 해결하는 지 계속 알아보겠다.

Chaining

• 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것

• 해당 버킷에 데이터가 이미 있으면 체인처럼 노드를 추가하여 다음 노드를 가르키는 방식으로 구현(연결리스트)

• 유연하지만 메모리 문제를 야기

출처 : 위키피디아

Open addressing

• chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블

• 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용하는 것

• 메모리 문제가 발생하지 않으나 해시충돌이 생길 수 있다.

출처 :  https://ratsgo.github.io/

출처 

• https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o
• https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
• https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98