[자료구조] 해시 테이블 (Hash Table)

1. 해시 테이블

• 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조
  
  • 키를 통해 해당 데이터에 빠르게 접근 가능
• 해싱
  • 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정

2. 해시 테이블 구조

• 키
  • 해시 테이블 접근을 위한 입력 값
• 해시 함수
  • 키를 해시 값으로 매핑하는 연산
• 해시 값
  • 해시 테이블의 인덱스
• 해시 테이블
  • 키-값을 연관시켜 저장하는 데이터 구조
    

    

3. 해시 충돌

• 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우
  • 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우
• 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음
  

  

4. 해시 충돌 해결 방법

• 개방 주소법 (Open Address)
  • 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장
  • hash와 value가 1:1 관계 유지
  • 비어 있는 공간 탐색 방법에 따라 분류
    • 선형 탐사법 (Linear Probing)
      • 빈 공간을 순차적으로 탐사하는 방법
        • 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사
      • 일차 군집화 문제 발생
        • 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생
    • 제곱 탐사법 (Quadratic Probing)
      • 빈 공간을 n 제곱만큼의 간격을 두고 탐사하는 방법
        • 충돌 발생 지점부터 이후의 빈 공간을 n 제곱 간격으로 탐사
      • 일차 군집화 문제 일부 보완
      • 이차 군집화 문제 발생 가능성
    • 이중 해싱 (Double Hashing)
      • 해싱 함수를 이중으로 사용
        • 해시 함수 1: 최초 해시를 구할 때 사용
        • 해시 함수 2: 충돌 발생 시, 탐사 이동 간격을 구할 때 사용
      • 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨
• 분리 연결법 (Separate Chaining)
  • 해시 테이블을 연결 리스트로 구성
  • 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결

5. 코드

// 해시 함수
public static int getHash(int key) {
    return key % 5;
}

public static void main(String[] args) {
    Hashtable<String, Integer> ht = new Hashtable();

    ht.put("key1", 10);
    ht.put("key2", 20);
    ht.put("key3", 30);
    ht.put("key3", 50);

    for(Map.Entry<String, Integer> item : ht.entrySet()) {
        System.out.println(item.getKey() + " - " + item.getValue());
        // key3 - 50
        // key2 - 20
        // key1 - 10
    }
    
    // 해시 함수 사용한 해시 충돌 케이스
    Hashtable<Integer, Integer> ht2 = new Hashtable();
    ht2.put(getHash(1), 10);
    ht2.put(getHash(2), 20);
    ht2.put(getHash(3), 30);
    ht2.put(getHash(4), 40);
    ht2.put(getHash(5), 50);
    
    // 충돌 전
    for(Map.Entry<Integer, Integer> item : ht.entrySet()) {
        System.out.println(item.getKey() + " - " + item.getValue());
        // 4 - 40
        // 3 - 30
        // 2 - 20
        // 1 - 10
        // 0 - 50
    }
    
    ht2.put(getHash(6), 60);

    // 충돌 후
    for(Map.Entry<Integer, Integer> item : ht.entrySet()) {
        System.out.println(item.getKey() + " - " + item.getValue());
        // 4 - 40
        // 3 - 30
        // 2 - 20
        // 1 - 60
        // 0 - 50
    }
}