hash table

해시는 삽입,삭제,탐색시 O(1)을 지향한다.

이진탐색트리와 비교할 경우, 데이터 탐색시 O(N*logN)이다. 배열의 경우 탐색시 O(1)이지만, 메모리를 미리 할당해야 둬야 하기 때문에 공간 효율적이지 않다.

하지만 해시의 문제점은 해시충돌이다.

해결책#1 : 체이닝

한 버킷당 들어갈 수 있는 엔트리 수에 제한을 두지 않고 모든 자료를 해시테이블에 담는 것

제한을 두지 않고 담는 방법은 기존 노드에 추가된 노드를 nextNode로 가리킨다. Linked List와 같다.

유연하지만, 메모리 문제가 야기된다.

삽입, 삭제, 탐색시 만약 한곳에 데이터가 전부 들어가있을 경우 O(N)이 걸릴 수 있다. 이외에 동일하게 상수 시간이다.

해결책#2: probing

체이닝과 다르게 한 버킷당 1개의 엔트리만 들어갈 수 있다. 이 때 충돌하게 되면 탐사(probing)를 하게 된다. 즉 새로운 주소를 찾는다.

1. Linear probing

가장 간단한 방식이다. 충돌 일으키면 다음칸에 저장한다.

1. 제곱 probing

충돌 일으키면 제곱만큼 이동.

1. 이중 해싱

2개의 해시 함수 준비. 충돌일어나면 2번째 해시함수를 통해 탐사 이동폭을 얻기 위해 사용.