[자료구조] 해시 (Hash)

해시 (Hash)

해시는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 매핑하는 과정 또는 그 결과를 말한다.

해시 함수 (Hash Function)

• 매핑 과정을 수행하는 함수로서, 입력 데이터를 받아서 해시 값을 계산하여 반환하는 함수
• 동일한 입력에 대해서는 항상 동일한 해시 값을 반환하며, 입력 데이터가 조금이라도 변경되면 다른 해시 값을 생성
• 데이터의 무결성을 검증하거나 데이터의 식별을 위해 사용
• Divison 기법 : 간단한 해시 함수, 입력값을 특정 수로 나눈 나머지를 해시 값으로 사용
  • H(k) = k mod m, k = 입력값, m = 해시 테이블 크기)
    
    
• Multiplication 기법 : 입력값과 곱셈을 통해 해시 값을 계산하는 방법
  • 0에서 1사이의 상수 A를 선택하고 k * A 의 소수 부분만을 택한다.
  • 소수 부분에 m을 곱한 다음 소수점 아래를 버린다.
    
    
• Folding 기법 : 입력값을 여러 부분으로 나누어 합산한 결과를 사용
  • 자릿수마다 더하거나, 입력값을 여러 그룹으로 분할하여 각 그룹을 더하는 등의 방식
  • 입력값의 길이와 상관없이 일정한 크기의 해시 값을 생성할 수 있다.
    
    
• Cryptographic Hash Functions (암호 해시 함수)

해시 충돌 (Hash Collision)

• 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우
  • 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우

해시 충돌 해결 방법 1

개방 주소법 (Open Address)

• 충돌 시, 테이블에서 비어 있는 공간의 해시를 찾아 데이터를 저장
• 해시와 value가 1:1 관계 유지
• 비어 있는 공간 탐색 방법에 따라 분류 : 선형 탐사법, 제곱 탐사법, 이중 해싱

(1) 선형 탐사법 (Linear Probing)

• 빈 공간을 순차적으로 탐사하는 방법
  • 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사
    
    
• 일차 군집화 문제 발생 : 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 현상
• primary cluster (키가 연속해서 채워진 슬롯들) 가 생성되면 점점 커지는 경향이 있다.
• 검색 시간이 클러스터(cluster)의 길이에 비례하게 된다.

(2) 제곱 탐사법 (Quadratic Probing)

• 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법
  • 충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사
  • 충돌 발생 시 h(k), h(k) + 1^2, h(k) + 2^2, h(k) + 3^2, ... 순서로 탐사한다.
    
    
• 일차 군집화 문제 일부 보완
• 이차 군집화 문제 발생 가능성

(3) 이중 해싱 (Double Hashing)

• 해싱 함수를 이중으로 사용
  • 해시 함수 1 : 최초 해시를 구할 때 사용
  • 해시 함수 2 : 충돌 발생 시, 탐사 이동 간격을 구할 때 사용
    
    
• 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨

해시 충돌 해결 방법 2

분리 연결법 (Seperate Chaining)

• 해시 테이블을 연결 리스트로 구성
• 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아니라 연결 리스트를 이용하여 해당 테이블에 데이터를 연결
• 삭제와 삽입이 간단하지만 작은 데이터들을 저장할 때는 연결리스트 자체의 오버헤드가 부담이 될 수 있다.

개방 주소법 vs 분리 연결법

개방 주소법 (Open Addressing)

• 장점
  1. 메모리 사용량이 작고, 포인터를 사용하지 않아 데이터 저장에 필요한 공간이 적다.
  2. 데이터의 캐시 효율성이 높을 수 있다.
• 단점
  1. 충돌이 발생하면 다른 공간을 찾아야 하므로 검색 시간이 길어질 수 있다.
  2. 해시 테이블이 가득 차면 삽입이 불가능하다.

분리 연결법 (Seperate Chaining)

• 장점
  1. 충돌이 발생해도 다른 공간을 찾이 않아도 되므로 검색 시간이 일정하다.
  2. 해시 테이블이 가득 차도 연결 리스트를 통해 삽입이 가능하다.
• 단점
  1. 포인터를 사용하여 데이터를 연결해야 하므로 메모리 사용량이 증가한다.
  2. 포인터를 따라가는 추가적인 메모리 접근이 필요해 캐시 효율성이 낮을 수 있다.

(1) 해시 테이블의 크기가 작고 충돌이 적은 경우 : 개방 주소법

(2) 해시 테이블의 크기가 크거나 충돌이 많은 경우 : 분리 연결법

+ 캐시 효율성 : 컴퓨터 시스템에서 데이터에 빠르게 접근할 수 있는 캐시 메모리의 활용 정도를 나타내는 지표, 캐시 히트율(Cache Hit Rate)과 캐시 미스율(Cache Miss Rate)로 평가된다.