Overview of HashMap

HashMap



< key, value >



asynchronous
Null allowed






Initial capacity
Load factor
capacity
Load factor
Is a measure of how full a hash table can be before its capacity automatically increases
rehash






Default load factor (0.75)



Is not synchronized


Map m = Collections.synchronizedMap(new HashMap(…) );


Constructors












Initial capacity
Load factor








Data structure









// Entry is a one-way linked list. It is the linked list of “HashMap chained storage”.

// Implement the Map.Entry interface, namely getKey(),getValue(),setValue(V value),equals(Object O),hashCode()

static class Entry<K,V> implements Map.Entry<K,V> {  

    final K key;  

    V value;  

// point to the next node

    Entry<K,V> next;  

    final int hash;  

 

// constructor

// Input parameters include “hash “,” key (k)”, “value (v)”,” next node (n)”

    Entry(int h, K k, V v, Entry<K,V> n) {  

        value = v;  

        next = n;  

        key = k;  

        hash = h;  

    }  

 

    public final K getKey() {  

        return key;  

    }  

    public final V getValue() {  

        return value;  

    }    

    public final V setValue(V newValue) {  

        V oldValue = value;  

        value = newValue;  

        return oldValue;  

    }    

// Determine whether two entries are equal

// If the “key” and “value” of two entries are equal, true is returned.

// Otherwise, return false

    public final boolean equals(Object o) {  

        if(! (oinstanceof Map.Entry))  

            return false;  

        Map.Entry e = (Map.Entry)o;  

        Object k1 = getKey();  

        Object k2 = e.getKey();  

        if(k1 == k2 || (k1 ! =null && k1.equals(k2))) {  

            Object v1 = getValue();  

            Object v2 = e.getValue();  

            if(v1 == v2 || (v1 ! =null && v1.equals(v2)))  

                return true;  

        }  

        return false;  

    }    

/ / implementation hashCode ()

    public final int hashCode() {  

        return (key==null   ? 0 : key.hashCode()) ^  

               (value==null ? 0 : value.hashCode());  

    }    

    public final String toString() {  

        return getKey() + “=” + getValue();  

    }    

RecordAccess () is called when adding elements to the HashMap.

// Do nothing here

    void recordAccess(HashMap<K,V> m) {  

    }    

RecordRemoval () is called when an element is removed from the HashMap.

// Do nothing here

    void recordRemoval(HashMap<K,V> m) {  

    }  

}


// Find the smallest power of 2 greater than Capacity, keeping the Hash table Capacity to a power of 2

// The idea of the algorithm: by using logical operations instead of mod, there is a rule that when N is Power of two, then X % N==X&(n-1).

    static final int tableSizeFor(int cap) {

        int n = cap – 1;

n |= n >>> 1; // >>> unsigned right shift, high complement 0

n |= n >>> 2; / / | = b is the bitwise or a and b and then assigned to a

        n |= n >>> 4;

        n |= n >>> 8;

        n |= n >>> 16;

        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

    }

// Construct an empty HashMap with an initial capacity and load factor specified

    public HashMap(int initialCapacity, float loadFactor) {

        if (initialCapacity < 0)

            throw new IllegalArgumentException(“Illegal initial capacity: ” + initialCapacity);

        if (initialCapacity > MAXIMUM_CAPACITY)

            initialCapacity = MAXIMUM_CAPACITY;

        if (loadFactor <= 0 || Float.isNaN(loadFactor))

            throw new IllegalArgumentException(“Illegal load factor: ” +  loadFactor);

        this.loadFactor = loadFactor;

        this.threshold = tableSizeFor(initialCapacity);

    }

// Construct an empty HashMap with the specified initial capacity and default load factor (0.75)

    public HashMap(int initialCapacity) {

        this(initialCapacity, DEFAULT_LOAD_FACTOR);

    }

Construct an empty HashMap with a default initial capacity (16) and a default load factor (0.75)

    public HashMap() {

        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

    }

// Construct a new HashMap with the same mapping as the specified Map, the same capacity as the specified Map, and the default load factor of 0.75

    public HashMap(Map<? extends K, ? extends V> m) {

        this.loadFactor = DEFAULT_LOAD_FACTOR;

        putMapEntries(m, false);

    }








// Entry is a one-way linked list.

// It is the list corresponding to “HashMap chain storage”.

// It implements the Map.Entry interface, which implements getKey(), getValue(), setValue(V value), equals(Object O), hashCode()

    static class Entry<K,V> implements Map.Entry<K,V> {  

        final K key;  

        V value;  

// point to the next node

        Entry<K,V> next;  

        final int hash;  

// constructor.

// Input parameters include “hash “,” key (k)”, “value (v)”,” next node (n)”

        Entry(int h, K k, V v, Entry<K,V> n) {  

            value = v;  

            next = n;  

            key = k;  

            hash = h;  

        }  

.

    }