[자료구조/알고리즘] 해시맵(해시 테이블)

해시 맵(Hash Map), 해시 테이블(Hash Table) 

키(key), 값(Value) 을 대응시켜 저장하는 데이터 구조.

- 키를 통해 해당 데이터에 빠르게 접근 가능하다는 특징.

해싱 : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정.

 

키(Keys) : 해시 테이블 접근을 위한 입력 값.

해시 함수(Hash Function) : 키를 해시 값으로 매핑하는 연산

해시 값(Hash Value) : 해시 테이블의 인덱스

해시 테이블(Hash Table) : 키 - 값을 연관시켜 저장하는 데이터 구조.

 

해시 충돌

해시 테이블의 같은 공간에서 서로 다른 값을 저장하려는 경우 (또는 서로 다른 키의 해시 함수를 통한 값이 동일한 경우) 에 발생한다.

개방 주소법 // 분리 연결법, 크게 2가지 해결 방법이있다.

 

개방 주소법(Open Address) : 충돌 시, 테이블에서 비어 있는 공간의 Hash를 찾아 데이터를 저장한다.

- Hash 와 Value가 1대1 관계를 유지

- 비어있는 공간 탐색 방법에 따라 분류, -> 선형 탐사법, 제곱 탐사법, 이중 해싱

가. 선형 탐사법 (Linear Probing)

빈 공간을 순차적으로 탐사하는 방법, 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사

단점으론 일차 군집화 문제가 발생. (반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우에 발생)

나. 제곱 탐사법 (Quadratic Probing)

빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법, 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사.

위의 단점이었던 일차 군집화 문제를 일부 보완했지만, 이차 군집화 문제 발생 가능성이 있다.

 

다. 이중해싱 (Double Hashing)

해싱 함수를 이중으로 사용

- 해시 함수 1 : 최초 해시를 구할 때 사용

- 해시 함수 2 : 충돌 발생 시, 탐사 이동  간격을 구할 때 사용.

선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨.

 

분리 연결법(Separate Chaining) 

- 해시 테이블을 연결 리스트로 구성, 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결.

하지만 연결 리스트로 구성되어 있는 해시 테이블 때문에 추후에 해당 데이터 값을 찾으려고 하면 상대적으로 앞의 방법들에 비해 오래 걸린다는 단점도 있다.