Java中的HashMap的工作原理是什么？_

金玉峰

hashmap的底层是以数组和单向链表进行实现的，当进行put操作的时候，首先通过hashcode()方法进行计算key的hash值，然后找出链表索引，然后看索引上是否有相同的key值，如果有就更新value值，如果没有就把值加在链表尾。hashmap有两个重要的属性参数，capacity（容量）和loadfactor（负载因子），初始值分别为16与0.75，当存储的数据的数量达到了capacity*loadfactor就会进行扩容操作（resize），将容量扩充为2n。一般进行初始化的时候，可以重新设置capacity与loadfactor，但是一般capacity的默认值一般是比较好的，不需要进行更改。只需要考虑capacity的值就行了，一般如果能够提前预估容量大小，将会大大减少扩容的消耗

编辑于 2018-04-24 21:28:01 回复(0)

要去看酷玩演唱会！

hashmap是一个key-value键值对的数据结构，从结构上来讲在jdk1.8之前是用数组加链表的方式实现，jdk1.8加了红黑树，hashmap数组的默认初始长度是16，hashmap数组只允许一个key为null，允许多个value为null
hashmap的内部实现，hashmap是使用数组+链表+红黑树的形式实现的，其中数组是一个一个Node[]数组，我们叫他hash桶数组，它上面存放的是key-value键值对的节点。HashMap是用hash表来存储的，在hashmap里为解决hash冲突，使用链地址法，简单来说就是数组加链表的形式来解决，当数据被hash后，得到数组下标，把数据放在对应下表的链表中。
然后再说一下hashmap的方法实现
put方法，put方法的第一步，就是计算出要put元素在hash桶数组中的索引位置，得到索引位置需要三步，去put元素key的hashcode值，高位运算，取模运算，高位运算就是用第一步得到的值h，用h的高16位和低16位进行异或操作，第三步为了使hash桶数组元素分布更均匀，采用取模运算，取模运算就是用第二步得到的值和hash桶数组长度-1的值取与。这样得到的结果和传统取模运算结果一致，而且效率比取模运算高
jdk1.8中put方法的具体步骤，先判断hashmap是否为空，为空的话扩容，不为空计算出key的hash值i，然后看table[i]是否为空，为空就直接插入，不为空判断当前位置的key和table[i]是否相同，相同就覆盖，不相同就查看table[i]是否是红黑树节点，如果是的话就用红黑树直接插入键值对，如果不是开始遍历链表插入，如果遇到重复值就覆盖，否则直接插入，如果链表长度大于8，转为红黑树结构，执行完成后看size是否大于阈值threshold，大于就扩容，否则直接结束
get方法就是计算出要获取元素的hash值，去对应位置取即可。
扩容机制，hashmap的扩容中主要进行两部，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算hash插入到新数组中，在jdk1.8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二部一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。
3.hashmap大小为什么是2的幂次方
在计算插入元素在hash桶数组的索引时第三步，为了使元素分布的更加均匀，用取模操作，但是传统取模操作效率低，然后优化成h&(length-1)，设置成2幂次方，是因为2的幂次方-1后的值每一位上都是1，然后与第二步计算出的h值与的时候，最终的结果只和key的hashcode值本身有关，这样不会造成空间浪费并且分布均匀，如果不是2的幂次方
如果length不为2的幂，比如15。那么length-1的2进制就会变成1110。在h为随机数的情况下，和1110做&操作。尾数永远为0。那么0001、1001、1101等尾数为1的位置就永远不可能被entry占用。这样会造成浪费，不随机等问题。

发表于 2018-03-08 20:37:45 回复(23)

牛客623299号

