자바 해시 테이블 자료구조

1. 해시와 해시 테이블 용어 정리

해시는 인덱스를 의미한다. 데이터(key + value)에서 key를 해시 함수에 넣어서, 해시(인덱스)를 얻어낸다. 얻어낸 해시(인덱스)를 배열 인덱스와 매치 하여, 데이터를 저장한다. 이렇게 데이터 중 키를 해시함수를 통해서, 인덱스를 얻어내고, 이 인덱스를 배열 인덱스에 맞춰 데이터 value를 저장하는 자료구조가 해시 테이블이다.

2. 좋은 해시 함수란?

예를 들어 데이터(key:이름, value:나이)라는 데이터로 좋은 해시 함수에 대해서 알아보자.

데이터(김민성, 16), 데이터(최선화, 33)가 있다. 이제 각 데이터의 key를 해시 함수를 얻어 인덱스 값을 얻어낸다.

하지만 이때, 김민성과 최선화의 해시 함수를 통해 얻은 인덱스 값이 같아지는 상황이 발생한다. 그럴 때 하나의 배열에 두 개의 밸류 값이 들어가는 문제가 발생한다. 배열의 1 대 1 대응 저장이 안되기 때문에, 검색과 삽입에 추가적 작동이 더 필요해진다.

즉 좋은 해시 함수란, 다양한 키 값이 해시 함수에 들어 갔을 때 겹치지 않은 인덱스를 제공하는 함수를 의미한다.

3. 해시 테이블 충돌을 대비하는 방법

해시 테이블 하나의 인덱스에 두개 이상의 데이터가 저장되었을 때, 충돌이라고 표현한다.

3-1 연결 리스트 사용, Seperate Chaning 방법

하나의 인덱스에 두개 이상의 데이터가 배정되었을 경우, 두 데이터를 연결리스트로 연결해서 저장을 한다.

그래서 검색과 삽입에 시간 복잡도가 O(1)보다 오래 걸리게 된다. 최악의 경우, 하나의 인덱스에 모든 데이터가 저장되었을 경우, 검색의 시간 O(n)이 걸리게 된다.

3-2 open Addressing 방법

인덱스가 중복 되었을 때, 해시 테이블의 빈 공간을 사용하도록 유도하는 방법

• 바로 옆에 있는 인덱스 이용하기
• 인덱스를 한번 더 해시 함수를 돌려 새로운 인덱스를 얻기

등 방법은 여러가지가 존재한다.

4. 해시의 시간 복잡도

빅오 표기법 평균 최악

탐색	O(1)	O(N)
삽입	O(1)	O(N)
삭제	O(1)	O(N)

배열의 인덱스를 사용하기 때문에, 탐색 삽입 삭제 전부 O(1)의 빠른 속로를 가진다. 그러나, 충돌이 심한 경우 최악은 O(N)까지 증가한다.

5. 자바로 LinkedList 해시 테이블 만들기

public class HashTable {
    class Node {
        String key;
        String value;
        Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    private LinkedList<Node>[] table;
    public HashTable(int size) {
        table = new LinkedList[size];
    }
    private int getHashCode(String key) {
        int hashCode = 0;
        for (char c : key.toCharArray()) {
            hashCode += (int) c;
        }
        return hashCode;
    }
    private int getIndex(int hashCode) {
        return hashCode % table.length;
    }
    private Node searchNode(int index, String key) {
        LinkedList<Node> nodes = table[index];
        for (Node node : nodes) {
            if (node.key == key) {
                return node;
            }
        }
        return null;
    }
    public void put(String key, String value) {
        int hashCode = getHashCode(key);
        int index = getIndex(hashCode);

        if (table[index] == null) {
            table[index] = new LinkedList<Node>();
            table[index].add(new Node(key, value));
        } else {
            Node searched = searchNode(index, key);
            if (searched != null) {
                searched.value = value;
            }else {
                table[index].add(new Node(key, value));
            }
        }
    }
    public String get(String key) {
        int hashCode = getHashCode(key);
        int index = getIndex(hashCode);

        Node searched = searchNode(index, key);
        if (searched == null) {
            return "null";
        }else {
            return searched.value;
        }

    }
}