해시 테이블(Hash Table)

해시 테이블(Hash Table) = 해시 맵, 해시표

• 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조
• 키를 통해 해당 데이터에 빠르게 접근 가능

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

해시 테이블 기본 구조

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

• 해시 함수(Hash function) : 키를 해시 값으로 매핑하는 연산

• 해시 값(Hash valute): 해시 테이블의 인덱스

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

해시 충돌

• 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우
• 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우

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

개방 주소법(Open Address) - 해시 충돌 해결 방법(1)

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

• hash vlaue가 1:1관계 유지

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

1) 선형 탐사법(Linear Probing)

• 빈 공간을 순차적으로 탐사하는 방법
• 충돌 발생 지점 부터 이후의 빈 공간을 순서대로 탐사

• 일차 군집화 문제 발생
• 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생

 

2) 제곱 탐사법(Quardratic Probing)

• 빈 공간을 n 제곱만큼의 간격을 두고 탐사하는 방법
• 충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사

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

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

 

3) 이중 해싱(Double Hashing)

• 해 함수(Hash Function)를 이중으로 사용
• 해시 함수 1: 최초 해시를 구할 대 사용
• 해시 함수 2: 충돌 발생 시, 탐사 간격을 구할 때 사용

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

분리 연결법(Separate Chaining) - 해시 충돌 해결 방법(2)

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

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

해시 선언/할당

Hashtable<String, Integer> ht = new Hashtable();
ht.put("key1", 10);
ht.put("key2", 20);
ht.put("key3", 30);

//출력
for(Map.Entry<String, Integer> item : ht.entrySet()){
	System.out.println(item.getKey) + "-" + item.getValue());
}

배열의 해시 충돌 세팅 방법

기본적인 Hash Table 기능 구현 Class

class MyHashTable {
    Integer[] table;
    int elemCnt; // 테이블안에 실질적으로 데이터 수 확인

    public MyHashTable() {
    }

    public MyHashTable(int size) {
        this.table = new Integer[size];
        this.elemCnt = 0;
    }

    public int getHash(int key){
        return key % 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;
        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]);
        }
        System.out.println();

    }
}

선형 탐사방법(Linear Probing)

class MyHashTable2 extends MyHashTable {

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

    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++;
    }
}

제곱 탐사법(Quadratic Probing)

class MyHashTable3 extends MyHashTable {

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

    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 = (int) (newIdx + Math.pow(2, cnt)) % this.table.length;
                if (this.table[newIdx] == null) {
                    break;
                }
                cnt++;
            }
            this.table[newIdx] = data;
        }
        this.elemCnt++;
    }
}

이중 해싱법(Double Hashing)

class MyHashTable4 extends MyHashTable {
    int c;

    MyHashTable4(int size) {
        super(size);
        this.c = this.getHashC(size);
    }

    public int getHashC(int size){
        int c = 0;
        if(size <= 2){
            return size; // 그 1~2 자체는 소수이기 때문에 바로 리턴
        }
        for(int i = size -1; i>2; i--){ // size -1 -> c가 table.length보다 작아야 하기 때문
            boolean isPrime = true;
            for(int j = 2; j<i; j++){
                if(i % j == 0){
                    isPrime = false; // 그 사이 수로 나누어 떨어지면 소수가 아니기 때문에
                    break;
                }
            }
            if(isPrime){
                c = i;
                break;
            }
        }
        return c;
    }

    public int getHash2(int key) {
        int hash = 1 + key % this.c; // c항 Hashtable보다 작으며 소수여야 한다.
        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 sis full!");
        } 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;
                if(this.table[newIdx]==null){
                    break;
                }
                cnt++;
            }
            this.table[newIdx] = data;
        }
        this.elemCnt++;

    }
}

분리 연결법(Separate 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() {
        return this.head == null;
    }

    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) {
                System.out.println("Data exist!");
                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;


    public 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();
        }
    }
}