자료구조 - 해싱

해싱(Hashing)

해싱이란?

• 해시 함수와 해시 테이블을 이용하여 데이터를 빠르게 저장하고 탐색하는 방법
• 데이터를 해시 테이블이라는 배열에 저장하고
• 데이터의 키 값으로 해시 함수를 통하여 테이블의 주소를 반환하여 원하는 데이터를 찾는 방식

해시 테이블

• 값의 연산에 의해 직접 접근 가능한 구조

해시 함수

• 해시 테이블에서 기 값을 주소로 변환하는데 사용되는 함수
• 계산이 빠르고 간단해야 하며, 다른 키 값이 같은 주소를 산출하는 경우가 적어야 함

해시 함수 종류

• 나눗셈법
• 중간 제곱법
• 폴딩법
• 기수 변환법
• 자리수 분석법

나눗셈법

• 키 값을 정수로 보고 이를 적당한 양의 정수(주소, 해시 테이블의 크기 등)로 나누어 그 나머지를 해시 주소로 하는 방법
• h(k) = k mod N
• h(): 해시 함수
• k: 키 값
• N: 나누는 수

특징

• 주소 계산법이 매우 간단하지만 나누는 수 N을 적당하게 선택하는 것이 쉽지 않음

N 선택 시 고려사항

• N 값은 충돌 발생의 가능성을 최소화하도록 선정
• 따라서 나누는 값 N은 소수로 정하는 것이 좋음

예시

• 키 값 : 172148
• 주소 공간 영역 : 7000
• 주소 공간 영역에 가까운 소수 : 6997
• 해시 주소 : 4220172148 / 6997 = 24 …. 4220

중간 제곱법

• 키 값을 제곱한 다음 그 제곱값의 중간 부분의 적당한 자리수를 해시 주소로 정하는 방법

예시

• 키 값 k = 7642
• k^2 = 58247424
• 해시 테이블의 주소 : 2474
• 58247424

폴딩법(folding)

• 키를 같은 크기의 부분으로 나누고(접고), 이들을 모두 더하거나 배타적 논리합(XOR) 등을 취하여 해시 주소를 정하는 방법
• 이동 폴딩(shift folding)
  • 각 부분을 오른쪽 끝을 맞추어 더한 값을 해시 주소로 정하는 방법

충돌

• 해시 테이블에 데이터를 삽입할 때 서로 다른 데이터가 같은 주소에 배당되는 것
• 오버플로우라고도 함
• 충돌(오버플로우) 해결법
  • 선형 조사법
  • 2차 조사법
  • 체이닝

선형 조사법

• 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장하는데
• 충돌이 발생한 자리에서 그 다음 버킷들을 차례로 하나씩 조사하여 최초로 나오는 빈 버킷에 데이터를 삽입하는 방법
• 장점
  • 주소 계산이 간단함
• 단점
  • 조사 시간이 많이 걸림
  • 해시 테이블 상에 데이터의 위치가 일정한 키에 의해 집단으로 뭉치는 경향 발생

2차 조사법

• 충돌이 발생했을 때 원래 주소로부터 2차함수 되는 거리만큼 떨어진 곳을 차례로 검색해서 최초로 나오는 빈 곳에 해당 데이터를 삽입하는 방법
• 장점
  • 주소 계산이 간단함
  • 데이터들의 윙치가 일정한 키를 중심으로 뭉치려는 경향을 어느정도 배제 가능
• 단점
  • 해시 테이블 모든 버킷 다 조사되지는 않음

체이닝법

• 각 버킷에 삽입과 삭제가 용이한 연결 리스트를 구성하는 방법
• 해시 테이블 자체는 포인터의 배열로 만들고, 같은 버킷에 해당되는 데이터들을 체인(연결리스트)으로 만들어서 연결
• 장점
  • 삽입, 삭제 시 문제 없음
• 단점
  • 포인터 연산이기 때문에 동적인 기억 장소 할당 필요
  • 링크 필드로 사용되는 부가적인 기억 장소 필요