[Data Structure] HashTable(해시테이블)

HashTable

[key, value] 쌍으로 저장하는 비선형 자료구조이다.

일정 크기의 배열을 생성 => key 값을 해시 함수를 통해 배열 Index 변환 => Index에 [key, value] 저장

 

비선형 자료구조 이유?

선형 자료구조는 순차적으로 데이터를 저장한다.

하지만, HashTable에서는 해시 함수로 어떤 인덱스 값이 나올지 몰라서, 순차적으로 저장하지 않으므로, 비선형 자료구조이다.

 

시간복잡도

x라는 value값이 있는지 탐색	O(N)
x라는 key값이 있는지 탐색	O(1)
x라는 key에 접근	O(1)
[key, value] 저장, 삭제	O(1)

 

해시충돌(Hash Collision)

HashTable은 일정한 크기에 배열에 [key, value]를 저장해서 유한한 메모리에 저장해야한다.

해시 함수를 사용해도 서로 다른 key값의 반환 값이 동일한 경우를 말한다.

해시 충돌이 발생하면, 최악의 경우 O(N)까지 증가할 수 있다.(탐색, 접근 연산)

해시 충돌이 발생하지 않아야 성능이 좋은 해시 함수이다.

 

비둘기집의 원리

N + 1개의 물건을 N개의 가방에 담을 경우, 하나의 가방에는 무조건 2개의 물건이 들어가 있다는 원리

 

Open Addressing

비어 있는 다른 주소(버킷)에 데이터를 저장

 

Linear Probing(선형 프로빙)

해시 함수에서 나온 값이 동일한 값이 나올 경우, 한칸씩 미룬다.

 

Quadratic Probing(이차식 프로빙)

해시 함수에서 나온 값이 동일한 값이 나올 경우, 충돌 횟수에 대한 제곱값 , 상수를 이용해 칸을 미룬다.

 

Double Hashing(이중 해싱)

해시 함수를 두번 적용한다.

 

Chaining

충돌이 발생한 주소(버킷)의 데이터를 LinkedList or BST(Binary Search Tree)로 연결

 

Java에서의 chaining

해시 충돌한 데이터의 수가 7개 이하 => LinkedList(접근, 탐색에서 성능적으로 분리)

해시 충돌한 데이터의 수가 8개 이상 => BST(시간복잡도 O(logN) 단축시키기 위함)

 

Load Factor

저장할 데이터 수 대비 너무 작은 사이즈로 인해서, 성능이 저하되는 것을 방지하기 위해 HashTable은 어느 정도 수준 이상 추가되면, 버킷 사이즈를 늘리고 Rehashing을 수행