Hash(해시)란?

해시

 

• 해시란 다양한 길이를 가진 데이터를 고정 길이를 가진 데이터로 매핑한 값 해당 과정은 해시함수를 통해 진행되며 해시값 자체를 index로 사용하게이 평균 시간복잡도가 O(1)으로 매우 빠르다. 최악의 경우 O(n)이 될 수 있다.
• 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)를 도출할 수 있다

 

해시의 충돌

key를 해시함수를 통해서 해시코드로 변환시키고 이 해시코드를 인덱스로 사용하여 값(value)를 저장하는데 이러한 경우 충돌이 발생할 수 있다

 

※ 비둘기집 원리

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ebssmd02&logNo=221289209404

위 그림에서 비둘기는 총 10마리인데, 상자가 9개밖에 존재하지 않을때 최소 한 상자에는 2마리의 비둘기가 들어가게 된다

대부분의 해시 알고리즘은 고정된 길이의 문자열을 반환한다. MD5 해시 알고리즘은 128비트의 값을 반환하는데, 한 비트 단위가 0 혹은 1 두가지 경우의 수를 가진다는 점에서 총 2^128개 만큼의 문자열을 반환할 수 있다. 이는 매우 큰 숫자이지만 무한은 아니다. 하지만 입력값은 무한하다. 따라서 특정한 두 입력값의 해시 결과값이 동일한 결과가 발생할 수 있다. 이러한 원리에 따라 해시 충돌이 발생할 수 있다.

 

이러한 충돌을 해결하는 두 가지 방법이

1.  Separate Chaining 

2. Open Addressing(개방 주소법) 이 있다

 

Separate Chaining 

해시 충돌이 일어나면 연결 리스트를 이용해 데이터들을 연결하는 방식

장점 

한정된 저장 공간을 효율적으로 사용할 수 있다

매번 이어 붙이기 때문에 메모리 공간을 미리 잡아 놓을 필요가 없다

 

단점

하나의 hash에만 자료가 계속 들어가면 검색 효율이 떨어진다

 

 

Open Addressing

 

비어있는 해시를 찾아 데이터를 저장하는 방법  그러므로 해시 테이블은 1개의 해시와 1개의 값이 매칭되어있는 형태

장점

추가 저장공간이 필요없다

 

단점

데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야 한다