util HashMap

来源:互联网 发布:js如何产生随机数 编辑:IT博客网 时间:2019/10/14 19:51

1.HashMap涉及的数据结构

   Entry[] ;

   //Entry数组:存储HashMap元素的地方.

   //Entry

   //1.封装了key;value;

   //2.本身是一个单向链表;包含hash值;next;指针;

 static class Entry<K,V> implements Map.Entry<K,V> {        final K key;        V value;        Entry<K,V> next;        final int hash;        /**         * Creates new entry.         */        Entry(int h, K k, V v, Entry<K,V> n) {            value = v;            next = n;            key = k;            hash = h;        }


2.存储的过程:

 

通过hashcode得到index后.存储的不仅仅是该元素的key,value,hash.还有指向下一个Entry的引用.如果出现了hashcode冲突问题.则新建一个Entry;将该Entry的nex指针指向已存在的Entry.

   public V put(K key, V value) {        if (key == null)            return putForNullKey(value);        int hash = hash(key.hashCode());        int i = indexFor(hash, table.length);        for (Entry<K,V> e = table[i]; e != null; e = e.next) {            Object k;            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //已经存在                V oldValue = e.value;                e.value = value;                e.recordAccess(this);                return oldValue;            }        }      //不存在,则插入        modCount++;        addEntry(hash, key, value, i);        return null;    }

 void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);        if (size++ >= threshold)            resize(2 * table.length);    }

3.取值的过程

 

还是hash-index-Entry的过程.不是直接return该index上Entry;而要检查Entry链上真正对应的那个


   public V get(Object key) {        if (key == null)            return getForNullKey();        int hash = hash(key.hashCode());        for (Entry<K,V> e = table[indexFor(hash, table.length)];             e != null;             e = e.next) {            Object k;            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))                return e.value;        }        return null;    }