해시 테이블_1

해시 테이블(Hash Table)

= 해시 맵, 해시 표

 

- 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조

: 키를 통해 해당 데이터에 빠르게 접근 가능

 

- 해싱

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

---

해시 테이블 구조

키

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

 

해시 함수

: 키를 해시 값으로 매핑하는 연산

 

해시 값

: 해시 테이블의 인덱스

 

해시 테이블

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

---

해시 충돌

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

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

 

- 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음

---

해시 충돌 해결 방법

 

▶ 개방 주소법(Open Address)

- 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장

- hash와 value가 1:1 관계 유지

- 비어 있는 공간 탐색 방법에 따라 분류 (선형 탐사법, 제곱 탐사법, 이중 해싱)

 

선형 탐사법

- Linear Probing

- 빈 공간을 순차적으로 탐사하는 방법

: 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사

- 일차 군집화 문제 발생

: 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생

 

제곱 탐사법

- Quadratic Probing

- 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법

: 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사

- 일차 군집화 문제 일부 보완

- 이차 군집화 문제 발생 가능

 

이중 해싱

- Double Hashing

- 해싱 함수를 이중으로 사용

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

   - 해시 함수 2: 충돌 발생 시, 탐사 이동 간격을 구할 때 사용

- 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨

 

▶ 분리 연결법(Separate Chaining)

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

- 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결

---

실습 코드

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

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

public class Main {
    // 해시 함수
    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); // 해당 키에 대한 데이터가 50으로 바뀜(충돌)

        for (Map.Entry<String, Integer> item: ht.entrySet()) {
            // 해시테이블 안에 있는 키 값 대응되는 데이터의 entry를 쭉 뽑아주는데
            // for문에서 받기 위해 타입을 맞춰준 것. Hashtable은 Map 인터페이스를 통해서 만들어내기 때문에
            // Map.Entry<String, Integer> 형태로 받아줄 수 있음
            System.out.println(item.getKey() + " - " + item.getValue());
        }

        // 해시 충돌 케이스 (해시 함수 사용)
        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);

        System.out.println("== 충돌 전 ==");
        for (Map.Entry<Integer, Integer> item: ht2.entrySet()) {
            System.out.println(item.getKey() + " - " + item.getValue());
        }

        System.out.println("== 충돌 후 ==");
        ht2.put(getHash(6), 60);
        for (Map.Entry<Integer, Integer> item: ht2.entrySet()) {
            System.out.println(item.getKey() + " - " + item.getValue());
        }
    }
}

 

자바에서 Map.Entry는 Map 형태의 인터페이스를 만드는데 사용하는데

실제 사용은 실습 코드와 같이 Map을 for문에서 돌려줄 경우 인터페이스 용도로 사용하거나

혹은 스트림(Stream) 사용 시 Map 형식의 데이터에서 처리가 필요할 때 Map.Entry를 사용하여 처리하게 된다.

---

연습 코드1

// Practice1
// 해시 테이블 배열로 직접 구현

class MyHashTable {

    Integer[] table;
    // 해시테이블 안에 실질적으로 데이터가 몇 개 들어가있는지 확인하기 위한 변수 선언
    int elemCnt;

    // 기본 생성자
    MyHashTable() {}
    MyHashTable(int size) {
        this.table = new Integer[size];
        this.elemCnt = 0;
    }

    public int getHash(int key) {
        return key % this.table.length;
    }

    public void setValue(int key, int data) {
        int idx = this.getHash(key);
        this.table[idx] = data;
        this.elemCnt++;
    }

    public int getValue(int key) {
        int idx = this.getHash(key);
        return this.table[idx];
    }

    // 데이터 지우는 상황
    public void removeValue(int key) {
        int idx = this.getHash(key);
        this.table[idx] = null; // 해시에 해당하는 데이터 null로 바꿔줌
        this.elemCnt--;
    }

    // 해시테이블 출력하는 부분
    public void printHashTable() {
        System.out.println("== Hash Table ==");
        for (int i = 0; i < this.table.length; i++) {
            System.out.println(i + ": " + this.table[i]);
        }
    }
}

public class Practice1 {

    public static void main(String[] args) {
        // Test code
        MyHashTable ht = new MyHashTable(7);
        ht.setValue(1, 1);
        ht.setValue(2, 2);
        ht.setValue(3, 3);
        ht.setValue(4, 4);
        ht.setValue(5, 5);
        ht.printHashTable();
        ht.setValue(8, 6); // 8을 7로 나눈 나머지 1(key), data 6 = 해시 충돌 발생
        ht.printHashTable();
    }
}

---

 연습 코드2

// Practice2
// 해시 충돌 해결 - 개방 주소법 (선형 탐사법)

class MyHashTable2 extends MyHashTable { // MyHashTable을 상속받아서


    MyHashTable2(int size) {
        super(size);
    }

    // setValue 쪽을 오버라이딩해서 구현을 할 것임
    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;
            while (true) { // 선형 탐사 - 순차적으로 증가시키면서 빈 공간 찾기
                newIdx = (newIdx + 1) % this.table.length;
                if (this.table[newIdx] == null) {
                    break;
                }
            }
            this.table[newIdx] = data;
        }
        elemCnt++;
    }
}

public class Practice2 {
    public static void main(String[] args) {
        // Test code
        MyHashTable2 ht = new MyHashTable2(5);
        ht.setValue(1, 1);
        ht.setValue(3, 3);
        ht.printHashTable();

        ht.setValue(1, 10);
        ht.printHashTable();

        ht.setValue(1, 20);
        ht.setValue(1, 30);
        ht.setValue(1, 40);
        ht.printHashTable();
    }
}