Hash Table (Java)

gistfile1.txt

package homeworks;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
 
/** Trida Pair reprezentuje dvojici (klic, hodnota). */
class Pair<K,V> {
    K key;
    V value;
 
    Pair(K k, V v) {
        key = k;
        value = v;
    }
 
    public int hashCode() {
        return key.hashCode() + 3 * value.hashCode();
    }
 
    public boolean equals(Object other) {
        if (! (other instanceof Pair<?,?>)) return false;
        Pair<?,?> o = (Pair<?,?>) other;
        return key.equals(o.key) && value.equals(o.value);
    }
}

/** Trida DSAHashTable reprezentuje rozptylovaci tabulku se zřetězením (první varianta v 
učebnici). */
class DSAHashTable<K,V> {
    HashSet<Pair<K,V>> arrayOfSets[];
    int size;
    int numberOfElements;
    Iterator it;
 
    /** Vytvori prazdnou instanci DSAHashTable, delka vnitrniho pole je nastavena na size, obsah vnitrniho pole
     * je inicializovan na prazdne mnoziny.
     */
    DSAHashTable(int size) {
        arrayOfSets = (HashSet<Pair<K, V> >[]) new HashSet<?>[size];
        this.size = size;
        for(int i=0; i<size;i++){
            arrayOfSets[i]=new HashSet<Pair<K,V>>();
        }
        numberOfElements=0;
    }
    
    /** Ulozi dvojici (key, value) do rozptylovaci tabulky. Pokud uz v tabulce je jina dvojice se stejnym klicem,
     * je smazana. Klic ani hodnota nesmi byt null. Pokud by pocet dvojic v tabulce po vykonani put mel vzrust nad
     *  dvojnasobek delky vnitrniho pole, vnitrni pole zdvojnasobi.
     */
    void put(K key, V value) {
        if(key==null || value==null){
            return;
        }
        int hash = this.getIndexOf(key);
        Pair<K,V> pair = new Pair<K,V>(key, value);
        
        V v = this.get(key);
        if(v != null){
           this.remove(key);
        }
        numberOfElements++;
        arrayOfSets[hash].add(pair);
        if (!isBigEnough()) {
            this.resize(2*size);
        }
    }
    
    
    /** Vrati hodnotu asociovanou s danym klicem nebo null, pokud dany klic v tabulce neni. */
    V get(K key) {
        int hash = this.getIndexOf(key);
        if(key==null){
            return null;
        }
        it = arrayOfSets[hash].iterator();
        while (it.hasNext()) {
            Pair p = (Pair) it.next();
            if (p.key.equals(key)) {
                return (V)p.value;
            }
        }
        return null;
    }
    
    /** Smaze dvojici s danym klicem. Pokud v tabulce dany klic neni, nedela nic. */
    void remove(K key) {
        if(key==null){
            return;
        }
        int hash = this.getIndexOf(key);
        Pair<K,V> p;
        
        it = arrayOfSets[hash].iterator();
        while (it.hasNext()) {
            p = (Pair<K,V>) it.next();
            if (p.key.equals(key)) {
                arrayOfSets[hash].remove(p);
                numberOfElements--;
                break;
            }
        }

    }

    /** Vrati vnitrni pole. Prvni vnitrniho pole mohou byt instance trid v balicku java.util, 
tzn. nemusite psat
     *  vlastni implementaci rozhrani java.util.Set.
     */
    Set<Pair<K,V>>[] getArray() {
        return arrayOfSets;
    }
    
    
    /** Pro dany klic vrati index v poli. Jako hashovaci funkce se pouzije key.hashCode. */
    int getIndexOf(K key) {
        return Math.abs(key.hashCode())%size;
    }
    
    
    /** Pokud je pocet prvku mensi nebo roven dvojnasobku delky vnitrniho pole, vrati true, jinak vrati false. */
    boolean isBigEnough() {
        if(numberOfElements<=2*size){
            return true;
        }
        else return false;
    }
    
    
    /** Zmeni delku vnitrniho pole, nainicializuje jej prazdnymi mnozinami a zkopiruje do nej vsechny dvojice. */
    void resize(int newSize) {
        HashSet<Pair<K,V>> oldArrayOfSets[] = arrayOfSets;
        HashSet<Pair<K,V>> newArrayOfSets[] = (HashSet<Pair<K, V> >[]) new HashSet<?>[newSize];
        this.arrayOfSets = newArrayOfSets;
        numberOfElements = 0;
        this.size = newSize;
        
        for (int j = 0; j < arrayOfSets.length; j++) {
            arrayOfSets[j]=new HashSet<Pair<K, V>>();
        }
        
        for (int i = 0; i < oldArrayOfSets.length; i++) {
            Iterator oaos_it = oldArrayOfSets[i].iterator();
            Pair p;
            while (oaos_it.hasNext()) {
                p = (Pair<K, V>) oaos_it.next();
                this.put((K) p.key, (V) p.value);
            }
        }
    }
    
    
    //** Vrati iterator pres vsechny dvojice v tabulce. Iterator nemusi mit implementovanou metodu remove. */
    Iterator<Pair<K,V>> iterator() {
        ArrayList<Pair<K,V>> al = new ArrayList<Pair<K, V>>();
        for (int i = 0; i < arrayOfSets.length; i++) {
            Iterator setIt = arrayOfSets[i].iterator();
            while(setIt.hasNext()){
                Pair p = (Pair) setIt.next();
                al.add(p);
            }
        }
        return al.iterator();
    }

}