HashTable

• 키(Key) - 값(value)를 대응시켜 저장

• 키(Key) 를 통해 해당데이터에 빠른 접근 가능

Key	Value
이름	홍길동
나이	19
성별	남

해시 함수를 사용하여 키의 해시코드를 계산하고 이를 이용해 배열의 인덱스를 결정하여 값을 저장한다.

해싱 (Hashing)

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

구조

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

---

해시 충돌

해시테이블의 같은 공간에 서로다른 값을 저장하려는 경우 (서로다른 키의 해시값이 동일한 경우) 해시 충돌이 발생

해시충돌 해결법

개방주소법 (Open Addressing)

• 포인터가 필요없고, 지정한 메모리외 추가적인 저장공간도 필요X
• 삽입, 삭제시 오버헤드가 적다
• 저장할 데이터가 적을때 더 유리하다

선형 탐사법 (Linear Probing)

• 해시 충돌시 충돌지점 이후의 가장 가까운 빈 공간을 찾아 저장
• 일차 군집화 문제

제곱 탐사법 (Quadratic Probing)

• 충돌 지점 이후의 빈 공간을 제곱만큼 건너뜀
• 이차 군집화 문제 가능성

이중 해싱 (Double Hashing)

• 다른 해시함수를 한번 더 적용한 결과를 이용
• 최초해시를 구할 때 해싱하고, 충돌이 발생할 때 해싱을 한번 실행
• 선형, 제곱 탐사법 보다 고르게 분포

분리 연결법 (Seperate Chaining)

• 해시 테이블을 연결리스트로 구성
• 충돌시 테이블 내의 다른 위치가 아닌 연결 리스트에 해당하는 다른 테이블에 데이터 연결
• 비교적 데이터가 많아도 선형적으로 성능저하가 나타나 개방주소법에 비해 유리하다

class Node {
    int key;
    int data;
    Node next;

    Node() {}
    Node(int key, int data, Node next) {
        this.key = key;
        this.data = data;
        this.next = next;
    }
}

class LinkedList {
    Node head;

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

    public boolean isEmpty() {
        if (this.head == null) {
            return true;
        }
        return false;
    }

    public void addData(int key, int data) {
        if (this.head == null) {
            this.head = new Node(key, data, null);
        } else {
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new Node(key, data, null);
        }
    }

    public void removeData(int data) {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = this.head;
        Node pre = cur;
        while (cur != null) {
            if (cur.key == data) {
                if (cur == this.head) {
                    this.head = cur.next;
                } else {
                    pre.next = cur.next;
                }
                break;
            }

            pre = cur;
            cur = cur.next;
        }
    }

    public Integer findData(int key) {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return null;
        }

        Node cur = this.head;
        while (cur != null) {
            if (cur.key == key) {
                return cur.data;
            }
            cur = cur.next;
        }
        System.out.println("Data not found!");
        return null;
    }

    public void showData() {
        if (this.isEmpty()) {
            System.out.println("List is empty!");
            return;
        }

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

class MyHashTable5 {
    LinkedList[] table;

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

    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].addData(key, data);
    }

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

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

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

    public 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 class Practice5 {
    public static void main(String[] args) {
        // Test code
        MyHashTable5 ht = new MyHashTable5(11);
        ht.setValue(1, 10);
        ht.setValue(2, 20);
        ht.setValue(3, 30);
        ht.printHashTable();
        ht.setValue(12, 11);
        ht.setValue(23, 12);
        ht.setValue(34, 13);

        ht.setValue(13, 21);
        ht.setValue(24, 22);
        ht.setValue(35, 23);

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

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

        System.out.println("== 데이터 삭제 ==");
        ht.removeValue(1);
        ht.removeValue(5);
        ht.removeValue(16);
        ht.printHashTable();
    }
}

---

HashMap

HashTable은 레거시로써 속도가 느려 잘 사용하지 않고 주로 HashMap을 사용한다.

vs HashTable

Key에 Null 사용여부

• Hashtable: X
• HashMap: O

Thread-safe

멀티 스레드 환경에서 여러 스레드로 동시 처리를 하게 될 때, 어떤 스레드에서의 변수가 다른 스레드에서 처리하는 변수에 의해 영향을 받는일이 없는 것을 Thread-safe 라고 한다.

• Hashtable: O (멀티 스레드 환경에서 우수)
• HashMap: X (싱글 스레드 환경에서 우수)

HashMap을 보완할수는 없나?

sychronizedMap, ConcurrentMap을 사용하면 Thread-safe 하게 사용할 수 있다.

성능

• 일반적으로 검색, 삽입 삭제가 $O(1)$로 빠름
• 최악의 경우 충돌 발생으로 $O(N)$

메소드

• put(key, value) : 입력
• get(key) : 출력
• remove(key) : 제거
• containsKey(key) : 키가 있는지 확인
• containsKey(value) : 값이 있는지 확인