Interview(7)Map and Hash Table

Interview(7)Map and Hash Table

Map - (key, value)
java.util.Map interface

public class MapDLNode implements Map {
    private List list;
    private EqualityTester tester;

    public MapDLNode(){  this(new EqualityTesterDefault()); }
    public MapDLNode(EqualityTester tester){  this(list = new ListDLNode(); tester = tester); }   
    public int getSize() { return list.getSize(); }
    public boolean isEmpty() {  return list.isEmptyy(); }

    public Object get(Object key){
        Iterator p = list.positions();
        while(p.hasNext()){
            Position pos = (Position) p.getNext();
            Entry entry = (EntryDefault) pos.getElem();
            if( tester.isEqualTo(entry.getKey(), key)){
                return entry.getValue();
            }
        }
        return null;
    }

    public Object put(Object key, Object value){
        Iterator p = list.positions();
        while (p.hasNext()){ //loop all the elements
            Position pos = (Position) p.getNext();
            Entry entry = (EntryDefault) pos.getElem();
            if( tester.isEqualTo(entry.getKey(), key)){
                Object oldValue = entry.getValue();
                list.replace(pos, new EntryDefault(key, value));
                return oldValue;
            }
        }
       
        list.insertFirst(new EntryDefault(key, value));
        return null;
    }

    public Object remove(Object key){
        Iterator p = list.positions();
        while (p.hasNext()){
            Position pos = (Position) p.getNext();
            Entry entry = (EntryDefault) pos.getElem();
            if(tester.isEqualTo(entry.getKey, key)){
                Object oldValue = entry.getValue();
                list.remove(pos);
                return oldValue;
            }
        }
        return null;
    }
    public Iterator entries() { return new IteratorElement(list); }
}

get(key), put(key, value), remove(key) - O(n), system will scan all the elements in these methods.

Hash Table
Bucket Array, array[0.. N-1]
Convert the key to 0 - N-1 ——> Hash Function

Hash Code —> hashCode()  —> 32 int

static int hashCode(long l){
    return (int) ((l>>32) + (int)l; )
}

Convert 2^32 = 4G = 0..N-1

|i| mod N = 0 .. N-1

MAD - Multiply Add Divide   | a x i + b| mod N

No matter how we improve the Hash Function or Solution, we still have the conflicts.

Solution to the Conflict - Separate Chaining
All the Value are List similar to below, or empty, or single value

Solution to the Conflict - Collision Pool
Two Bucket, one for normal items, one for conflict items

public class MapHashTable implements Map {

    private Map[] a; // bucket array
    private int n;
    private final double maxLemda = 0.75;
    private int size;
    private EqualityTester t;

    public MapHashTable(){
        this(0, new EqualityTesterDefault());
    }

    public MapHashTable(int n, EqualityTester t){
        t = t;
        n = p(n); //less than n
        a = new Map[n];
        for(int i = 0;i< n;i++){
            a[i] = new MapDLNode(t); //use MapDLNode for in bucket array
        }
        size = 0;
    }

    private int h(Object key) {  return key.hashCode() % N; } //hash code the key and mod N
    private static boolean prime(int n){ ..snip… } //check prime number
    private static int p(int n) { …snip.. } //return the prime number bigger than n
    public int getSize() { return size; }
    public boolean isEmpty(){  return 0 == size; }

    public Object get(Object key){
        return a[h(key)].get(key);
    }
   
    public Object put(Object key, Object value) {
        Object oldValue = A[h(key)].put(key, value);
        if(null == oldValue){
            size++; //new item, update size
            if(size > N * maxLemda){
                rehash();
            }
        }
        return oldValue;
    }

    public Object remove(Object key) {
        Object oldValue = A[h(key)].remove(key);
        if( null != oldValue) { size- -;  }
        return oldValue;
    }

    public Iterator entries(){ //combine all the entries together
        List l = new ListDLNode();
        for(int i = 0;i<N;i++){
            Iterator it = a[i].entries();
            while(it.hasNext()){
                l.insertLast(it.getNext());
            }
        }
        return new InteratorElement(l);
    }

    private void rehash(){
        Iterator it = this.entries();
        N = p(N<<1);
        A = new Map[N]; //double the N
        for(int i = 0;i<N;i++){
            A[i] = new MapDLNode(T);
        }
        while(it.hasNext()) {
            Entry e = (Entry)it.getNext();
            Object k = e.getKey();
            Object v = e.getValue();
            a[h(k)].put(k, v); //re-insert everything
        }
    }
}

Dictionary


References: