[자료구조] 해시 테이블

<content>

• 해시함수
• 좋은 해시함수의 특징
• 비둘기집 원리
• 로드 팩터 (load factor)
• 충돌
• separate chaining
• open addressing

---

 

 

해시함수?

• ⭐ 임의 크기 데이터를 고정 크기 값으로 mapping하는데 사용할 수 있는 함수
• 해시테이블의 핵심이다!
  해시테이블을 인덱싱하기 위해서 해시함수를 사용하는데, 이것을 해싱(hashing)이라 한다.
  
• 어떠한 입력이든 고정 크기의 값으로 mapping해준다는 의미는
  입력이 3글자이든, 4글자이든, 5글자이든 2자리의 숫자로 mapping해줄 수 있다는 의미이다.

 

---

좋은 해시함수의 특징

• 해시함수 값 충돌의 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시 값이 균일하게 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시 테이블 사용 효율이 높은 것
• 좋은 해시함수 예시
  • hash table의 사이즈 = 2^n이라고 가정 
  • 1. key를 2^n으로 나눈 나머지
  • 2. 전체 bit pattern을 n개의 구간으로 나누고 XOR 연산을 수행하면서 접는 방법
  • 3. key를 제곱한 뒤, n bits를 선택
  • 4. key를 다항식에 넣은 뒤, 그 결과를 2^n으로 나눈 나머지

 

---

비둘기집 원리

• n개 아이템을 m개 컨테이너에 넣을 때
  n>m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템들이 들어 있다
• 이것을 해시 테이블과 연관지어 생각해보면
  데이터의 수가 n, 버킷의 수가 m일 때 n>m이면 어떤 버킷에는 2개 이상의 데이터가 들어있다는 뜻

 

---

로드 팩터

• 로드 팩터란, 해시 테이블에 저장된 데이터의 개수 n을 버킷의 개수 k로 나눈 것
• load factor = n/k
• 로드 팩터의 값에 따라 해시 함수를 재작성해야 될지 아니면 해시 테이블의 크기를 조정해야 할 지 결정한다.
• 또한 로드 팩터의 값은 해시 함수가 key를 잘 분산해주는지 말하는 효율성 측정에서도 사용된다.
• 일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소한다.
• 자바10의 경우 로드 팩터가 0.75가 넘어설 경우 해시 테이블의 공간을 재할당한다.

 

---

해시 함수

• key가 해시 함수를 통과하여 해시 값으로 바뀐다.
• 해시 테이블을 인덱싱하기 위해서 해시 함수를 사용하는 것을 해싱(hashing)이라고 한다.
• 해싱 알고리즘에는 다양한 것들이 있다.
• 해싱 알고리즘 중 가장 단순하면서 널리 쓰이는 것은 정수형 해싱 기법인 modulo-division method이다.
  • h(x) = x mod m : 입력값 x를 해시테이블의 크기 m으로 나눈 나머지
• 구글은 해시 함수를 딥러닝으로 학습한 모델을 적용해 충돌을 최소화하는 논문을 발표했다 (!)

 

---

충돌

• 아무리 좋은 해시 함수라 하더라도 충돌은 발생한다.
• 여기서 충돌이란, 다른 입력에 대해 동일한 해시값이 나오는 현상을 말한다.

 

---

개별 체이닝 (separate chaining)

https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/

• 충돌 발생 시, 연결리스트 등 자료구조와 연결하는 방식이다.
  • 메모리 할당하여 추가해주면 된다.
• 기본적인 자료구조만 있으면 되기 때문에 개별 체이닝 방식은 인기가 높다.
  • C++, 자바는 separate chaining 방식 사용하여 해시 테이블 구현
• 개별 체이닝 방식의 해시 테이블
  • 키의 해시 값을 계산한다 (해시 함수 이용)
  • 해시 값을 이용해 배열의 인덱스를 구한다.
  • 같은 인덱스가 있다면 연결리스트로 연결한다.
• 잘 구현한 경우 대부분의 탐색은 O(1)
• 최악의 경우 (해시 충돌이 계속 발생하는 경우) 탐색은 O(n)이다.
• 자바8에서는 데이터의 개수가 많아지면 red-black tree에 저장하는 형태를 사용하기도 했다.

 

