해시 테이블

1. 해시 테이블 정의

=해시 맵=해시 표

해싱이란, 키를 특정 계산식 (function)에 넣어 나온 결과를 사용하여 값에 접근하는 과정이다. 해시 테이블은 해싱을 통해 키, 값을 대응시켜 저장하는 데이터 구조이다.

2. 해시 테이블 기본 구조

키: 해시 테이블 접근을 위한 입력 값

해시 함수: 키를 해시 값으로 매핑하는 연산; 해시 함수는 골고루 값을 분포시켜야 좋은 해쉬 연산이 가능하다

해시 값: 해시 테이블의 인덱스

해시 테이블: 키-값을 연관시켜 저장하는 데이터 구

3. 충돌

해쉬 충돌이란?

다른 키가 해쉬 함수에 넣었을 때 같은 위치를 가르키는 것이다.

충돌 하도록 내버려 둔다면, 충돌 전의 데이터는 삭제되고 충돌시킨 데이터가 그 자리를 차지한다.

해결법 1: 개방 주소법 (open address)

hash 와 value의 1:1 대응관계를 유지시키는 방법으로, 충돌 시 테이블의 빈 공간을 찾아 데이터를 저장한다. 비어있는 공간을 어떻게 찾는지에 따라 분류된다.

선형 탐사법
충돌 발생시 다른 빈자리를 충돌발생 지점부터 순서대로 탐사
단점: 일차 군집화

제곱 탐사법
충돌 발생 시 n제곱 간격으로 탐사 (2^0, 2^1, 2^2...)
단점: 2차 군집화

이중 해싱
층돌 발생 시 2번째 해시 함수 사용해 빈공간을 찾아감

해결법 2: 분리 연결법 (separate chaining)

hash 와 value의 1:1 대응을 포기하는 방법으로, 충돌시 연결리스크로 해당 테이블에 데이터 연결한다. (단, 1:1 대응이 더 이상 아니여서, 연결리스트가 길어질수록 찾는 시간 느려진다.)

해시 사용

// 선형 자료구조 - 해시 테이블

import java.util.Hashtable;
import java.util.Map;

public class Main {
    public static int getHash(int key) {  
        return 원하는계산식넣기; 
    }

    public static void main(String[] args) {
        Hashtable<String, Integer> ht = new Hashtable();
                 //<키, 데이터>
    }
}

일부 메소드

put()
get(), getValue(), getKey()
remove()
entrySet()