hash table
해시는 삽입,삭제,탐색시 O(1)을 지향한다.
이진탐색트리와 비교할 경우, 데이터 탐색시 O(N*logN)이다. 배열의 경우 탐색시 O(1)이지만, 메모리를 미리 할당해야 둬야 하기 때문에 공간 효율적이지 않다.
하지만 해시의 문제점은 해시충돌이다.
한 버킷당 들어갈 수 있는 엔트리 수에 제한을 두지 않고 모든 자료를 해시테이블에 담는 것
제한을 두지 않고 담는 방법은 기존 노드에 추가된 노드를 nextNode로 가리킨다. Linked List와 같다.
유연하지만, 메모리 문제가 야기된다.
삽입, 삭제, 탐색시 만약 한곳에 데이터가 전부 들어가있을 경우 O(N)이 걸릴 수 있다. 이외에 동일하게 상수 시간이다.
체이닝과 다르게 한 버킷당 1개의 엔트리만 들어갈 수 있다. 이 때 충돌하게 되면 탐사(probing)를 하게 된다. 즉 새로운 주소를 찾는다.
가장 간단한 방식이다. 충돌 일으키면 다음칸에 저장한다.
충돌 일으키면 제곱만큼 이동.
2개의 해시 함수 준비. 충돌일어나면 2번째 해시함수를 통해 탐사 이동폭을 얻기 위해 사용.
