Algorithmen & Datenstrukturen mit Java: Beispielklasse für einfache Hash-Tabellen

Map	Schnittstelle bleibt unverändert

package ds.interfaces;
/** Simple interface for maps
 */
import java.util.Iterator;
import ds.util.Invariant;
import ds.util.Function2;
import ds.util.K;  // example class for keys
import ds.util.V;  // example class for values
import ds.util.KV; // key value pair
public
    interface Map
    extends Iterable<KV>,
            Invariant {
    boolean isEmpty();
    boolean member(K k);
    V       lookup(K k);
    int     size();
    KV      findMin();
    KV      findMax();
    Map     insert(K k, V v);
    Map     remove(K k);
    Map     union(Map m2);
    Map     difference(Map m2);
    Map     unionWith(Function2<V,V,V> op, Map m2);
    Map     differenceWith(Function2<V,V,V> op, Map m2);
    Map     copy();
    // inherited
    // public Iterator<KV> iterator();
    // public inv();
}

Map	implementiert als sehr einfache Hash-Tabelle
	ohne Generics
	nur eine destruktive Implementierung ist hier sinnvoll

package ds.destructive.map;
/** Implementation of maps with hash maps implemeted as arrays
    hash maps require a a hash function on the
    keys of a map. These hashes are used for indexing the
    hash table.
    This is a DESTRUCTIVE implementation.
*/
import ds.interfaces.Map;
import ds.util.K;  // example class for keys
import ds.util.V;  // example class for values
import ds.util.KV; // key value pair
import static ds.util.KV.mkPair;
import ds.util.Function2;
import ds.util.Invariant;
import ds.util.Pair;
import ds.util.Predicate;
import java.util.Iterator;
import static ds.util.Undef.undefined;
//----------------------------------------
public
    class SimpleHashMap
    implements Map {
    //----------------------------------------
    private int     card;
    private KV []  elems;
    SimpleHashMap (int len) {
        card   = 0;
        elems  = new KV [len];
        ++cntMap;
    }
    //----------------------------------------
    // the smart constructors
    // empty list
    public static SimpleHashMap empty() {
        return
            empty(16); // why 16?
    }
    public static SimpleHashMap empty(int length) {
        int l = 16;
        while (l < length) l *= 2;
        // length of hash table is always a power of 2
        // for efficient modulo operations
        return
            new SimpleHashMap(length);
    }
    public static
        SimpleHashMap fromIterator(Iterator<KV> elems) {
        SimpleHashMap res = empty();
        while ( elems.hasNext() ) {
            KV p = elems.next();
            res  = res.insert(p);
        }
        return
            res;
    }
    public boolean isEmpty() {
        return size() == 0;
    }
    public boolean member(K k) {
        return
            lookup(k) != null;
    }
    public int size() {
        return
            card;
    }
    public V lookup(K k) {
        int ix = keyToHash(k);
        KV  kv = elems[ix];
        while ( kv != null
                &&
                ! kv.fst.equalTo(k)
                ) {
            incr(ix);
            kv = elems[ix];
        }
        return
            kv == null ? null : kv.snd;
    }
    public KV findMin() {
        return
            undefined("findMin not implemented");
    }
    public KV findMax() {
        return
            undefined("findMax not implemented");
    }
    public SimpleHashMap insert(K k, V v) {
        return
            insert(mkPair(k,v));
    }
    public SimpleHashMap insert(KV p) {
        K   k  = p.fst;
        int ix = keyToHash(k);
        KV  kv = elems[ix];
        while ( kv != null
                &&
                ! kv.fst.equalTo(k)
                ) {
            incr(ix);
            kv = elems[ix];
        }
        if (kv == null) {
            // new elem
            elems[ix] = p;
            ++card;
        } else {
            // update of value
            elems[ix] = p;
        }
        return
            checkExpand();
    }
    public SimpleHashMap remove(K k) {
        return
            undefined("remove not implemented");
    }
    public SimpleHashMap union(Map m2) {
        return
            unionWith(const2, m2);
    }
    public
    SimpleHashMap unionWith(Function2<V,V,V> op,
                                Map m2) {
        return undefined("unionWith not implemented");
    }
    public
    SimpleHashMap difference(Map m2) {
        return
            differenceWith(null2, m2);
    }
    public
    SimpleHashMap differenceWith(Function2<V,V,V> op,
                                 Map m2) {
        return
            undefined("differenceWith not implemented");
    }
    public SimpleHashMap copy() {
        return
            this;
    }
    public Iterator<KV> iterator() {
        ++cntIter;
        return
            new HashMapIterator(this);
    }
    public boolean inv() {
        for (int i = 0; i < elems.length; ++i) {
            if (elems[i] != null) {
                int ix = keyToHash(elems[i].fst);
                /* all entries in hashtable
                   in the intervall [ix..i]
                   must be filled, otherwise the hash does not
                   fit to the position
                */
                int j = i;
                while (j != ix) {
                    decr(j);
                    if (elems[j] == null)
                        // unused cell found
                        return
                            false;
                }
            }
        }
        return true;
    }
    //----------------------------------------
    // internal methods
    private static Function2<V,V,V> const2
        = new Function2<V,V,V>() {
        public V apply(V x, V y) {
            return y;
        }
    };
    private static Function2<V,V,V> null2
        = new Function2<V,V,V>() {
        public V apply(V x, V y) {
            return null;
        }
    };
    private int keyToHash(K k) {
        return
            k.hash() & (elems.length - 1);
    }
    private int incr(int i) {
        ++i;
        return
            i == elems.length ? 0 : i;
    }
    private int decr(int i) {
        return
            (i == 0 ? elems.length : i) - 1;
    }
    private SimpleHashMap checkExpand() {
        if (card > elems.length) {
            return
                reorganize(2 * elems.length);
        }
        return this;
    }
    private SimpleHashMap reorganize(int newSize) {
        SimpleHashMap nm = empty(newSize);
        for (int i = 0; i < elems.length; ++i) {
            nm = nm.insert(elems[i]);
        }
        return
            nm;
    }
    private static
        class HashMapIterator
        extends ds.util.Iterator<KV> {
        SimpleHashMap map;
        int len;
        int ix;
        HashMapIterator(SimpleHashMap m) {
            map = m;
            ix  = 0;
            len = m.elems.length;
            advance();
            ++cntIter;
        }
        public boolean hasNext() {
            return
                ix < len;
        }
        private void advance() {
            while ( ix < len
                    &&
                    map.elems[ix] == null
                  ) {
                ++ix;
            }
        }
        public KV next() {
            if ( ix == len )
                return
                    undefined("empty hashmap");
            KV res = map.elems[ix];
            ++ix;
            advance();
            return
                res;
        }
    }
    //----------------------------------------
    // profiling
    private static int cntMap  = 0;
    private static int spcMap = 0;
    private static int cntIter = 0;
    public static String stats() {
        return
            "stats for ds.destructive.map.SimpleHashMap:\n" +
            "# new SimpleHashMap()      : " + cntMap + "\n" +
            "# words SimpleHashMap()    : " + spcMap + "\n" +
            "# new Iterator()           : " + cntIter + "\n";
    }
    public String objStats() {
        int o =
            1 +   // SimpleHashMap
            1 +   // array
            card; // KV
        int f =
            2 +                // SimpleHashMap
            elems.length + 1 + // array
            card * 2;          // KV
        int m = o + f;
        return
            "mem stats for ds.destructive.map.SimpleHashMap object:\n" +
            "# objects              : " + o + "\n" +
            "# fields               : " + f + "\n" +
            "# mem words            : " + m + "\n";
    }
}

Quellen
	interface Map
	class SimpleHashMap
	class K
	class V
	class KV
	class Iterator
	class Invariant
	class Undef