[해시 테이블] 해시 테이블, 해시 함수

 

• 해시 테이블은 자료를 검색, 삽입, 삭제하는 데 평균시간이 가능하게 하여 극단적 효율에 다다른 자료구조
• 키 자신의 값에 따라 자리가 결정됨
• 해시 테이블은 키가 저장될 자리를 키의  '값'으로 결정하는 자료구조
• 해시 함수는 임의의 킷값을 입력으로 받아 주소 중 한 값을 리턴함(리턴값=해당 키를 저장하는 자리)
• 해시 함수
  • 나누기의 방법
  • 곱하기 방법
• 충돌
  • 어떤 키가 이미 자리 잡고 있는 상태에서 다른 키가 삽입을 시도하는 것
  • 동일한 주소에 2개 이상의 키가 해싱되는 상황
• 충돌 해결방법
  • 체이닝 : 충돌을 일으킨 키들을 연결 리스트로 관리하는 방법
  • 개방 주소 방법 : 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 것
• 검색 시간 
  • 체이닝, 개방 주소 방법으로 검색할 때의 기대시간
• 적재율
  • 해시 테이블에 원소가 차 있는 비율
  • 해시 테이블의 성능에 매우 중요한 영향을 미침
  • 적재율이 높을수록 충돌 확률은 높아져 해시 테이블의 성능이 나빠짐

 

 

해시테이블의 객체 구조

• 2가지 충돌 해결 방법에 따라 해시 테이블 구현 방식은 다르지만 둘 다 같은 모양의 객체를 가짐
• 키를 저장하는 배열 table[]의 타입이 다르고, 운용 방식이 다름

해시 테이블로 사용하는 배열
해시 테이블의 원소 개수
해시 테이블에서  원소 X를 검색하기
해시 테이블에 원소 X를 삽입하기
해시 테이블에서 원소 X를 삭제하기
해시 테이블이 빈 상태인지 알려주기
해시 테이블을 깨끗이 청소하

 

 

해시 함수

• 해시 함수는 키값을 입력으로 받아 해시 테이블상의 주소를 리턴함
• 해시 함수는 '입력 키를 해시 테이블 전체에 고루 분산시켜 저장해야 한다'라는 성질을 가져야함
• 두 키 값이 상대적으로 비슷하다고 해서 다른 키들보다 상대적으로 해시값이 더 비슷하지 않아야 함
  • 이 성질을 만족해야 서로 다른 두 키가 한 주소를 놓고 충돌한 확률이 낮아짐

 

해시 함수를 만드는 대표적인 방법

나누기 방법

• 해시 테이블 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 수축 시킴

h(x) = x%m

• m
  • 해시 테이블의 크기
  • 2의 멱수에 가깝지 않은 소수를 택하는 것이 좋음(멱수: 거듭 제곱으로 된 수)
  • 만일 m=2^p라면 입력 키의 하위 p비트에 의해 해시값이 결정되므로 분산시키기에 이상적이지 않음
  • 해시값은 모든 입력 키의 모든 비트를 이용하는 것이 확률적으로 좋은 분포를 갖도록 하는데 유리함
• %
  • 나머지 연산
  • 해시 테이블에 있는 m개의 자리가 0부터 m-1의 주소값을 가지므로 m으로 나눈 나머지 연산을 사용하는 것이 자연스러움

 

곱하기 방법

• 먼저 입력 값으 0과 1 사이의 소수로 대응시킨다음, 해시 테이블 크기 m을 곱하여 0부터 m-1 사이로 팽창시킴
• 해시 함수의 특성을 결정짓는 0<A<1 범위의 상수 A를 미리 준비해놓아야함
• 임의의 키에 대해
  • x에 A를 곱한 다음 소수부만 취하기
  • 방금 취한 소수부에 m을 곱하여 그 정수부를 취함 -> x의 주소 결정

h(x) = x%m

• 곱하기 방법은 해시 테이블의 크기 m을 아무렇게나 잡아도 상관 없음
• 따라서 컴퓨터의 이진수 환경에 맞게 m=2^p로 잡는 것이 자연스러움
• 컴퓨터 시스템에서 어떤 목적으로 메모리를 할당할 때 흔히 2의 멱수로 할당하므로 소수 크기로 할당하는 나누기 방법에 비해 낭비가 적음
• 대신 상수 A를 어떻게 잡느냐에 따라 해싯값 분포가 영향을 받음

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」