Java - 간단한 HashTable 구현

javaexamples

Java는 HashMap을 지원하기 떄문에 HashTable을 구현할 필요가 없습니다. 하지만 알고리즘의 동작 원리를 알고 싶거나, 알고리즘 시험에서 라이브러리를 사용하지 못하게 한다면 직접 구현해야 합니다.

HashTable을 만드는 방법은 매우 다양하고, 방법에 따라서 성능이 다릅니다. 이 글에서는 매우 간단히 만들 수 있는 HashTable을 Java로 구현해보았습니다.

HashTable

HashTable은 (key, value)의 데이터를 Table에 저장하는 것을 말합니다. O(1)에 데이터를 저장하거나 찾을 수 있을 정도로 매우 빠른 속도를 보장합니다. 이런 속도를 가능하게 하는 것은 key를 hash로 변경하기 때문입니다.

서로 다른 key가 동일한 hash를 갖을 수 있기 때문에 이럴 때 어떻게 처리하냐에 따라서 소비하는 메모리와 탐색하는데 걸리는 시간 차이가 발생합니다.

이 글에서 구현한 방법은 동일한 hash를 갖고 있는 데이터를 저장할 때, 이미 저장된 값이 있으면 hash + 1으로 다음 테이블에 저장할 수 있는지 시도합니다. 여기서 Linked List처럼 Chain 방식을 적용하면 좋겠지만, 중복된 hash가 적을 것이라고 생각된다면 hash + 1과 같은 방식으로 구현해도 성능 차이는 크지 않을 것 같습니다.

Example

아래 코드는 간단히 구현한 HashTable 예제입니다.

다음 메소드를 제공합니다.

  • get(key)
  • put(key, value)
  • remove(key)
  • size()
  • toString()
public static class Item {
    public String key;
    public Object value;

    public Item(String key, Object value) {
        this.key = key;
        this.value = value;
    }
}

public static class HashTable {
    private static int HASH_TABLE_CAPACITY = 1000;
    private Item[] data = new Item[HASH_TABLE_CAPACITY];
    private int size = 0;

    private int getHash(String key) {
        int hash = 0;
        for (int i = 0; i < key.length(); i++) {
            char val = key.charAt(i);
            hash = (hash + val*(i + 1)) % HASH_TABLE_CAPACITY;
        }
        return hash;
    }

    public Object get(String key) {
        if (key != null) {
            int hash = getHash(key);
            while (data[hash] != null && !data[hash].key.equals(key)) {
                hash = (hash + 1) % HASH_TABLE_CAPACITY;
            }
            return data[hash] != null ? data[hash].value : null;
        }
        return null;
    }

    public void put(String key, Object value) {
        if (key != null) {
            int hash = getHash(key);
            while (data[hash] != null && !data[hash].key.equals(key)) {
                hash = (hash + 1) % HASH_TABLE_CAPACITY;
            }
            data[hash] = new Item(key, value);
            size++;
        }
    }

    public Object remove(String key) {
        Object removed = null;
        if (key != null) {
            int hash = getHash(key);
            while (data[hash] != null && !data[hash].key.equals(key)) {
                hash = (hash + 1) % HASH_TABLE_CAPACITY;
            }
            if (data[hash] != null) {
                removed = data[hash];
                data[hash] = null;
                size--;
            }
        }
        return removed;
    }

    public int size() {
        return size;
    }

    public String toString() {
        String out = "<HashTable>\n";
        for (int i = 0; i < data.length; i++) {
            Item item = data[i];
            if (item != null) {
                out += "  Key(hash, index): " + data[i].key
                        + "(" + getHash(data[i].key) + ", " + i + ")"
                        + ", Value: " + data[i].value + "\n";
            }
        }
        return out;
    }
}
  • Table의 배열 크기는 1000으로 설정하였습니다. 크기를 인자로 전달받아 동적으로 배열 크기를 조절하도록 구현할 수도 있습니다.
  • 매우 간단히 구현하기 위해 Generics를 사용하지 않고 Object를 저장하도록 하였습니다.
  • null은 key로 허용되지 않도록 구현하였습니다.
  • String의 hash를 계산할 때, String.hashCode()를 사용하지 않고 직접 구현하였습니다. ASCII에 문자열 인덱스를 곱하고 그것의 합을 테이블 크기로 나눠주었습니다. 더 복잡한 알고리즘을 적용하면 hash가 충돌될 가능성이 줄어들 것 같습니다.

실행

다음과 같이 구현한 HashTable이 잘 동작하는지 확인해보았습니다.

HashTable hashTable = new HashTable();

hashTable.put("Tokyo", "Japan");
hashTable.put("Seoul", "Korea");
hashTable.put("Beijing", "China");
hashTable.put("Paris", "France");
hashTable.put("Washington", "USA");
hashTable.put("Brazilia", "Brazil");
System.out.println("Size: " + hashTable.size());

System.out.println((String) hashTable.get("Tokyo"));
System.out.println((String) hashTable.get("Seoul"));
System.out.println((String) hashTable.get("Beijing"));
System.out.println((String) hashTable.get("Paris"));
System.out.println((String) hashTable.get("Washington"));
System.out.println((String) hashTable.get("Brazilia"));

hashTable.remove("Brazilia");
System.out.println("Size: " + hashTable.size());
System.out.println((String) hashTable.get("Brazilia"));
System.out.println(hashTable.toString());

위의 코드를 실행하면 다음과 같이 출력됩니다.

Size: 6
Japan
Korea
China
France
USA
Brazil
Size: 5
null
<HashTable>
  Key(hash, index): Paris(611, 611), Value: France
  Key(hash, index): Seoul(626, 626), Value: Korea
  Key(hash, index): Tokyo(666, 666), Value: Japan
  Key(hash, index): Beijing(913, 913), Value: China
  Key(hash, index): Washington(975, 975), Value: USA

위의 예제에서 toString()의 결과를 보면 중복된 hash가 없어서 모두 hash와 동일한 index에 저장되고 있습니다.

만약 다음과 같이 동일한 hash를 리턴하도록 만들면 hash + 1과 같이 다음 index에 저장됩니다. hash 충돌이 발생하면 성능적으로 좋지 않지만, hash 충돌이 적다고 생각된다면 간단히 구현하는 방법을 선택할 수 있습니다.

private int getHash(String key) {
    return 0;
}

위의 예제에서 hash가 0으로 리턴되도록 만들고 코드를 실행하면 다음과 같이 hash는 동일하지만 저장되는 index는 다른 것을 볼 수 있습니다.

<HashTable>
  Key(hash, index): Tokyo(0, 0), Value: Japan
  Key(hash, index): Seoul(0, 1), Value: Korea
  Key(hash, index): Beijing(0, 2), Value: China
  Key(hash, index): Paris(0, 3), Value: France
  Key(hash, index): Washington(0, 4), Value: USA
Loading script...

Related Posts

codechachaCopyright ©2019 codechacha