[DataStructure] 해쉬 테이블(HashTable)이란 feat. Java

이전에 해쉬란 무엇인가에 대해서 정리를 하였지만,

또 정리를 더 자세하게 해보고 이번 포스팅에서는 직접 기능까지 구현해보자

https://superohinsung.tistory.com/113

[Algorithm] Hash(해시) 란

 

해쉬 테이블 이란

키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조이다. 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산할수 있으며,  Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빠르다.

미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색 지원한다.

 

미리 알면 좋은 용어들

해쉬 함수(Hash Function): 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

해쉬 (Hash), 해쉬 값(Hash Value), 또는 해쉬 주소(Hash Address): 해싱 함수를 통해 리턴된 고정된 길이의 값

해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

슬롯(Slot): 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간

 

해쉬 테이블의 장단점과 주요 용도

장점

• 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
• 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽다.

단점

• 일반적으로 저장공간이 좀 더 많이 필요하다.
• 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.

주요 용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐쉬 구현시 (중복 확인 쉽기 때문에)

 

충돌(Collision) 해결 알고리즘 

해쉬테이블의 가장 큰 문제는 충돌(Collision)의 경우이다. 이 문제를 충돌(Collision) 또는 해쉬 충돌(Hash Collision)이라고 부른다.

 

Chaining 기법

개방 해싱 또는 Open Hashing 기법 중 하나 : 해쉬 테이블 저장공간 외의 공간을 활용하는 기법

충돌이 일어나면, 링크드 리스트라는 자료구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법이다.

    
    public boolean put(String key, String value) {
        Integer index = this.hashFunc(key);
        if (this.hashTable[index] != null) {
            HashEntry findEntry = this.hashTable[index];
            HashEntry prevEntry = this.hashTable[index];
            while (findEntry != null) {
                if (findEntry.key.equals(key)) {
                    findEntry.value = value;
                    return true;
                } else {
                    prevEntry = findEntry;
                    findEntry = findEntry.next;
                }
            }
            prevEntry.next = new HashEntry(key, value);
        } else {
            this.hashTable[index] = new HashEntry(key, value);
        }
        return true;
    }

 

Linear Probing 기법

폐쇄 해싱 또는 Close Hashing 기법 중 하나 : 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법

충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장하는 기법 -> 저장공간의 활용도를 높이기 위한 기법

    public boolean put(String key, String value) {
        Integer index = this.hashFunc(key);
        if (this.hashTable[index] != null) {
            if (this.hashTable[index].key.equals(key)) {
                this.hashTable[index].value = value;
                return true;
            } else {
                Integer currIndex = index + 1;
                while (currIndex < this.hashTable.length && this.hashTable[currIndex] != null) {
                    if (this.hashTable[currIndex].key.equals(key)) {
                        this.hashTable[currIndex].value = value;
                        return true;
                    } else {
                        currIndex++;
                    }
                }
                if (currIndex < this.hashTable.length) {
                    this.hashTable[currIndex] = new Entry(key, value);
                    return true;
                } else {
                    return false;
                }
            }
        } else {
            this.hashTable[index] = new Entry(key, value);
            return true;
        }
    }

 

빈번한 충돌을 개선하는 기법

해쉬테이블 저장공간을 확대및 해쉬 함수 재정의한다.

 

예를 들어서

String name = "Dave";
int key = 0;
for (int i = 0; i < name.length(); i++) {
    key += name.charAt(i);
}

(int)(key) % 200

이런식으로 재정의한다.

 

시간 복잡도

• 일반적인 경우 (Collision이 없는 경우) O(1)
• 최악의 경우 (Collision이 모두 발생하는 경우)는 O(n)
• Linear Probing, Chaining 기법 둘 다 동일

 

검색에서 해쉬 테이블의 사용 예

• 배열에서 데이터를 저장하고, 검색할 때 O(n)
• 이상적인 해쉬 테이블 케이스에서 데이터를 검색할 때 O(1)

 

Java HashMap

해쉬 테이블 구조를 활용하여 구현된 JAVA Collection Framewor에 속한 클래스이다.

import java.util.HashMap;

HashMap<Integer, String> map1 = new HashMap();
map1.put(1, "사과");
map1.put(2, "바나나");
map1.put(3, "포도");

HashMap<String, String> map2 = new HashMap();
map2.put("DaveLee", "01033334444");
map2.put("Dave", "01032221111");
map2.put("David", "0104445555");