[자료구조] 해시테이블

해시테이블 (HashTable) 이란?

https://blog.kakaocdn.net/dn/b1zOw1/btqL6HAW7jy/jpBA5pPkQFnfiZcPLakg00/img.png

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

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

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

 

해싱이란?

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

 

해시테이블의 연산

● search() - 해시테이블 내 데이터를 탐색한다.

● insert() - 해시테이블에 (값, 데이터) 추가

● delete() - 데이터 삭제

 

** HashTable과 HashMap 차이

	HashTable 해시테이블	HashMap 해시맵
공통점	둘 다 Map 인터페이스를 구현한 것
차이점1 : Thread-safe	O (멀티 스레드 환경에서 우수)	X (싱글 스레드 환경에서 우수)
차이점2 : Key에 Null 사용 여부	X	O

 

해시 충돌이란?

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

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

 

> 개방 주소법

- 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터 저장 ( hash와 value 1:1 유지)

- 비어 있는 공간 탐색 방법에 따른 분류 

 

1) 선형 탐사법 : 빈 공간을 순차적으로 탐사하는 방법

- 충돌 발생 지점부터 이후 빈 공간을 순서대로 탐사한다.

- 일차 군집화 문제 발생 가능!

 

2) 제곱 탐사법 : 빈 공간을 n제곱 만큼 간격 두고 탐사

- 충돌 발생 지점부터 이후 빈공간 n제곱 간격 탐사

- 선형 탐사법과 마찬가지로, 이차 군집화 문제 발생 가능!

 

3) 이중 해싱 : 해싱 함수를 이중으로 사용

- 해싱 함수 1) 최초 해시를 구할 때 사용

- 해싱 함수 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");
    }
}