首页 > 代码库 > HashMap put,get操作

HashMap put,get操作

HashMap中的put方法

public V put(K key, V value) {        //当key为null,调用putForNullKey方法,保存null与table第一个位置中,这是HashMap允许为null的原因        if (key == null)            return putForNullKey(value);        //计算key的hash值        int hash = hash(key.hashCode());                  ------(1)        //计算key hash 值在 table 数组中的位置        int i = indexFor(hash, table.length);             ------(2)        //从i出开始迭代 e,找到 key 保存的位置        for (Entry<K, V> e = table[i]; e != null; e = e.next) {            Object k;            //判断该条链上是否有hash值相同的(key相同)            //若存在相同,则直接覆盖value,返回旧value            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {                V oldValue = e.value;    //旧值 = 新值                e.value =http://www.mamicode.com/ value;                e.recordAccess(this);                return oldValue;     //返回旧值            }        }        //修改次数增加1        modCount++;        //将key、value添加至i位置处        addEntry(hash, key, value, i);        return null;    }

key为null:

private V putForNullKey(V value) {        for (Entry<K,V> e = table[0]; e != null; e = e.next) {            if (e.key == null) {                V oldValue = e.value;                e.value = value;                e.recordAccess(this);                return oldValue;            }        }        modCount++;        addEntry(0, null, value, 0);        return null;    }

获取Entry的第一个元素table[0],并基于第一个元素的next属性开始遍历,直到找到key为null的Entry,将其value设置为新的value值。
如果没有找到key为null的元素,则调用如上述代码的addEntry(0, null, value, 0);增加一个新的entry

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);    }

hash方法:

static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }

讲解说明:

技术分享
将hash函数作为已给定的hashCode的一个补充,可以提高hash函数的质量。hash质量的好坏是非常重要的,因为HashMap用2的次幂作为表的hash长度,这就容易产生冲突,因为hashCodes在低位不是不同的(hashCodes that do not differ in lower bits)。注意:Null 的key的hash值总是0,即他在table的索引为0。       让我们通过例子来帮助我们理解一下上面的话。加入说key object的hashCode()只返回三个值:31、63和95.31、63和95都是int型,所以是32位的。        31=00000000000000000000000000011111         63=00000000000000000000000000111111         95=00000000000000000000000001011111      现在加入HashMap的table长为默认值16(2^4,HashMap的长度总是2的次幂)      假如我们不用hash函数,indexFor将返回如下值:      31=00000000000000000000000000011111 => 1111=15       63=00000000000000000000000000111111  => 1111=15       95=00000000000000000000000001011111 => 1111=15为什么会这样?因为当我们调用indexFor函数的时候,它将执行31&15,,63&15和95&15的与操作,比如说95&15得出一下结果:        00000000000000000000000001011111 &00000000000000000000000000001111        也就是说(2^n-1)总会是一个1的序列,因此不管怎样,最后会执行0&1的于然后得出0.        上面的例子,也就解释了凡是在末尾全是1111的都返回相同的index,因此,尽管我们有不同的hashcode,Entry对象却讲都被存在table中index为15的位置。        倘若我们使用了hash函数,对于上面每一个hashcode,经过hash作用作用后如下:        31=00000000000000000000000000011111 => 00000000000000000000000000011110         63=00000000000000000000000000111111  => 00000000000000000000000000111100         95=00000000000000000000000001011111 => 00000000000000000000000001011010        现在在通过新的hash之后再使用indexFor将会返回:        00000000000000000000000000011110 =>1110=14         00000000000000000000000000111100 =>1100=12         00000000000000000000000001011010 =>1010=10        在使用了hash函数之后,上面的hashcodes就返回了不同的index,因此,hash函数对hashmap里的元素进行了再分配,也就减少了冲突同时提高了性能。         hash操作最主要的目的就是在最显著位的hashcode的差异可见,以致于hashmap的元素能够均匀的分布在整个桶里。         有两点需要注意:          如果两个key有相同的hashcode,那他们将被分配到table数组的相同index上           如果两个key不具有相同的hashcode,那么他们或许可能,或许也不可能被分配到table数组相同的index上。
View Code

