해시테이블 (HashTable) 이란?

• 해시함수를 사용하여 변환한 값을 색인(index)로 삼아 키(KEY)와 값(VALUE)를 대응시켜 저장하는 데이터 구조

• 키를 통해 해당 데이터에 빠르게 접근이 가능하다.

• 해시 값 : 해시 테이블의 Index

해싱이란?

• 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정

해시테이블의 연산

• search() - 해시테이블 내 데이터를 탐색한다.
• insert() - 해시테이블에 (값, 데이터) 추가
• delete() - 데이터 삭제

HashTable과 HashMap 차이

해시 충돌이란?

• 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우

  ( 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우)

1. 개방 주소법

• 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터 저장 ( hash와 value 1:1 유지)
• 비어 있는 공간 탐색 방법에 따른 분류
  1) 선형 탐사법 : 빈 공간을 순차적으로 탐사하는 방법
  - 충돌 발생 지점부터 이후 빈 공간을 순서대로 탐사한다.
  - 일차 군집화 문제 발생 가능!
  
  2) 제곱 탐사법 : 빈 공간을 n제곱 만큼 간격 두고 탐사
• 충돌 발생 지점부터 이후 빈공간 n제곱 간격 탐사
• 선형 탐사법과 마찬가지로, 이차 군집화 문제 발생 가능!
  
  3) 이중 해싱 : 해싱 함수를 이중으로 사용
• 해싱 함수 1) 최초 해시를 구할 때 사용
• 해싱 함수 2) 충돌 발생 시, 탐사 이동 간격 구할 때 사용
• 앞에 두 탐사법에 비해 데이터가 골고루 분포

2. 분리 연결법

• 해시 테이블을 연결 리스트로 구성
• 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case에 가까워지는 빈도를 줄일 수 있다.

해시테이블 구현

• 기본적인 해시테이블 구현 방법이다. 해시테이블을 출력할 때 Map.Entry를 통해 사용한 법을 기억해두면 좋다.

import java.util.Hashtable;
import java.util.Map;
 
public class HashTableEx {
    // 해시 함수
    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);
 
        for (Map.Entry<String, Integer> item : ht.entrySet()) {
            System.out.println(item.getKey() + " - " + item.getValue());
        }
        
        ht.remove("key1");
    }
}