알고리즘 공부 - 해시 테이블

해시 테이블

• 키(key), 값(value)을 대응시켜 저장하는 데이터 구조
  • 키를 통해 해당 데이터 빠르게 접근 가능
• 해싱 - 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정

구조

키 : 해시 테이블 접근을 위한 입력 값
해시 함수 : 키를 해시 값으로 매핑하는 연산
해시 값 : 해시 테이블의 인덱스
해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조

해시 충돌

• 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우
  • 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우
  • 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음

static int getHash(int key) {
    return key%5;
}
public static void main(String[] args) {
    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());
    }
    // 1 - 10 -> 1 - 60 으로 데이터 값이 수정됨
}

개방 주소법

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

 // 선형 탐사법
static int getHash(int key, int n) {
    return ((key % n) + n) % n;
}
public static void main(String[] args) {
    Hashtable<Integer, Integer> ht2 = new Hashtable<>();
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    while(ht2.size()<n) {
        int key = getHash(sc.nextInt(), n);
        int value = sc.nextInt();
        while(ht2.containsKey(key)) {
            key++;
        }
        ht2.put(getHash(key, n), value);
    }
    for (Integer i : ht2.keySet()) {
        System.out.println(i+" - "+ht2.get(i));
    }
}

// 제곱 탐사법
public static void main(String[] args) {
    Hashtable<Integer, Integer> ht2 = new Hashtable<>();
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    while(ht2.size()<n) {
        int key = getHash(sc.nextInt(), n);
        int value = sc.nextInt();
        int cnt=0;
        while(ht2.containsKey(key)) {
            key = getHash(key+(int)Math.pow(2, cnt), n);
            cnt++;
        }
        ht2.put(key, value);
    }
    for (Integer i : ht2.keySet()) {
        System.out.println(i+" - "+ht2.get(i));
    }
}

// 이중 해싱
static int getHash2(int key, int n) {
    return 1 + (key % (n - 1));
}

public static void main(String[] args) {
    Hashtable<Integer, Integer> ht2 = new Hashtable<>();
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    while (ht2.size() < n) {
        int originalKey = sc.nextInt();
        int value = sc.nextInt();
        int key = getHash(originalKey, n);
        int step = getHash2(originalKey, n);
        int cnt = 0;

        while (ht2.containsKey(key)) {
            key = getHash(originalKey + step * cnt, n);
            cnt++;
        }
        ht2.put(key, value);
    }
    for (Integer i : ht2.keySet()) {
        System.out.println(i + " - " + ht2.get(i));
    }
}

분리 연결법

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

static class Node {
    int key, data;
    Node next;
    Node() {}
    public Node(int key, int data, Node next) {
        this.key = key;
        this.data = data;
        this.next = next;
    }
}
static class LinkedList {
    Node root;

    LinkedList() {}
    LinkedList(Node node) { this.root = node; }

    boolean isEmpty() { return this.root == null; }
    void addData(int key, int data) {
        if(this.root==null) this.root = new Node(key, data, null);
        else {
            Node cur = this.root;
            while (cur.next!=null) {
                cur = cur.next;
            }
            cur.next = new Node(key, data, null);
        }
    }
    void removeData(int data) {
        if(this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }
        Node cur = this.root;
        Node pre = cur;
        while (cur!=null) {
            if (cur.key==data) {
                if (cur == this.root) this.root = cur.next;
                else pre.next = cur.next;
                break;
        }
        pre = cur;
        cur = cur.next;
        }
    }
    Integer findData(int data) {
        if(this.isEmpty()) {
            System.out.println("List is empty");
            return null;
        }

        Node cur = this.root;
        while (cur!=null) {
            if (cur.key==data) {
                System.out.println("Data exist!");
                return cur.data;
            }
            cur = cur.next;
        }
        System.out.println("Data not found!");
        return null;
    }
    void showData() {
        if (this.isEmpty()) {
            System.out.println("List is empty!");
            return;
        }

        Node cur = this.root;
        while (cur!=null) {
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}

static class MyHashTable {
    LinkedList[] table;

    MyHashTable(int size) {
        this.table = new LinkedList[size];
        for (int i = 0; i < this.table.length; i++) {
            this.table[i] = new LinkedList(null);
        }
    }

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

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

        this.table[idx].addData(key, data);
    }

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

    void removeValue(int key) {
        int idx = this.getHash(key);

        this.table[idx].removeData(key);
    }

    void printHashTable() {
        System.out.println("== Hash Table ==");
        for (int i = 0; i < this.table.length; i++) {
            System.out.print(i+" : ");
            this.table[i].showData();
        }
    }

}

public static void main(String[] args) {
    MyHashTable ht = new MyHashTable(11);
    ht.setValue(1, 10); // 1 : 10
    ht.setValue(2, 20); // 2 : 20
    ht.setValue(3, 30); // 3 : 30
    ht.printHashTable();

    ht.setValue(12, 11); // 1 : 10 11
    ht.setValue(23, 12); // 1 : 10 11 12
    ht.setValue(34, 13); // 1 : 10 11 12 13

    ht.setValue(13, 21); // 2 : 20 21
    ht.setValue(24, 22); // 2 : 20 21 22
    ht.setValue(35, 23); // 2 : 20 21 22 23

    ht.setValue(5, 1);   // 5 : 1
    ht.setValue(16, 2);  // 5 : 1 2
    ht.setValue(27, 3);  // 5 : 1 2 3
    ht.printHashTable();

    System.out.println("== key 값으로 해당 데이터 가져오기 ==");
    System.out.println(ht.getValue(1));   // 10
    System.out.println(ht.getValue(12));  // 11

    System.out.println("== 데이터 삭제 ==");
    ht.removeValue(1);  // 1 : 11 12 13
    ht.removeValue(5);  // 5 : 2 3
    ht.removeValue(16); // 5 : 3
    ht.printHashTable();
}