데이터 구조 - 5 - 해시 표

5. 해시 표
1. 개념
해시 표 는 맵 관계 가 존재 하 는 데이터 구조 로 KEY 를 지정 하면 해당 하 는 VALUE, KEY 와 VALUE 를 찾 아 Entry (또는 Node) 를 구성 할 수 있 습 니 다.
키 가 유일 해.나중에 추 가 된 Entry 가 이전의 어떤 Entry 의 KEY 와 같다 면, 새로운 VALUE 만 오래된 VALUE 로 덮어 쓰 고, 새로운 Entry 는 만 들 지 않 습 니 다.
모든 Entry 를 유지 하기 위해 배열 구 조 를 사용 할 수 있 으 며, 적 게 사용 하기 위해 같은 hashCode 값 의 KEY 에 대응 하 는 Entry 를 단 방향 링크 구조 로 유지 할 수 있 습 니 다. (성능 을 향상 시 키 기 위해 조건 을 만족 시 키 는 단 방향 링크 를 이 진 트 리 로 전환 하거나 이 진 트 리 를 단 방향 링크 로 복원 할 수 있 습 니 다)
2. 상용 방법

put 는 해시 표 에 요 소 를 추가 합 니 다 (같은 KEY 의 Entry 를 주의 하 십시오. 새로운 VALUE 는 오래된 VALUE 를 덮어 씁 니 다)

get 주어진 KEY 에 따라 대응 하 는 VALUE 찾기

remove 주어진 KEY 에 따라 대응 하 는 Entry 제거

3. 예시

class HashTable<K, V> {
    private Entry<K, V>[] table;
    private final int length;
    private int size;

    public HashTable(int length) {
        this.length = length;
        this.size = 0;
    }

    public void put(K key, V value) {
        if (null == key || null == value) {
            throw new NullPointerException();
        }

        if (null == table) {
            @SuppressWarnings("unchecked")
            Entry<K, V>[] table = (Entry<K, V>[])new Entry[this.length];
            this.table = table;
        }

        int hash = hash(key);
        Entry<K, V> entry = table[hash];
        while (null != entry) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
            entry = entry.prev;
        }

        entry = table[hash];
        Entry<K, V> put = new Entry<K, V>(key, value);
        table[hash] = put;
        put.prev = entry;

        this.size++;
    }

    public V get(K key) {
        if (null == key) {
            throw new NullPointerException();
        }

        int hash = hash(key);
        Entry<K, V> entry = table[hash];
        while (null != entry) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.prev;
        }

        return null;
    }

    public boolean remove(K key) {
        if (null == key) {
            throw new NullPointerException();
        }

        int hash = hash(key);
        Entry<K, V> entry = table[hash];
        boolean first = true;
        Entry<K, V> next = table[hash];
        while (null != entry) {
            if (entry.key.equals(key)) {
                if (first) {
                    table[hash] = entry.prev;
                } else {
                    next.prev = entry.prev;
                }

                this.size--;
                return true;
            }

            entry = entry.prev;
            if (first) {
                first = false;
            } else {
                next = next.prev;
            }
        }

        return false;
    }

    public int size() {
        return this.size;
    }

    private int hash(K key) {
        return key.hashCode() % this.length;
    }

    private static class Entry<K, V> {
        private final K key;
        private V value;
        private Entry<K, V> prev;

        private Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return this.key + "=" + this.value;
        }
    }

    @Override
    public String toString() {
        if (null == table) {
            return "{}";
        }

        StringBuilder sBuilder = new StringBuilder("{");
        for (int i = 0; i < this.length; i++) {
            Entry<K, V> entry = table[i];
            while (null != entry) {
                sBuilder.append(entry.toString()).append(',').append(' ');
                entry = entry.prev;
            }
        }

        return sBuilder.substring(0, sBuilder.length() - 2) + '}';
    }

}