[자료구조] 해시 테이블

해시 테이블

 

• Key, Value을 대응시켜 저장하는 데이터 구조
• 해싱 : Key를 특정 계산식(Hash function)에 넣어 나온 결과를 사용해 값에 접근하는 과정
• 해시 충돌 : 해시 테이이블의 같은 공간에 서로 다른 값을 저장하려는 경우

 

 

 

1. 개방 주소법

 

• 해시 충돌 시, 테이블에 비어 있는 공간의 해시를 찾아 데이터를 저장
• 선형 탐사법 : 빈 공간을 순차적으로 탐사하는 방법, 일차 군집화 문제 발생

public void setValue(int key, int data) {
        int idx = this.getHash(key);

        if (this.elemCnt == this.table.length) {
            System.out.println("full");
        } else if (this.table[idx] == null) {
            this.table[idx] = data;
        } else {
            int newIdx = idx;
            while (true) {
                newIdx = (idx + 1) % this.table.length;
                if (this.table[newIdx] == null) {
                    break;
                }
            }
            this.table[newIdx] = data;
        }
        
        elemCnt++;
    }

• 제곱 탐사법 : 빈 공간을 n 제곱만큼 간격으로 탐사하는 방법, 이차 군집화 문제 발생

public void setValue(int key, int data) {
        int idx = this.getHash(key);

        if (this.elemCnt == this.table.length) {
            System.out.println("Hash table is full!");
            return;
        } else if (this.table[idx] == null) {
            this.table[idx] = data;
        } else {
            int newIdx = idx;
            int cnt = 0;
            while (true) {
                newIdx = (newIdx + (int)Math.pow(2, cnt)) % this.table.length;
                if (this.table[newIdx] == null) {
                    break;
                }
                cnt++;
            }
            this.table[newIdx] = data;
        }

        elemCnt++;
}

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

public int getHash2(int key) {
        int hash = 1 + key % this.c; // c는 사이즈보다 작은 소수 값 
        return hash;
}

public void setValue(int key, int data) {
        int idx = this.getHash(key);

        if (this.elemCnt == this.table.length) {
            System.out.println("Hash table is full!");
            return;
        } else if (this.table[idx] == null) {
            this.table[idx] = data;
        } else {
            int newIdx = idx;
            int cnt = 1;
            while (true) {
                newIdx = (newIdx + this.getHash2(newIdx) * cnt) % this.table.length;
            }
        }

        elemCnt++;
}

 

 

2. 분리 연결법

 

• 해시 테이블을 연결 리스트로 구성

 

 

 

 

 

---

 

 

 

 

 

해시 테이블 클래스

 

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

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

        ht.put("key1", 1);
        ht.put("key2", 2);
        ht.put("key3", 3);
        for (Map.Entry<String, Integer> item: ht.entrySet())
            System.out.println(item.getKey() + ", " + item.getValue());

        System.out.println(ht.get("key1"));

        ht.remove("key1");
        for (Map.Entry<String, Integer> item: ht.entrySet())
            System.out.println(item.getKey() + ", " + item.getValue());
 }

 

	Hashtable	HashMap
Thread	멀티 스레드 환경에서 우수	싱글 스레드 환경에서 우수
Key에 null 사용 여부	O	X