HashMap的底层是用hash数组和单向链表实现的，当调用put方法是，首先计算key的hashcode，定位到合适的数组索引，然后再在该索引上的单向链表进行循环遍历用equals比较key是否存在，如果存在则用新的value覆盖原值，如果没有则向后追加。HashMap的两个重要属性是容量capacity和加载因子loadfactor，默认值分布为16和0.75，当容器中的元素个数大于 capacity*loadfactor时，容器会进行扩容resize 为2n，在初始化Hashmap时可以对着两个值进行修改，负载因子0.75被证明为是性能比较好的取值，通常不会修改，那么只有初始容量capacity会导致频繁的扩容行为，这是非常耗费资源的操作，所以，如果事先能估算出容器所要存储的元素数量，最好在初始化时修改默认容量capacity，以防止频繁的resize操作影响性能。

发表于 2016-07-26 19:39:09 回复(9)

evoler

HashMap类有一个叫做Entry的内部类。这个Entry类包含了key-value作为实例变量。每当往hashmap里面存放key-value对的时候，都会为它们实例化一个Entry对象，这个Entry对象就会存储在前面提到的Entry数组table中。Entry具体存在table的那个位置是根据key的hashcode()方法计算出来的hash值（来决定）。

发表于 2016-03-09 15:56:33 回复(1)

清蒸巴旦木

java8对hashmap做了优化，底层有两种实现方法，一种是数组和链表，一种是数组和红黑树，hsahmap会根据数据量选择存储结构

if (binCount >= TREEIFY_THRESHOLD - 1)
当符合这个条件的时候，把链表变成treemap，这样查找效率从o(n)变成了o(log n)

发表于 2016-08-12 16:53:52 回复(0)

老铁好好干啊

http://blog.csdn.net/vking_wang/article/details/14166593

发表于 2017-07-20 17:16:45 回复(0)

xiplus329


	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 = value;



	                e.recordAccess(this);



	                return oldValue;     //返回旧值



	            }



	        }



	        //修改次数增加1



	        modCount++;



	        //将key、value添加至i位置处



	        addEntry(hash, key, value, i);



	        return null;



	    }

HashMap保存数据的过程为：首先判断key是否为null，若为null，则直接调用putForNullKey方法。若不为空则先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，则通过比较是否存在相同的key，若存在则覆盖原来key的value，否则将该元素保存在链头（最先保存的元素放在链尾）。若table在该处没有元素，则直接保存。

发表于 2017-06-26 18:41:24 回复(0)

小辣鸡223

1）hashmap是一个key-value键值对的数据结构。从结构上来讲在jdk1.8之前是用数组+链表的方式实现，jdk1.8加了红黑树(数组+链表||数组+红黑树)，hashmap数组的默认初始长度是16，hashmap数组只允许一个key为null，允许多个value为null

2）hsahmap会根据数据量选择存储结构。

if (binCount >= TREEIFY_THRESHOLD - 1)
当符合这个条件的时候，把链表变成treemap，这样查找效率从o(n)变成了o(log n)

3）HashMap中有一个Hash函数，它使用hashcode和equals()方法来向集合中添加和检索元素，当调用put()方法的时候，hashMap会计算key的hash值，该哈希值就对应了数组上的一个位置，然后把value存储在对应的索引位置上。如果key已经存在，value会被更新成新的值。hashMap的重要特性是容量负载因子和扩容极限

发表于 2019-06-21 11:38:18 回复(0)

晓黑

JDK1.8对HashMap进行了优化，加入了红黑树，有篇文章讲的挺好的：http://www.importnew.com/20386.html

编辑于 2018-04-15 11:21:10 回复(0)

Metaverse

http://www.admin10000.com/document/3322.html

发表于 2016-04-25 14:53:50 回复(0)

零一201907071439296

HashMap是一种键值对的数据结构，在jdk8之前是由数组加链表组成的，在1.8之后变成了数组加链表加红黑树组成的。当调用put方法是，则会对key进行hash计算，得到hashcode，然后通过索引定位对应的位置中，遍历该索引位置的链表并equals比较key是否存在，存在也赋予新值，不存在则在链表后面追加该键值对

编辑于 2020-04-01 12:38:22 回复(0)

mkBall

