[Data Structure] Hash(해쉬)

1. Hash Table 구조

Hash Table 은 Associative(연관) 방법으로 데이터를 저장하는 자료 구조로 Cache 구현 시 사용하기도 한다.

Array 형태로 데이터를 저장하며, 각 데이터 값은 Unique 한 Index 를 갖는다.

 

- 장점 -

• 원하는 데이터의 Index 만 알고 있다면, 데이터의 접근이 매우 빠름
• 데이터의 크기와 상관없이 삽입과 검색의 행위가 매우 빠른 자료 구조
• Key 에 대한 데이터가 있는지(중복) 확인이 쉬움

- 단점 -

• 일반적으로 저장 공간이 많이 필요
• 여러 키에 해당하는 주소가 동일할 경우 Collision(충돌)을 해결하기 위한 별도의 방안이 필요

Hash Table 저장 구조

Hashing 은 Key Value 범위를 Array 의 Index 범위로 변환하는 기술을 말한다.

Modulo 연산을 사용해 Key 값의 범위를 얻는다.

예를 들어 Hash Table 의 크기가 20이라면, 다음과 같이 항목이 저장된다.

Serial Number	Key	Hash	Array Index
1	1	1 % 20 = 1	1
2	2	2 % 30 = 2	2
3	42	42 % 20 = 2	2
4	4	4 % 20 = 4	4
5	12	12 % 20 = 12	12
6	14	14 % 20 = 14	14
7	17	17 % 20 = 17	17
8	13	13 % 20 = 13	13
9	37	37 % 20 =17	17

2. Linear Probing

위의 표를 보다 보면, 무엇인가 이상한 점을 느꼈을 것이다.

Index 의 값이 겹치는 부분이 존재한다.

이런 경우를 Collision(충돌) 이라고 하며, 이런 문제를 해결하는 방법 중 하나가 Linear Probing 이다.

Linear Probing 은 빈 칸을 찾을 때까지 다음 칸을 조사하여 Array 의 다음 빈 위치를 검색할 수 있다.

Serial Number	Key	Hash	Array Index	After Linear Probing, Array Index
1	1	1 % 20 = 1	1	1
2	2	2 % 30 = 2	2	2
3	42	42 % 20 = 2	2	3
4	4	4 % 20 = 4	4	4
5	12	12 % 20 = 12	12	12
6	14	14 % 20 = 14	14	14
7	17	17 % 20 = 17	17	17
8	13	13 % 20 = 13	13	13
9	37	37 % 20 =17	17	18

또 다른 Collision 의 해결 방법으로, Linked List 를 사용해 데이터를 추가로 뒤에 연결시켜 저장하는 방법도 있다.

3. 시간 복잡도

• Collision 이 없는 경우 O(1)
• Collision 이 모두 발생하는 경우 O(n)
• Linear Probing, Chaning 기법 모두 동일

4. Example

public class HashTable {

    public Slot[] hashTable;

    public HashTable(Integer size) {
        this.hashTable = new Slot[size];
    }

    public static class Slot {
        String key;
        String value;

        Slot(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    public int hash(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }

    public void saveData(String key, String value) {
        int address = this.hash(key);

        if (this.hashTable[address] != null) {
            if (Objects.equals(this.hashTable[address].key, key)) {
                this.hashTable[address].value = value;
            } else {
                int curAddress = address + 1;
                while (this.hashTable[curAddress] != null) {
                    if (Objects.equals(this.hashTable[curAddress].key, key)) {
                        this.hashTable[curAddress].value = value;
                        return;
                    } else {
                        curAddress++;
                        if (curAddress >= this.hashTable.length) {
                            return;
                        }
                    }
                }
                this.hashTable[curAddress] = new Slot(key, value);
            }
        } else {
            this.hashTable[address] = new Slot(key, value);
        }
    }

    public String getData(String key) {
        int address = this.hash(key);
        if (this.hashTable[address] != null) {
            if (Objects.equals(this.hashTable[address].key, key)) {
                return this.hashTable[address].value;
            } else {
                int currAddress = address + 1;
                while (this.hashTable[currAddress] != null) {
                    if (Objects.equals(this.hashTable[currAddress].key, key)) {
                        return this.hashTable[currAddress].value;
                    } else {
                        currAddress++;
                        if (currAddress >= this.hashTable.length) {
                            return null;
                        }
                    }
                }
                return null;
            }
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        HashTable hashTable = new HashTable(20);

        hashTable.saveData("Dohyun", "2313");
        hashTable.saveData("Seohui", "1986");
        hashTable.saveData("Sooyeon", "1234");

        System.out.println(hashTable.getData("Dohyun"));
        System.out.println(hashTable.getData("Seohui"));
        System.out.println(hashTable.getData("Sooyeon"));
    }
}

- 끝 -