[ 자료구조 ] 해쉬 (Hash)

Hash 란?

• Hash
  데이터를 key-value 형태로 저장하고 Key값이 배열의 인덱스로 저장되기에 검색과 저장이 빠른 자료구조
• Hash Function & Hashing
  해시함수란 key값을 고정된 길이의 hash로 변환하는 함수이며, 해싱은 key값을 hash로 변환하는 과정이다.
  (즉, 해시함수를 사용하여 해싱작업을 하는것, key값으로 > hash 생성)
• Hash Table
  해시테이블은 연관배열구조를 이용하여 데이터를 key-value형태로 저장하는 자료구조.
  해시테이블은 key-value가 1:1 매핑구조이므로 삽입, 삭제, 검색 과정에서 평균적으로 O(1)의 복잡도를 가짐
  
  - 장점 : 중복제거, 데이터 캐시, 인덱스접근으로 빠른 연산속도
  - 단점 : 공간복잡도 커짐, 충돌 발생 가능성, 순서있는 배열에 부적합

 

 

 

Hash Table VS Hash Map

java에서 둘의 차이점은 동기화 지원여부와 널처리 여부이다.

	Hash table	Hash Map
동기화 지원	O	X
Null 허용	X	O

 

 

 

충돌 (Collision) 이란?

해싱을 했더니 같은 hash값이 나온경우 해싱충돌이라함. 

해시충돌 발생 시 개방주소법, 체이닝, 리사이징과 같은 방법으로 해결해야함.

 

• 체이닝 (Chaining)
  체이닝은 저장소(bucket)에서 충돌 발생 시 기존값과 새로운값을 LinkedList(추가메모리)로 연결하는 방식

        - 장점 : 미리 충돌 대비용 공간을 잡을 필요 없다. 
        - 단점 : 많은 양의 데이터 연결이 존재시 검색효율이 낮아짐.

• 개방 주소법(Open Addressing)
  충돌 발생 시 인덱스 뒤에 있는 빈 버킷을 찾아 데이터를 삽입하는 방식
  아래 사진에서는 152번에 john을 할당, 그 아래 빈버켓이 있다면 Sandra, 이후 Ted Baker를 삽입한다.
  
  
  [개방 주소법 탐색 방식]
  1. 선형 조사법 (linear probing)
  해시테이블을 ht, 해시값을 k라고 할 때 충돌이 ht[k]에서 발생했다면 비어있는 공간이 나올 때까지 ht[k]+1, ht[k]+2... 를 조사한다. 테이블의 마지막에 도달하게 되면 테이블의 처음부터 다시 비어있는 공간을 찾고, 만약 조사를 시작했던 위치로 다시 돌아오게 되면 테이블이 가득 찬 것이다.
  
  선형 조사법은 군집화(clustering) 문제가 발생 할 수 있다. 군집화란, 한 번 충돌이 시작되면 그 위치 근처에 항목들이 집중되는 현상이다. 군집화 문제가 발생하면 빈 공간을 탐색하는 시간이 오래 걸린다.
  
  2. 이차 탐사법(quadratic probing)
  충돌 발생 시 제곱 수를 증가시켜 다음 빈 슬롯을 탐색
  
  3. 더블 해싱(Double Hashing)
  충돌 발생 시 두번째 해시함수를 사용하여 위치를 탐색. 이 방법은 충돌해결하는데 시간이 오래걸리지만, 클러스터링 문제를 완화 가능
  
  
  
  
  

참고 자료
https://go-coding.tistory.com/30

[자료구조] Hash의 개념 및 설명