（新手必看）HashMap是什么？

02-29 阅读 0评论

$（新手必看）HashMap是什么？,（新手必看）HashMap是什么？,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,安全,方法,第2张$

（图片来源网络，侵删）

所属专栏: JavaEE初阶

一、哈希表的概念

二、哈希表的一些参数

默认初始容量为16

最大长度为2的30次幂

默认加载因子为0.75

$（新手必看）HashMap是什么？,（新手必看）HashMap是什么？,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,安全,方法,第3张$

（图片来源网络，侵删）

当链表节点小于等于6，自动退化成链表

当链表节点大于等于8，长度大于64时进行变化成红黑树

扩容阈值，当你的hashmap中的元素个数超过这个阈值，便会发生扩容

threshold = capacity * loadFactor

2.1无参构造函数

三、哈希表扩容机制

$（新手必看）HashMap是什么？,（新手必看）HashMap是什么？,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,安全,方法,第4张$

（图片来源网络，侵删）

3.1到底什么时候扩容？

3.2为什么HashMap的长度必须是2的n次幂

3.3为什么HashMap的键值可以设为null？

3.4为什么不直接取余，而要>>>16？

四、JDK1.8的新结构——红黑树

五、HashMap扩容操作是尾插还是头插？

六、HashMap是怎么解决哈希冲突的？

6.1闭散列

6.2二次探测

6.3开散列/哈希桶

一、哈希表的概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( log2 N)，搜索的效率取决于搜索过程中元素的比较次数

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

当向该结构中：

插入元素：Key-Value

根据待插入元素的关键码Key，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素：Key-Value

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功Value

在JDK1.7中，HashMap数据结构为数组+链表；JDK1.8之后增加了数组+链表+红黑树变换，HashMap存储的键值对Key-Value，Key具有唯一性，采用了链地址法来处理哈希冲突，当往 HashMap 中添加元素时，会计算 key 的 hash 值取余得出元素在数组中的的存放位置。

HashMap 是线程不安全的

在 1.8 版本的中 hash() 和 resize( ) 方法也有了很大的改变，提升了性能

Key和Value都可存放null，Key只能存放一个null

//HashMap的默认初始长度16 static final int DEFAULT_INITIAL_CAPACITY = 1 >>16？

如果使用直接使用hashCode对数组大小取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的
(h >>> 16)是无符号右移16位的运算，左边补0，得到 hashCode 的高16位，可以使得到的 hash 值更加散列，尽可能减少哈希冲突，提升性能
而这么来看 hashCode 被散列 (异或) 的是低16位，而 HashMap 数组长度一般不会超过2的16次幂，那么高16位在大多数情况是用不到的，所以只需要拿 key 的 HashCode 和它的低16位做异或即可利用高位的hash值，降低哈希碰撞概率也使数据分布更加均匀