[자료구조] Hash table

Hash table 이란?

효율적인 탐색을 위한 자료구조로써 key-value쌍으로 데이터를 저장합니다. 이때 hash function를 사용하여

index(해시값) 는 h(key)가 됩니다.

 

시간 복잡도는 저장,삭제,검색 모두 기본 적으로 O(1) 이지만 collision(인덱스 중복)이 일어나는 최악의 상황이면 O(n)이 될 수 있음. 이렇게 시간은 빠르지만 공간효율성은 떨어짐

 

그럼 좋은 hash function은 뭘까요?

해시값이 최대한 겹치지 않아야하고 연산속도가 빨라야합니다.

 

 

그럼 인덱스(해시값) 중복(collision)이 일어나면 어떻게 되며 해결방법은?

크게 2가지 방법으로 해결

 

open addressing

- 미리 정해진 규칙에 따라 hash table의 빈 슬롯을 찾음.

- 빈 슬롯 찾는 방법에 따라 크게 Linear Probing(선형 조사법), Quadratic Probing(이차 조사법), Double Hashing(이중해시, 중복해시)으로 나뉨

- 선형 조사법 -> 충돌이 발생한 해시값으로 부터 일정한 값 만큼(+1,+2,+3...) 건너 뛰어, 비어 있는 곳에 저장

- 이차 조사법 -> 제곱수로 건너뛰어 저장

- 이중 해시, 중복해시 -> 해시 함수가 두개 첫번째 해시 함수는 저장할 위치 두번째 해시 함수는 건너뛰는 값 구하기 위해 사용

 

separete chaining

- linked list에 노드를 추가하여 데이터 저장