indexFor方法:

static int indexFor(int h, int length) {        return h & (length-1);    }

讲解说明:

技术分享
这个方法有点意思,主要作用是定位hashmap里的bucket。-------------------------------------------------------大家知道hashmap底层就是一个数组,然后数组里每个元素装了个链表。这个数组元素称为bucket桶-------------------------------------------------------先复习一下逻辑与。0 & 0 = 0;0 & 1 = 0;1 & 0 = 0;1 & 1 = 1;第二个参数length始终为2的n次方,所以,换成二进制数就是 100,1000,10000,...(length -1)就是 11, 111,1111,...这样的话,第一个参数h比第二个参数小的情况下,那结果就是h。第一个参数h比第二个参数大的情况下,如下:例:h=18 -> 10010length-1=15 -> 01111所以在第一个参数比第二个参数大的情况下等于第一参数%第二参数,取余数
View Code

addEntry

技术分享
void addEntry(int hash, K key, V value, int bucketIndex) {        //获取bucketIndex处的Entry        Entry<K, V> e = table[bucketIndex];        //将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry         table[bucketIndex] = new Entry<K, V>(hash, key, value, e);        //若HashMap中元素的个数超过极限了,则容量扩大两倍        if (size++ >= threshold)            resize(2 * table.length);    }
View Code

put的流程:

当我们想一个HashMap中添加一对key-value时,系统首先会计算key的hash值,然后根据hash值确认在table中存储的位置。

若该位置没有元素,则直接插入。否则迭代该处元素链表并依此比较其key的hash值。

如果两个hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),则用新的Entry的value覆盖原来节点的value。

如果两个hash值相等但key值不等 ,则将该节点插入该链表的链头(最先保存的元素放在链尾),新元素设置为Entry[0],其next指针指向原有对象,即原有对象为Entry[1]

技术分享
比如, 第一个键值对A进来,通过计算其key的hash得到的i=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其i也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,i也等于0,那么C.next = B,Entry[0] = C;这样我们发现i=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起,也就是说数组中存储的是最后插入的元素。
View Code

HashMap的get操作:

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)))//-------------------1----------------                return e.value;        }        return null;    }

当key为null时,调用getForNullKey()

private V getForNullKey() {        for (Entry<K,V> e = table[0]; e != null; e = e.next) {            if (e.key == null)                return e.value;        }        return null;    }

当key不为null时,先根据hash函数得到hash值,在更具indexFor()得到i的值,循环遍历链表,如果有:key值等于已存在的key值,则返回其value。

=======================================================================================================

JDK8的讲解图:

HashMap的put方法

技术分享

=====================================================================

JDK1.8以后对hashmap进行了大量的优化

JDK8 因为对自己改造过的哈希大量冲突时的红黑树有信心,所以简单一些,只是把高16位异或下来。

  static int hash(int h) {            return h ^ (h >>> 16);        }

所以即使Key比较均匀无哈希冲突,JDK8也比JDK7略快的原因大概于此。

存在哈希冲突的情况,比如两个哈希值取模后落在同一个桶上,或者两条不同的key有相同的哈希值。
JDK7的做法是建一条链表,后插入的元素在上面,一个个地执行上面的判断。
而JDK8则在链表长度达到8,而且桶数量达到64时,建一棵红黑树,解决严重冲突时的性能问题。

http://www.cnblogs.com/chenssy/p/3521565.html

http://blog.csdn.net/zhangerqing/article/details/8193118

http://tech.meituan.com/java-hashmap.html

http://calvin1978.blogcn.com/articles/hashmap.html

http://www.importnew.com/7099.html

HashMap put,get操作