[DS] Hash Table 해쉬 테이블

Introduction

해쉬 테이블 자료 구조에 대해서 알아보겠습니다.

Hash Table이란 검색하고자 하는 key 값을 입력 받아서, hash function를 이용해서 반환 받은 hash code를 배열의 index로 환산 해서 데이터에 접근하는 자료 구조 입니다.

간략하게 도식화하면 아래와 같습니다.

F(Key) ->         Hashcode ->         Index         ->        Value

"Chuck"             494               2 ex) 494 % 3

"Song"              407               2

"Kim"               289               1

"Derick"            594               0

"Rachel"            591               0

F()는 hash function이고 key는 문자열, 숫자, 파일데이터 등이 될 수 있습니다. hashcode는 정수, hashcode를 배열의 크기로 나머지 연산해서 얻은 결과가 index입니다.

그리고 각 배열은 주로 linked list 형태로 구현되며

Index

  0 -> Derick -> Rachel

  1 -> Kim

  2 -> Chuck -> Song

위와 같이 데이터가 저장되어있습니다.

Time Complexity

Hash Table은 평균적으로 검색 시간이 O(1)이지만 모든 데이터가 한 index로 몰려서 저장(Collision)되는 경우에는 한 index의 모든 데이터를 다 뒤져봐야 하기 때문에 최악의 경우에는 O(N)까지 성능이 하락할 수 있습니다. 

Hash function, Collision resolution

index에 얼마나 골고루 데이터를 할당하는지 결정하는 것이 바로 hash function의 hash algorithm이며, Collision이 일어난 경우에 이를 해결하기 위한 방법(Collision resolution)으로는 예시와 같이 배열 내부를 linked list로 구현하는 방식 외에도 여러 방식이 있습니다. 위의 예시에서는 설명의 단순화를 위해서 실제로 Hash function에서는 거의 사용하지 않는 문자열의 아스키 코드 값을 더해서 만드는 방식을 사용했습니다. 실제로 사용되는 hash function으로는 SHA 방식이 유명합니다.

Collision 발생 원인

Collision은 다른 key를 가졌지만 hash function에 의해서 같은 hashcode를 갖거나, 다른 hashcode가 생성 됐지만 나머지 연산에서 같은 index를 가지면서 생길 수 있습니다.

Code implementation - JAVA

import java.util.LinkedList;
 
class HashTable {
    class Node {
        String key;
        String value;
 
        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
 
        String value() {
            return value;
        }
 
        void value(String value) {
            this.value = value;
        }
    }
 
    LinkedList<Node>[] data;
 
    HashTable(int size) {
        data = new LinkedList[size];
    }
 
    int getHashCode(String key) {
        int hashcode = 0;
        for (char c : key.toCharArray()) {
            hashcode += c;
        }
        return hashcode;
    }
 
    int convertToIndex(int hashcode) {
        return hashcode % data.length;
    }
 
    // index로 배열을 찾은 후, 배열에 노드가 여러개 존재하는 경우 key를 이용해서 해당 노드를 찾아오는 함수
    Node searchKey(LinkedList<Node> list, String key) {
        if (list == null) return null;
        for (Node n : list) {
            if (n.key.equals(key)) {
                return n;
            }
        }
        return null;
    }
 
    // 데이터를 받아서 저장하는 함수
    void put(String key, String value) {
        int hashcode = getHashCode(key);
        int index = convertToIndex(hashcode);
        System.out.println(key + ", hashcode(" + hashcode + "), index(" + index + ")");
        LinkedList<Node> list = data[index];
        // 특정 index의 리스트가 null이면
        if (list == null) {
            list = new LinkedList<Node>();
            data[index] = list;
        }
        Node node = searchKey(list, key);
        // 특정 list의 node가 null이면
        if (node == null) {
            list.addLast(new Node(key, value));
        } else {
            node.value(value);
        }
    }
 
    // key를 가지고 데이터를 가져오는 함수
    String get(String key) {
        int hashcode = getHashCode(key);
        int index = convertToIndex(hashcode);
        LinkedList<Node> list = data[index];
        Node node = searchKey(list, key);
        return node == null ? "Not found" : node.value();
    }
}
 
public class Test {
    public static void main(String[] args) {
        HashTable h = new HashTable(3);
 
        h.put("Chuck", "he is pretty");
        h.put("Song", "she is a beautiful");
        h.put("Kim", "he is an nice");
        h.put("Derick", "he is warm");
        h.put("Rachel", "she is friendly");
        System.out.println(h.get("Chuck"));
        System.out.println(h.get("Song"));
        System.out.println(h.get("Kim"));
        System.out.println(h.get("Derick"));
        System.out.println(h.get("Rachel"));
        System.out.println(h.get("John"));
    }
}

https://github.com/ChungminPark/_problem_solving/blob/master/DS/HashTable.java

References

https://www.youtube.com/watch?v=Vi0hauJemxA

제 글이 도움이 되셨다면 간단하게 '공감', '댓글' 부탁드립니다!