Hash Table

해싱(Hashing)

- key-value를 해시 함수를 이용하여 매핑하는 것

- 빠르게 요소에 접근할 수 있다.

 

해시 테이블(Hash Table)

- 해시 함수를 이용하여 변환한 값들을 index 삼아 key-value 쌍으로 저장한 자료 구조

- 저장/검색을 하는 데 있어 복잡도가 평균적으로 O(1)로, 가장 낮다.

- 매우 빠른 응답

- 파이썬의 Dictionary, 루비의 Hash, 자바의 Map이 이에 해당한다.

- IP와 이에 해당하는 컴퓨터 이름, 주민등록 시스템 등 다양한 방식으로 응용 가능하다.

- 최소 원소를 찾는 등의 작업은 지원 X

 

Load factor ⍺

- 해시 테이블의 검색 효율과 밀접한 관련

- 해시 테이블 전체에서 얼마나 원소가 차 있는지를 나타내는 수치

- n개의 원소가 저장되어 있다면 ⍺= n/m

- Load Factor가 높아지면 해시 테이블의 효율이 떨어진다.

- 따라서 threshold를 미리 설정해 둔다. => 이를 넘어 서면 해시테이블의 크기를 두 배로 늘린 다음, 다시 해싱한다.

 

Hash Function(해시 함수)

- 해시 함수를 통해 인덱스 값이 결정된다.

- 입력 원소가 해시 테이블에 고루 저장되어야 한다.

- 계산이 간단해야 한다.

- Division method와 Multiplication method가 있다.

 

Division method

h(x) = x mod m

- m: table 사이즈(주로 소수임)

 

Multiplication method

h(x) = (xA mod 1) * m

- A : 0 < A < 1 인 상수

- m = 2^p (p는 정수)

 

 

Collision

- 해시 테이블의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것

- chaining과 Open Addressing이 있다.

 

 

Chaining

- 같은 주소로 해싱되는 원소를 모두 하나의 Linked List로 관리한다.

- 추가적인 Linked List 필요

 

Open Addressiong

- 빈 자리가 생길 때까지 해시값을 계속 만들어낸다.

- Linear probing, Quadratic probing, Double hashing의 방법이 있다.

 

Linear Probing

- 하지만 *Primary Clustering에 약하다.

- Primary Clustering : 특정 영역에 원소가 몰리는 현상

 

Quadratic Probing

- 하지만 *Secondary Clustering에 약하다

- Secondary Clustering : 여러 개의 원소가 동일한 초기 해시 함수 값을 갖는 현상

 

Double Hashing

- 삭제 후에는 삭제 되었다는 표시를 해야 한다.

 

 

 

 

참조 --

https://www.geeksforgeeks.org/hashing-data-structure/

Hashing Data Structure - GeeksforGeeks

https://nlp.chonbuk.ac.kr/AL/ch06.pdf

 

https://velog.io/@edie_ko/hashtable-with-js

자료구조 | 해시 테이블 hash table