[자료구조] Hash(해시), Hash Table(해시 테이블)

1. 해시 함수(Hash Funtion)

데이터의 효율적인 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.

이 때 매핑전 원래 데이터의 값을 키(Key), 매핑 후 데이터의 값을 해시값(Hash value) 또는 해시코드, 매핑하는 과정 자체를 해싱(hashing) 이라고 합니다.

 

해시 함수의 가장 기본적인 성질은 두 해시 값이 다르면 원래의 데이터의 값도 다르다는 것입니다.

하지만, 같은 해시값을 가지고 있더라도 원래의 데이터가 꼭 같은 것은 아닙니다.

 

해시함수의 종류 : MD1, MD4, MD5, SHS, SHA-1, HAS-160 등

 

2. 해시테이블 (Hash Table)

해시테이블(Hash) 테이블은 효율적인 탐색을 위한 자료구조로 키(Key) 를 값(Value)에 대응시킵니다.

간단한 Hash 테이블을 구현하는 방법은 아래와 같습니다.

1. 해시 함수(hash function)으로 해시코드를 계산합니다. 
2. 해시값(해시코드) % array_length 등과 같이 배열의 인덱스를 구한다. 물론 서로 다른 두개의 해시코드가 같은 인덱스를 가리킬 수도 있습니다.
3. 배열의 각 인덱스에는 키(Key)와 값(Value) 로 이루어진 연결리스트를 선언합니다. 이러한 충돌 문제를 해결하기 위한 아이디어를 Chaining이라고 합니다. 충돌(Collision) 이란 서로 다른 두개의 키가 같은 해시코드를 가리키거나 서로 다른 두개의 해시코드가 같은 인덱스를 가리키는 경우를 말합니다.

따라서, 키에 상응하는 값을 찾기 위해서는 해시함수로 해시코드를 계산하고, 그 해시코드를 이용해 인덱스를 찾습니다.

그리고, 충돌에 대비하여 배열에 연결리스트를 사용하기 때문에 연결리스트를 탐색해 상응하는 키의 값을 찾아야 합니다.

 

충돌이 자주 발생한다면, 최악의 경우의 수행시간은 O(N)이 됩니다. (N은 키의 개수)

하지만, 일반적으로 해시에 대해 이야기 할 때는 충돌을 최소화하도록 잘 구현된 경우를 가정하는데 이 경우 탐색 시간은 O(1) 입니다.

 

3. Hash 구현 연습

'2. 해시테이블' 의 구현방법을 참조하여, hash를 구현 해보았습니다. 소스코드는 아래 GitHub 경로에 있습니다.

https://github.com/JunpilPark/algorithm/tree/master/hash/HashPracticeSource

JunpilPark/algorithm

 

4. 레퍼런스(Reference)

해시함수 : https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

해시 함수 - 위키백과, 우리 모두의 백과사전

해시함수의 종류 : http://blog.naver.com/PostView.nhn?blogId=nologout&logNo=220958739809

해시함수 종류(MD5, SHA, HAVAL, RIPEMD 등) 비교표

해시함수의 종류 :

https://ko.wikipedia.org/wiki/%EC%95%94%ED%98%B8%ED%99%94_%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

암호화 해시 함수 - 위키백과, 우리 모두의 백과사전

해시 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

해싱, 해시함수, 해시테이블 · ratsgo's blog