---

오픈 어드레싱 (open addressing)

https://en.wikipedia.org/wiki/Open_addressing

• 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식이다.
• 무한정 저장할 수 있는 separate chaining 방식과 달리, open addressing 방식은 전체 slot 개수 이상은 저장할 수 없다.
• 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.
• open addressing에도 여러가지 방법이 있다.
  • linear probing
    • 충돌이 발생한 경우, 해당 위치부터 순차적으로 탐사를 진행
    • 간단하면서 전체적인 성능이 좋은 편이다.
    • 하지만 해시 테이블에 저장되는 데이터들이 뭉치는 문제점이 존재 (cluster 형성)
    • 해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 현상을 클러스터링이라고 한다.
      클러스터끼리 합쳐지면 특정 위치에는 데이터가 몰리고, 다른 위치에는 데이터가 없는 상태가 된다.
      이러한 현상은 해시 테이블의 탐색 시간을 증가하게 한다.
  • quadratic probing
    • 간격이 2차 함수꼴로 증가 (+1, +4, +9, ...)
    • linear probing에서 cluster 형성의 문제를 막기 위한 방법
  • double hashing
    • 현재 hash 값에 또 다른 hash function을 사용하여 이동할 거리를 정한다.
• open addressing 방식은 bucket size보다 큰 경우에는 삽입할 수 없다.
• 따라서 hash table의 일정 비율이상 채워지면 더 큰 크기의 또 다른 bucket을 생성한 후,
  여기에 새롭게 복사하는 re-hashing 작업이 일어난다.

 

---

separate chaining과 open addressing의 비교

출처 : 파이썬 알고리즘 인터뷰 책

• 일반적으로 open addressing의 방법 중 하나인 선형 탐사는 separate chaining보다 성능이 좋다.
• 하지만 hash table의 80% 이상이 차게 되면 open addressing 방식의 성능은 급격히 저하된다.
• 또한 open addressing 방식은 hash table 크기 이상 저장할 수 없다.
• 따라서 파이썬은 open addressing 방식을 택하되, load factor를 작게 잡아 성능 저하 문제를 해결한다.
•  

	chaining	open addressing
충돌 해결	다른 자료구조 이용하여 해결	hash table 자체만 이용하여 해결
메모리 사용	pointer size overhead	오버헤드 없다
load factor에 따른 성능 변화	directly proportional	proportional to (load factor/(1-load factor)
hash table size보다 더 많은 item 저장 가능 여부	가능하다	불가능하다
hash function 요구사항	균등 분포	균등 분포 (+ cluster를 피해야 한다)
removal	가능	removals clog the hash table with 'deleted' entries.
구현	간단하다	비교적 어렵다

www.algolist.net/Data_structures/Hash_table/Open_addressing

 

 

* open addressing에서의 삭제

 

linear probling을 예시로 들겠다.

• hash function(a) = 3 -> 3번 해쉬값에 대응되는 hash table에 값 저장
• hash function(b) = 3 -> 3번 해쉬값에 대응되는 hash table에 이미 값 존재 -> 4번 비어있으므로 4번에 저장
• hash function(c) = 3 -> 3번 이미 존재 -> 4번도 이미 존재 -> 5번 비어있으므로 5번에 저장
• 이 때, index 4에 저장된 값을 지워버리면 index 5번에 저장된 값을 찾아갈 수 없다.
  • 왜냐하면 hash function(c) = 3이 나왔을 때 3 찾고 없으면 4를 찾아보는데
    이 때 4번이 비어있으면 더이상 탐색을 하지 않기 때문이다.
  • 만약에 4번이 비어있어도 4번을 다음을 search하게 하려면 search의 성능이 O(N)이 되버린다.
  • 따라서 삭제하는 것을 지원하지 않기도 한다.

 

---

언어별 해시 테이블 구현 방식

• 파이썬에서 해시 테이블로 구현된 자료형은 딕셔너리
  • 파이썬의 해시 테이블은 open addressing 방식이다.
  • separate chaining은 추가 메모리 할당이 필요한데, 이 과정은 상대적으로 느리기 때문에 선택 X
• C++ : separte chaining
• 자바 : separate chaining