文章版权归katherine所有，请随意转载
一.HashMap概述
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作， 并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保 证该顺序恒久不变。
二.HashMap的数据结构
Jdk1.8中的结构示意图
这里写图片描述
在JDK1.8之前，HashMap采用桶+链表实现，本质就是采用数组+单向链表组合型的数据结构。它之所以有相当 快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap通过key的hashCode来计算hash值，不同的hash值就存在数组 中不同的位置，当多个元素的hash值相同时（所谓hash冲突），就采用链表将它们串联起来（链表解决冲突），放置在该hash值所对应的数组位置上。
在JDK1.8中，HashMap的存储结构已经发生变化，它采用数组+链表+红黑树这种组合型数据结构。当hash值发生冲突时，会采用链表或者红黑树解决冲突。当同一hash值的结点数小于8时，则采用链表，否则，采用红黑树。
通过key的hashCode来计算hash值再计算下标值
只要hashCode相同，计算出来的hash值就一样
就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突解决冲突示意图如下
这里写图片描述
在看源码之前我们先看一下源码中涉及的关键属性：
三.关键属性
capacity
capacity译为容量。capacity就是指HashMap中桶的数量。默认值为16。一般第一次扩容时会扩容到64，之后是2倍。总之，容量都是2的幂。
loadFactor
loadFactor译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为：size/capacity
size
size表示HashMap中存放node的数量就是所有的键值对的数量
threshold
threshold表示当HashMap的size大于threshold时会执行resize（扩容）操作。 �threshold=capacity*loadFactor
四.HashMap的四种构造方法
A.默认的构造方法public HashMap()
容量 = 16
装载因子=0.75
B.自定义容量publicHashMap(intinitialCapacity)
this(initialCapacity, DEFAULT_LOAD_FACTOR);
调用了重载方法 传入了自定义容量和默认的加载因子
C.自定义容量和装载因子publicHashMap
(intinitialCapacity,floatloadFactor)
要判断传入的自定义容量是否合法
重新计算阈值
D.构造一个映射关系与指定map相同的HashMap
public HashMap(Map<? extends K, ? extends V> m)
HashMap中有几个特别重要的函数，这篇博客也是主要涉及了几个比较重要的函数
四.hash（）函数
这里写图片描述
四.resize（）函数
这里写图片描述
五.put( )操作
把源码用流程图的方式展示出来了 可以对比源码来看这个流程图，或者之后补上加注释的代码
这里写图片描述
这里写图片描述
这里写图片描述
插入成功还要给size+1
然后判断是否超过阈值 需不需要扩容
总结put操作
1、(n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中).
2、若桶中已经存在元素，则比较桶中第一个元素(数组中的结点)的hash值,key值
a).hash值相等,key相等,则将第一个元素赋值给e,用e来记录。
b).hash值不相等，即key不相等；为链表结点,从尾部插入新节点
c).若结点数量达到阈值，转化为红黑树。
返回null或者被覆盖的value
六.get( )操作
这里写图片描述
这里写图片描述
总结get操作
1.桶中第一项(数组元素)hash值相等,key相等;则取第一个的值
2.若桶中已经存在元素，则比较桶中第一个元素(数组中的结点)的hash值,key值
a).若为红黑树结点，在红黑树中查找。
b).若为链表结点，在链表中查找。
七.为什么每次扩容都是二倍
为了效率 里面的运算都是位运算
那位运算是基于二进制的
然后(n-1)&hash这里就是一个典型的
初始n= 16 在减一之后是15（16的余数结果就在0-15之间）
然后与hash值做与运算的时候才能起到求余的效果
00000000 00000000 00000000 00001111
00000000 00000000 00000000 01011011
当你扩大为2的n次幂时
永远都可以通过减一得到低位全部为1的结果
那与任何数做与运算的时候都可以快速的得到取余结果
所以说当length = 2^n时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。
八.最后
hashmap涉及了很多的位运算和红黑树的操作，反正也是看的很晕
以上肯定也有很多错误
不过都看到这里了就给个喜欢呗 啾
网友评论