해쉬 테이블(Hash Table)

해쉬 테이블(Hash Table)

• 저장되는 데이터는 Key와 Value로 한 쌍을 이룸.

• 탐색의 시간복잡도가 거의 ​에 가깝다.

• dictionary나 map이라고 부르기도 한다.

해쉬 함수(Hash function)

• key 값의 범위를 제한하여 메모리를 절약하기 위한 방법

int GetHashValue(int key){
    return key % 2018;
}

• 위의 해쉬 함수에서는 key 값을 받아 크기가 2018인 배열에 들어갈 인덱스를 결정한다.

• key값에 따라 중복되는 인덱스가 나타날 수 있음. 이를 충돌이라고 하며, 충돌을 다루는 방법은 체이닝과 프로빙, 이중 해쉬 등이 있다.

체이닝(Chaining)

• 연결 리스트를 활용하여 충돌을 해결.

• 추가적인 메모리가 필요하다.

프로빙(Probing)

• 충돌이 발생했을 때 옆자리가 비어있는지 살펴보고, 비었을 겨우 그 자리에 대신 저장.

• 해쉬 함수를 ​라고 했을 때, ​가 충돌 되었다면, ​을 찾는다. 또 충돌이면 ​.

• 충돌의 횟수가 증가하면 한 군데 데이터가 집중되는 클러스터 현상이 발생.

• 이를 해결하기 위해 조금 더 멀리서 찾는 이차 프로빙(Quadratic Probing) 방법이 나옴.​ , ​ ...

이중 해쉬(Double Hash)

• 프로빙의 문제점은 충돌이 발생했을 때, 빈 자리를 찾는 위치가 항상 동일 한 것.

• 여전히 클러스터 현상이 발생할 확률이 높기 때문에, 빈 자리를 찾는 해쉬 함수를 하나 더 추가 하는 것이 이중 해쉬이다.

  • 1차 해쉬 함수 : 키를 근거로 저장위치를 결정

  • 2차 해쉬 함수 : 충돌 발생시 몇 칸 뒤를 살필지 결정