[자료구조] Hash Table -3

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.

https://github.com/ejImDev/data_structure_study.git

동적 해싱

• 대용량의 데이터베이스를 위한 해시방법으로 재해싱을 수행하지 않고 동적으로 해시테이블의 크기를 조절
  
  

• 대표적인 동적해싱
  

  • 확장 해싱
    
  • 선형 해싱
    
    

확장해싱

• 디렉터리를 메인메모리에 저장하고, 데이터는 디스크 블록 크기의 버킷 단위로 저장
• 버킷이란 키를 저장하는 곳
  
• 확장해싱에서는 버킷에 overflow가 발생하면 새 버킷을 만들어 나누어 저장하며 이때 이 버킷들을 가리키던 디렉터리는 2배로 확장
  
• 즉, 디렉터리를 확장
  
  

선형해싱

• 디렉터리 사용 없이, 삽입할 때 버킷을 순서대로 추가하는 방식
  
• 추가되는 버킷은 삽입되는 키가 저장되는 버킷과 무관하게 순차적으로 추가
  
• 만일 삽입되는 버킷에 저장공간이 없으면 overflow 체인에 새 키를 삽입
  
• 체인은 단순연결리스트로서 오버플로우 된 키들을 임시로 저장하고, 나중에 버킷이 추가되면 overflow 체인의 키들을 버킷으로 이동
  
• 오버플로우가 일어날 경우 버킷 개수가 linear하게 (하나씩) 증가됨
  
  

## 해시방법의 성능 비교 및 응용

• 해시방법의 성능은 탐색이나 삽입 연산을 수행할 때 성공과 실패한 경우를 각각 분석하여 측정
  
• 선형조사는 적재율 ∝가 너무 작으면 해시 테이블에 empty 원소가 너무 많고, ∝ 값이 1.0에 근접할수록 군집화가 심화됨
  
• 개방주소방식의 해싱은 ∝∽0.5, 즉, M∼2N일때 상수시간 성능 보임
  
• 체이닝은 ∝가 너무 작으면 대부붑ㄴ의 연결리스트들이 empty가 되고, ∝가 너무 크면 연결리스트들의 길이가 너무 길어져 해시성능이 매우 저하됨
  

• 일반적으로 M이 소수이다
  
  

• 이러한 해시함수들의 공통점
  
  • 키의 모든 자리의 숫자들이 함수 계산에 참여함으로써 계산 결과에서는 원래의 키에 부여된 의미나 특성을 찾아볼 수 없게 된다는 점
    
  • 계산 결과에서 해시테이블의 크기에 따라 특정부분만 해시값으로 활용한다는 점
    
    
• 가장 널리 사용되는 해시함수 : 나눗셈 함수
  
  • 나눗셈 함수는 키를 소수 M으로 나눈 뒤, 그 나머지를 해시값으로 사용
    
  • h(key) = key % M이고, 따라서 해시테이블의 인덱스는 0에서 M-1이 됨
    
  • 여기서 제수로 소수를 사용하는 이유는 나눗셈 연산을 했을 때, 소수가 키들을 균등하게 인덱스로 변환시키는 성질을 갖기 때문
    
    

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/6YTPEDcAKaU