HashTable LinearProbing 구현

HashTable을 LinearProbing으로 구현해 보았습니다.

 

해시테이블이란?

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다.

 

삽입,조회,삭제가 O(1)안에 가능하여 많이 사용됩니다.

 

구현 방법에는 링크드 리스트를 이용하는 방법과 LinearProbing방법이 있습니다.

링크드리스트를 이용해 구현하는 방법은 인터넷상에 잘 나와있기 때문에 LinearProbing방법으로 구현해 보겠습니다.    

 

메서드

• hashfunction
• put
• get
• remove
• isEmpty

구현

Key와 Value 형테로데이터를 저장하기위한 클래스 Entry를 선언합니다.

public class Entry<K, V> {
    K key;
    V value;

    public Entry(final K key, final V value) {
        this.key = key;
        this.value = value;
    }
    
    ... getter/toString
}

 

이제 Entry를 저장하는 HashTable을 만들면 됩니다.

public class HashTable_LinearProbing <K, V> {
    private Entry<K,V>[] table;
    private int size;
    private int numberOfItems;

    public HashTable_LinearProbing(final int size) {
        this.table = new Entry[size];
        this.size = size;
        this.numberOfItems = 0;
    }

    private int hashFunction(final K key) {
        String keyString = key.toString();
        int hashCode = 0;
        for (char c : keyString.toCharArray()) {
            hashCode += c;
        }

        return hashCode % size;
    }

    public void put(K key, V value) {
        int hashCode = hashFunction(key);
        System.out.println("in Put HashCode : " + hashCode + " : " + key.toString());
        if (table[hashCode] == null) {
            table[hashCode] = new Entry(key, value);
            numberOfItems++;
            System.out.println(table[hashCode].toString());
        } else {
            for (int i = (hashCode+1); i < size; i++) {
                if (table[i] == null) {
                    table[i] = new Entry(key, value);
                    numberOfItems++;
                    System.out.println(table[i].toString());
                    break;
                }
            }
        }
    }

    public V get(K key) {
        int hashCode = hashFunction(key);
        V value = null;
        System.out.println("in get HashCode : " + hashCode);
        if (table[hashCode].getKey() == key) {
            value = table[hashCode].getValue();
        } else {
            for (int i = (hashCode+1); i < size; i++) {
                if (table[i] != null) {
                    if (table[i].getKey() == key) {
                        value = table[hashCode].getValue();
                    }
                }
            }
        }
        System.out.println(value);
        return value;
    }

    public void remove(K key) {
        int hashCode = hashFunction(key);
        System.out.println("in remove HashCode : " + hashCode);
        if (table[hashCode].getKey() == key) {
            System.out.println(table[hashCode].toString());
            table[hashCode] = null;
            numberOfItems--;
        } else {
            for (int i = (hashCode+1); i < size; i++) {
                if (table[i] != null) {
                    if (table[i].getKey() == key) {
                        System.out.println(table[i].toString());
                        table[i] = null;
                        numberOfItems--;
                    }
                }
            }
        }
    }

    public boolean isEmpty() {
        System.out.print("현재 테이블의 상태 : ");
        return numberOfItems == 0;
    }

    public void print() {
        System.out.println("\n\n-------------------------------------\n\n");
        for (int i = 0; i < size; i++) {
            System.out.print(i+" : ");
            if (table[i] == null) {
                System.out.println("null : " + i);
            } else {
                System.out.println(table[i].toString());
            }
        }
    }
}

LinearProbing 방식이기에 데이터가 HashTable의 길이를 넘는다면 에러가 발생합니다.

이때 Load Factor 를 활용하여 HashTable의 크기를 늘려야 합니다.

 

느낀점

Java에서 제공하는 HashTable을 항상 사용해왔는데 직접 구현해보려고 하니

생각보다 쉽지 않았습니다.

 

간단하게 HashTable을 구현해 보면서 HashTable에대해 더 잘 알게되었습니다.