해시테이블이란?

key, value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있다. 평균 시간복잡도는 O(1)이다.

키를 해시함수를 적용해 배열의 고유한 index에 저장하는 방식인데 이때 충돌이 발생하는데 분리연결법과 개방 주소법으로 해결하고있다.

분리 연결법

충돌이 발생하면 연결리스트를 통해 해당 인덱스에 다음번에 저장하는 방식 위 그림이 분리연결법을 나타내는 그림이다.

개방 주소법

충돌 발생시 비어있는 해시테이블에 저장하는 방식인데 간단하게 설명하자면
고정폭 만큼 이동하여 차례대로 넣는 방식이나, 제곱폭으로 저장하는 방식, 해싱을 한번 더 하는 방식이 있다.

Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.

Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.

Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

파이썬으로 구현하기

사실 파이썬에 우리가 이미 사용하고 있는 해시테이블이 있다.

key, value를 사용하고 있는 dictionary자료형을 사용하면 된다

파이썬은 해시테이블을 분리연결법으로 구현하였다.

이미지출처:https://jsonsang2.tistory.com/14