Hashmap底层是由数组和单向链表实现的，通过哈希函数实现存储。可以通过hashcode，equal，put等方法对内容操作。它拥有capcity和loadfactor两个重要属性，分别表示基础容量和负载因子。

编辑于 2020-02-27 21:26:50 回复(0)

牛客479003785号

666

发表于 2021-08-31 14:21:06 回复(0)

牛客牛牛气冲天

hashmap是一个key-value键值对的数据结构，从结构上来讲在jdk1.8之前是用数组加链表的方式实现，jdk1.8加了红黑树，hashmap数组的默认初始长度是16，hashmap数组只允许一个key为null，允许多个value为null hashmap的内部实现，hashmap是使用数组+链表+红黑树的形式实现的，其中数组是一个一个Node[]数组，我们叫他hash桶数组，它上面存放的是key-value键值对的节点。HashMap是用hash表来存储的，在hashmap里为解决hash冲突，使用链地址法，简单来说就是数组加链表的形式来解决，当数据被hash后，得到数组下标，把数据放在对应下表的链表中。然后再说一下hashmap的方法实现 put方法，put方法的第一步，就是计算出要put元素在hash桶数组中的索引位置，得到索引位置需要三步，去put元素key的hashcode值，高位运算，取模运算，高位运算就是用第一步得到的值h，用h的高16位和低16位进行异或操作，第三步为了使hash桶数组元素分布更均匀，采用取模运算，取模运算就是用第二步得到的值和hash桶数组长度-1的值取与。这样得到的结果和传统取模运算结果一致，而且效率比取模运算高 jdk1.8中put方法的具体步骤，先判断hashmap是否为空，为空的话扩容，不为空计算出key的hash值i，然后看table[i]是否为空，为空就直接插入，不为空判断当前位置的key和table[i]是否相同，相同就覆盖，不相同就查看table[i]是否是红黑树节点，如果是的话就用红黑树直接插入键值对，如果不是开始遍历链表插入，如果遇到重复值就覆盖，否则直接插入，如果链表长度大于8，转为红黑树结构，执行完成后看size是否大于阈值threshold，大于就扩容，否则直接结束 get方法就是计算出要获取元素的hash值，去对应位置取即可。扩容机制，hashmap的扩容中主要进行两部，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算hash插入到新数组中，在jdk1.8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二部一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。 3.hashmap大小为什么是2的幂次方在计算插入元素在hash桶数组的索引时第三步，为了使元素分布的更加均匀，用取模操作，但是传统取模操作效率低，然后优化成h&(length-1)，设置成2幂次方，是因为2的幂次方-1后的值每一位上都是1，然后与第二步计算出的h值与的时候，最终的结果只和key的hashcode值本身有关，这样不会造成空间浪费并且分布均匀，如果不是2的幂次方如果length不为2的幂，比如15。那么length-1的2进制就会变成1110。在h为随机数的情况下，和1110做&操作。尾数永远为0。那么0001、1001、1101等尾数为1的位置就永远不可能被entry占用。这样会造成浪费，不随机等问题。

发表于 2021-08-13 23:50:48 回复(0)

Assassin丶冷靖

它是以键值对(key-value)的形式存储元素， key值不可以重复，如果key值重复，value会被替换为新值。它使用hashCode()和equals()对元素进行增加和检索

编辑于 2020-08-31 15:15:52 回复(0)

jesse先生

<p>java中的hashmap是以键值对的形式存储元素，hashmap需要一个hash函数，他使用hashcode（）和equals方法向集合检索和添加元素。hashmap会计算key的hash</p><p>值</p>

发表于 2020-07-07 15:51:14 回复(0)

牛仔糖

HashMap是以键值对的形式存储元素的。HashMap有一个hash函数，它使用hashCode()和equals()方法来向集合添加和检索元素。当调用put()方法的时候，HashMap会计算key的hash值，然后把键值对存储在集合中合适的索引上。如果key已经存在了，value会被更新成新值。

发表于 2020-06-26 21:10:29 回复(0)