자료 구조 - Hash

해시

색인(Index)에 해시값을 사용하는 자료 구조

정렬을 하지 않고도 빠른 검색, 빠른 삽입이 가능하다

<파이썬 알고리즘 인터뷰> p.286, 책만, 2020 / 개별 체이닝(Separate Chaining) 방식

 

해시 함수

Key를 해시(값)로 매핑하는 함수를 말한다

 

문제점

해시 함수는 보통 입력값의 범위보다 출력값의 범위가 좁은 경우가 많기 때문에

입력이 다름에도 불구하고 드물게 동일한 값이 출력되는 경우도 존재한다

(이러한 경우를 해시 충돌이라고 함)

 

해시 충돌에 대비하는 방법으로는 개별 체이닝(Separate Chaining)과 오픈 어드레싱(Open Addressing) 등이 있다

 

개별 체이닝(Separate Chaining)

리스트의 각각의 색인을 연결 리스트로 만든다

새로 입력이 될 때마다 같은 해시를 가진다 하더라도 색인이 연결리스트로 구현되어 있기 때문에

원하는 데이터의 접근이 가능해진다

 

오픈 어드레싱(Open Addressing)

해당 해시의 다음 순번에 위치한 색인들 중 비어있는 곳에 넣는 방식이다

다음 순번의 색인을 구하는 방식으로는 보통 다음과 같은 방법이 있다

+1 하는 방식인 선형 탐색법(Linear Probing)

1, 2(=1+1), 6(=2+4), 15(=6+9), ...처럼 n의 제곱을 더하는 방식인 2차 탐색법(Quadratic Probing)

추가적인 해시값으로 다음 위치를 결정하는 2중 해싱(Double Hashing) 

 

STL의 unordered_map

STL의 unordered_map은 hash를 이용해서 만든 클래스이다

(참고로 STL의 map은 Red - Black Tree)

 

해시 함수를 통해 key를 특정 값으로 변환시키고 이 값을 value를 저장할 공간의 인덱스로 사용한다

저장되는 공간은 보통 bucket 또는 slot이라고 한다

(bucket_count()를 이용하면 전체 bucket 카운트를 구할 수 있음)

 

SSS