해시 테이블

1. 해시검색은 어떻게 할까?

해시 테이블에서 데이터를 저장하고 검색할때 어떻게 찾는지 오늘 공부해보았습니다.
알고리즘이나 암호화쪽을 공부할 때 가장 많이 들었던 용어가 해시코드였는데 해시코드란 어떤 본문의 길이와 상관없이 일정한 크기의 해시 값을 의미합니다. 따라서 원문에서 공백이나 점 하나라도 다르다면 해시 값이 다르기 때문에 이 방법으로 비교를 통해서 빠르게 검색할 수 있다는 장점이 있습니다. 실제로 블록체인에서 모든 고객의 장부를 비교할 때 해시 값으로 비교를 한다고 합니다.

해시검색은 왜 속도가 빠를까요? 그건 데이터를 저장할 때 해시 알고리즘을 통해서 해시 값을 얻은 후에 데이터를 저장할 수 있는 배열의 크기 값을 나눈 몫으로 인덱스를 구하고 그 인덱스를 해당 데이터를 저장할 인덱스로 사용하기 때문입니다.
따라서 특정 key를 가지고 검색을 하게 된다면 해시 값을 통해서 인덱스를 찾아내서 바로 접근하기 때문에 검색 속도가 빠를 수 밖에 없습니다.

하지만 어떤 해시 알고리즘을 쓰느냐에 따라서 성능이 달라질 수 있습니다. 만약 동일한 인덱스로 데이터를 저장하게 된다면 collision(해시 충돌)이 발생할 수 있는데요 이 것은 저장되는 문자의 경우의 수가 무한한것에 비해서 해시코드는 정수개 만큼 존재하기 때문에 한정적입니다.

위의 그림을 보면 만약 해시 값을 통해서 배열의 특정 인덱스 부분만 데이터가 저장된다면 메모리의 공간이 낭비되는 비효율적인 문제가 발생할 수 있습니다.
따라서 어떤 해시 알고리즘을 사용하느냐에 따라서 충돌을 최소화하는 것이 중요합니다.

간단하게 문자열 데이터를 저장할 때 각각 문자에 해당되는 아스키 코드 값으로 해시코드를 추출하는 알고리즘을 구현하여 데이터를 저장하는 예제를 살펴보겠습니다.

2. 해시 테이블 예제 코드

import java.util.LinkedList;

public class HashTable {

    class Node {
        String key;
        String value;
        // 실제 데이터(key, value)를 가지고 있는 Node 객체
        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

        public String getValue() {
            return value;
        }

        public void setValue(String value) {
            this.value = value;
        }
    }
    // 실제 Node 객체를 가진 LinkedList 배열 참조변수 선언 
    LinkedList<Node>[] data;

    public HashTable(int size) {

        this.data = new LinkedList[size];
    }
    // 검색할 문자열을 아스키 코드를 이용하여 해시 값 추출
    private int getHashCode(String key) {
        int hashcode = 0;
        for (char c : key.toCharArray()) {
            hashcode += c;
        }
        return hashcode;
    }
    // 해시코드를 이용하여 인덱스를 찾기
    private int convertToIndex(int hashcode) {
        return hashcode % data.length;
    }
    // 데이터 검색
    private Node searchKey(LinkedList<Node> list ,String key){

        if(list == null) return null;
        for (Node node : list){
            if(node.key.equals(key)){
                return node;
            }
        }
        return null;
    }
    // 데이터 저장
    public void put(String key, String value){

        int hashcode = getHashCode(key);
        int index = convertToIndex(hashcode);
        LinkedList<Node> list = data[index];

        if(list == null){
            list = new LinkedList<>();
            data[index] = list;
        }

        Node node = searchKey(list, key);
        
        // Node가 null이면 새로운 Node 객체 생성
        if(node == null){
            list.addLast(new Node(key, value));
        }else {
            // 이미 존재한다면 key에 해당하는 value를 오버라이드 합니다.
            node.setValue(value);
        }
    }

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

위의 해시 테이블의 코드를 살펴보면 inner class로 Node 클래스를 정의하였는데 실제 key, value를 가지고 있는 객체입니다. 실제 데이터를 저장하거나 검색할 때 해시코드를 구해야하는데 저는 아스키 코드를 이용하여 해시 값을 생성하였습니다.

private int getHashCode(String key) {
    int hashcode = 0;
    for (char c : key.toCharArray()) {
        hashcode += c;
    }
    return hashcode;
}

"sung" 라는 문자열 데이터를 저장하거나 검색한다면 아스키 코드 값을 구하면 445라는 해시코드가 생성됩니다.

private int convertToIndex(int hashcode) {
    return hashcode % data.length;
}

해시코드를 이용하여 리스트의 몇번째 인덱스에 데이터를 저장할지 찾기 위해서 인덱스를 구하는 메소드입니다.

public class HashTest {

    public static void main(String[] args) {

        HashTable hashTable = new HashTable(3);

        hashTable.put("junyoung", "is genius");
        hashTable.put("pomeranian", "is my first friend");
        hashTable.put("siba", "is my second friend");
        hashTable.put("siberian", "is my third friend");

        System.out.println(hashTable.get("junyoung"));
        System.out.println(hashTable.get("pomeranian"));
        System.out.println(hashTable.get("pomeranian"));
        System.out.println(hashTable.get("siba"));
        System.out.println(hashTable.get("siberian"));
    }
}

실제 실행을 해보면 LinkedList에 저장된 Node 객체의 key 값과 비교하여 일치하면 Node 객체의 value 값을 리턴하고, 없을 경우에는 "Not Found" 문자열을 리턴하도록 구현하였습니다.

간단하게 해시 테이블의 사용방법에 대해서 예제 코드를 작성해봤는데요. 실제로 다양한 해시 알고리즘이 있기 때문에 프로젝트 특성에 맞게 유연하게 잘 선택해서 사용해야 할 것 같습니다.