Hash (2)

소스코드

public class Hash<K, V> implements Iterable<K>{
    class HashElement<K, V> implements Comparable<HashElement<K, V>>{
        K key;
        V value;

        public HashElement(K key, V value){
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(HashElement<K, V> o) {
            return ((Comparable<K>)this.key).compareTo(o.key);
        }

    }
	
    private int numElements, tableSize;
    private double maxLoadFactor;
    LinkedList<HashElement<K, V>>[] table; 

    public Hash(int tableSize) {
        numElements = 0;
        maxLoadFactor = 0.75;
        this.tableSize = tableSize;

        table = (LinkedList<HashElement<K, V>>[]) new LinkedList[tableSize];

        for (int i = 0; i < tableSize; i++) {
            table[i] = new LinkedList<HashElement<K, V>>();
        }
    }

    public double loadFactor() {
        return (double) numElements / tableSize;
    }
	
    // 원래는 추가 뿐 아니라 업데이트 기능도 포함해야 함
    // - 키에 처음 접근할 때는 null 반환 
    // - 키에 다시 접근할 때는 기존에 저장되어 있던 value 반환
    public void add(K key, V value) {
        if (loadFactor() > maxLoadFactor) {
            resize(tableSize*2);
        }

        HashElement<K, V> he = new HashElement(key, value);

        int hv = key.hashCode();
        hv &= 0x7FFFFFFF;
        hv %= tableSize;

        table[hv].addFirst(he);
        numElements++;
    }
	
    public V remove(K key) {
        int hv = (key.hashCode() & 0x7FFFFFFF) % tableSize;

        for (HashElement<K, V> he : table[hv]) {
            if (((Comparable<K>)key).compareTo(he.key) == 0) {
                numElements--;
                return table[hv].remove(he).value;
            }
        }
        return null;
    }
	
    public V getValue(K key) {
        int hv = (key.hashCode() & 0x7FFFFFFF) % tableSize;

        for (HashElement<K, V> he : table[hv]) {
            if (((Comparable<K>)key).compareTo(he.key) == 0) {
                return he.value;
            }
        }
        return null;
    }
	
    public void resize(int newSize) {
        // Generating newTable
        LinkedList<HashElement<K, V>> [] newTable = (LinkedList<HashElement<K, V>> []) new LinkedList[newSize];

        for (int i = 0; i < newSize; i++) {
            newTable[i] = new LinkedList<HashElement<K, V>>();
        }

        // Rehashing
        for (K key : this) {
            V value = getValue(key);
            HashElement<K, V> he = new HashElement(key, value);

            int hv = (key.hashCode() & 0x7FFFFFFF) % newSize;
            newTable[hv].addFirst(he);
        }

        table = newTable;
        tableSize = newSize;
    }
	
    // K 대신 T를 써야 하는 이유 
    // - 하단 보충 설명 참조
    class IteratorHelper<T> implements Iterator<T>{

        T[] keys;
        int position;

        public IteratorHelper(){
            keys = (T[]) new Object[numElements];
            int p = 0;

            for (int i = 0; i < tableSize; i++) {
                for(HashElement<K, V> he : table[i]) {
                    keys[p++] = (T) he.key;
                }
            }

            position = 0;
        }

        @Override
        public boolean hasNext() {
            return position < keys.length;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                return null;
            }
            return keys[position++];
        }

    }
	
    @Override
    public Iterator<K> iterator() {
        return new IteratorHelper();
    }
}

 

보충 설명

내부 클래스를 class IteratorHelper<K> implements Iterator<K> {...} 로 정의했다고 해보자.

 

컴파일러는 외부 클래스의 K와 내부 클래스의 K를 구분해서 생각한다. 이 때 내부 클래스에 적혀 있는 K는 모두 내부 클래스의 K로 인식한다. 

for (int i = 0; i < tableSize; i++) {
    for (HashElement<K, V> he : table[i]) {
        keys[p++] = (K) he.key; 
    }
}

따라서 컴파일러는 위 상황을 LinkedList<HashElement<외부 K, V>> 타입인 table[i] 에서 HashElement<내부 K, V> 변수를 뽑으려고 하는 상황으로 오해하게 되고, 이 때문에 type mismatch 경고를 하게 된다. 

 

add Ver. 2

public V add(K key, V value) {
    if (loadFactor() > maxLoadFactor) {
        resize(tableSize*2);
    }

    HashElement<K, V> he = new HashElement(key, value);

    int hv = key.hashCode();
    hv &= 0x7FFFFFFF;
    hv %= tableSize;

    V oldValue = getValue(key);
    if (oldValue == null) {
        table[hv].addFirst(he);
        numElements++;
    } else {
        HashElement<K, V> oldHe = new HashElement<>(key, oldValue);
        table[hv].remove(oldHe);
        table[hv].addFirst(he);
    }

    return oldValue;
}

 

참고

교수는 Hash<K, V> 클래스가 HashI<K, V>를 구현한다고 적어 놨음.