#14 해싱(Hashing)

1. 해싱(Hashing)

해싱은 데이터를 키:값의 쌍으로 구성하여 배열에서 인덱스로 데이터를 참조하듯 키로 데이터에 바로 접근할 수 있도록 하기위해

고안된 방식이다.  해시 함수(Hash Function)를 사용하여 키 값을 특정한 길이의 해시값으로 변환하고 이 해시값에 해당하는

위치에 데이터를 저장하는 것으로 삽입, 삭제, 탐색에 O(1)에 가까운 성능을 보이도록 한다.  Python의 dictionary 나 Java의
HashMap, HashTable 과 같이 대부분의 언어에서 내장 라이브러리로 지원하며 굉장히 자주 사용되는 유용한 방식이다. 

 

 

2. 용어

• 버킷(Bucket) : 해시 함수로 얻은 해시 값을 주소로 하는 저장 공간.  해시 방식은 미리 지정된 갯수만큼의 버킷을 만들어두고
                                데이터를 저장해나간다. 
  
  
• 슬롯(Slot) : 버킷이 데이터 하나를 저장하기 위해 사용하는 공간. 
  
  
• 충돌(Collision) : 서로 다른 키 값에 대해 해시 함수로 얻은 해시 값이 서로 동일한 경우, 즉 같은 버킷에 다수의 데이터를
                                    저장해야하는 상황을 의미한다.
• 클러스터링(Clustering) : 연속된 주소를 가진 버킷에 데이터가 밀집되는 현상을 의미한다.
• 부하율(Load Factor) : 전체 버킷 중 사용중인 버킷의 비율을 의미한다. 

 

 

3. 해싱의 특징

• 삽입, 삭제, 탐색에 평균적으로 O(1)의 성능을 보인다.
  
  
• 해시 함수의 특성상 언젠가 충돌이 반드시 발생하며 그럴수록 성능이 저하되기 때문에 해시 함수가 얼마나
  충돌이 일어나지 않도록 해시 값을 생성하느냐에 따라 성능이 크게 좌우된다.

 

 

4. 충돌(Collision) 의 처리

 ① 체이닝(Chaining) 기법

• 같은 해시 값을 가지는, 즉 같은 버킷에 저장해야할 데이터들을 연결 리스트의 형태로 이어붙이는 방식
  
  
• 비교적 구현이 간단하고 연결리스트를 사용하기 때문에 슬롯 갯수의 제약이 없다.
  
  
• 클러스터링에 영향을 거의 받지 않기 때문에 해시 함수를 선정할 때 충돌의 최소화만을 중점적으로 고려할 수 있다.
  
  
• 충돌이 많이 발생할 경우 최악의 경우 O(N) 수준까지 성능이 저하될 수 있다.
   
• 하나의 버킷의 슬롯 갯수가 일정 이상으로 늘어나면 연결 리스트 대신 이진 트리를 사용하여 검색효율을 높이기도 한다.
  
  
• 부하율이 높아져도 성능 저하가 선형적으로 발생하기 때문에 높은 부하율이 예상될수록 개방주소기법에 비해 성능이 좋다.
  
  
• 처음에 얻은 해시주소 내에서 문제를 해결하기 때문에 폐쇄 해싱(Closed Hashing)이라고도 한다.

 

 ② 개방주소(Open  Addressing) 기법

• 충돌이 발생할 경우 다른 비어있는 버킷을 찾아 데이터를 삽입하는 방식
  
  
• 체이닝 기법과 달리 추가적인 메모리나 외부 자료구조에서의 작업을 필요로하지 않는다.
  
  
• 연결리스트나 트리 등 외부 자료구조를 사용하지 않기 때문에 삽입/삭제의 오버헤드가 적어 저장할 데이터가  적다면
  체이닝 기법보다 좋은 성능을 보인다.
  
  
• 저장해야할 데이터가 많아져서 부하율이 일정 이상으로 증가하면 체이닝에 비해 성능이 급격히 저하된다.
• 비어있는 버킷을 찾는 방식으로 선형 탐색, 제곱 탐색, 이중 해싱이 있다. 
  
  
• 선형 탐색은 말그대로 선형적으로 다음 버킷을 참조해나가며 빈 버킷을 찾는 방식이다.
  
  
• 제곱 탐색은 처음 얻은 해시 값에서 제곱수만큼씩 증가해나가며 빈 버킷을 찾는 방식이다.
• 이중 해싱은 처음 얻은 해시 값이 충돌을 일으킬 경우 2차 해시 함수를 사용하여 다시한번 해시 값을 얻는 방식이다.
  가장 많은 연산을 필요로하지만 클러스터링의 영향을 거의 받지 않는다.
  
  

 ※ 클러스터링에 취약하다는 것은 반대로 참조 지역성(Locality of Reference)이 높다는 의미가 되기 때문에
      캐싱 성능이 좋아진다. 그렇기 때문에 선형탐색 -> 제곱 탐색 -> 이중 해싱 순으로 클러스터링 방지는 잘 되지만
      참조 지역성이 낮아져 캐싱 성능은 떨어진다. 체이닝 기법의 경우에도 클러스터링의 영향을 거의 받지 않기 때문에
      참조 지역성이 낮아 선형탐색을 통한 개방주소 기법에 비해 캐싱 성능이 떨어진다.

 

 

5. 리사이징(Resizing) & 재해싱(Rehashing)

• 부하율이 높아져 성능이 저하되는 것을 방지하기 위해 기존보다 더 많은 버킷을 할당한 뒤 기존에 저장된 데이터들을
  새로운 공간간에 다시해싱하는 작업 
  
  
• 개방주소법의 경우 삭제 시 발생하는 더미 데이터 등으로 인한 성능저하 문제도 있기 때문에 주기적인 재해싱을 해줘야
  성능을 유지할 수 있다.