广元园区建设投资有限公司网站,温州做网站软件,网络搭建drc,怎么给网站做广告hashMap简介
HashMap是基于哈希表实现的#xff0c;每一个元素是一个key-value对#xff0c;无序#xff0c;不可重复。HashMap是非线程安全的#xff0c;只是用于单线程环境下#xff0c;多线程环境下可以采用concurrent并发包下的concurrentHashMap。HashMap 实现了Ser…hashMap简介
HashMap是基于哈希表实现的每一个元素是一个key-value对无序不可重复。HashMap是非线程安全的只是用于单线程环境下多线程环境下可以采用concurrent并发包下的concurrentHashMap。HashMap 实现了Serializable接口因此它支持序列化实现了Cloneable接口能被克隆。hashmap集合的默认初始化容量为16(23)如果初始化增加的大小则是最接近该数的2的幂次方默认加载因子为0.75也就是说这个默认加载因子是当hashMap集合底层数组的容量达到75%时数组就开始扩容。hashmap集合初始化容量是2的陪数为了达到散列均匀提高hashmap集合的存取效率。无论我们指定的容量为多少构造方法都会将实际容量设为不小于指定容量的2的次方的一个数且最大值不能超过2的30次方HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。JDK1.8之后当链表的长度达到 “8” 时内部会调用 “treeifyBin” 方法判断数组长度是否达到 “64” 达到就会自动变成红黑树的结构达不到会调用扩容机制当红黑树节点的个数达到 “6” 之后又会变成链表结构。 源码解析
初始化Map
HashMap hashMapnew HashMap();
public HashMap() {
//DEFAULT_LOAD_FACTOR 0.75f;this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted
}HashMap hashMapnew HashMap(5);
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity 0)//初始化大小不能为负数 throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);
//不能超过最大值 if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;
//指定的扩容因子不能小于等于0 if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor;this.threshold tableSizeFor(initialCapacity);
}//不管传多大的容量容量都是最靠近设置值的2的幂次方
tableSizeFor()
static final int tableSizeFor(int cap) {//返回给定目标容量的两倍幂int n cap - 1;//减1.防止传入的刚好是2的幂次方的时候得到的是下一个幂次方比如传入4不减1会得到8 n | n 1;//右移一位然后|运算能保证高2位是1是4 n | n 2;n | n 4;n | n 8;n | n 16;//类推到最大的2的32-1也就是32个1因为 java中int4字节也就是32位达到int的最大值return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;//再加1
}
举例展示
ncap-1 ; // 4 二进制位100
n | n 1; // n1 为 0000 0010 与n|运算 得到0000 0110
n | n 2; // n2 为 0000 0001 与n|运算 得到0000 0111 转换为十进制为7
n | n 8; // 还是7
n | n 16; // 还是7
return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : n 1; //再加1返回8得到的是传入的最近的2 的幂
put方法
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
hash()扰动函数
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);//让高低位都参与下标hashcode的计算
}
putVal方法
//hash 通过扰动函数得到的hash值 onlyIfAbsent false evict true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;//定义变量
//第一次进来 table为空并且tab.length为0 if ((tab table) null || (n tab.length) 0)
//进入resize方法,得到一个初始化大小为8的数组 n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)//根据 hashcode取模7 得到下标并且查询下标值是否为空第一次为null tab[i] newNode(hash, key, value, null);//在下标 位置new node 将key value赋值 else {//将数组上的链表移到新数组 NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;
}
初始化resize方法 final NodeK,V[] resize() {//返回一个node数组 NodeK,V[] oldTab table;//第一次进来为null int oldCap (oldTab null) ? 0 : oldTab.length;//oldCap0 int oldThr threshold;//传进来最靠近2的幂等的数据 现在传的是5 那么就是8 int newCap, newThr 0;if (oldCap 0) {//第一次进来不满足 if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in threshold// 满足 oldThr8 initial capacity was placed in threshold 初始容量为阈值 newCap oldThr;//newCap8 else { // zero initial threshold signifies using defaults零初始阈值表示使用默认值 不进入
newCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}
//满足条件if (newThr 0) {float ft (float)newCap * loadFactor;//ft8*0.75 得到6 newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);//newThr 为6 }threshold newThr;//赋值扩容阈值为6 SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];//初始化8大小的数组 table newTab;//将初始化的table赋值给tableif (oldTab ! null) {//第一次不满足条件不需要进行rehashfor (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {oldTab[j] null;if (e.next null)newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);if (loTail ! null) {loTail.next null;newTab[j] loHead;}if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;//返回初始化为8的tab
}
第二个元素put
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;
//table为8容量的table 不为空不进入该逻辑 if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)根据hash得 到下标如果为空直接new node tab[i] newNode(hash, key, value, null);//在下标 位置new node 将key value赋值 else {//下标如果有位置说明key是一样的或者发生了hash冲突NodeK,V e; K k;if (p.hash hash //p为下标位置已有的值 如果该值的key跟传入的一致 把e替换成p ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)//如果是黑红树 往红黑树添加节点e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {//不是node节点也不是红黑树for (int binCount 0; ; binCount) {
//e为p节点的下一个节点如果为空说明到了p节点位 置的最后一个位置循环里把p设置为eif ((e p.next) null) {p.next newNode(hash, key, value, null);//加到p节点的nextif (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//如果binCount大于等于7 代表链表的长度达到 8的时候转为红黑树 treeifyBin(tab, hash);//里面会先判断容量是否小于64不然先进行resize扩容 break;//跳出循环}
//hash冲突 并且key相同的时候直接跳出 覆盖原来 的key就行 if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for key//如果e不为null V oldValue e.value;//得到原来位置的值if (!onlyIfAbsent || oldValue null)//如果onlyIfAbsent为false 或者没有value 替换原来 的value e.value value;afterNodeAccess(e);//模板方法 return oldValue;}}modCount;if (size threshold)//如果大于我的阈值进行resizeresize();afterNodeInsertion(evict);模板return null;
}
扩容resize方法
final NodeK,V[] resize() {NodeK,V[] oldTab table;//已有的的数组table int oldCap (oldTab null) ? 0 : oldTab.length;// 之前table长度为8 int oldThr threshold;//之前的阈值为6int newCap, newThr 0;if (oldCap 0) {//80满足if (oldCap MAXIMUM_CAPACITY) {//不为最大值没有 扩容到最大值 threshold Integer.MAX_VALUE;return oldTab;}//newCap为之前容量的2倍 如果小于最大值并且之前的容量大于默 认的大小newThr为老阈值的2倍我们的例子不满足 else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr 0) {//满足该场景当前新的阈值还是0 float ft (float)newCap * loadFactor;//根据新的table容量计算下次扩容的阈值 为16 *0.7512 newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);//12赋值 给newThr }threshold newThr;//阈值设置为12SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;//讲table数组扩容到16if (oldTab ! null) {//满足 for (int j 0; j oldCap; j) {//循环老的数组数据 NodeK,V e;if ((e oldTab[j]) ! null) {//将下标的数据赋 值给e oldTab[j] null;if (e.next null)//e的next为null。代表当前位置不是链表没有发生hash冲突 newTab[e.hash (newCap - 1)] e;// 把e放到新的位置 else if (e instanceof TreeNode)//如果是红黑 树将树移到新的位置 如果小于6 会退化成单向链表 ((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);if (loTail ! null) {loTail.next null;newTab[j] loHead;}if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;
}
get方法
public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;
}
getNode方法
final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;
//table不为空并且通过hash拿到的value不为空 if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {
//第一个节点的数据就是我要的key直接返回第一个节点if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))
//不为空说明是红黑树或者链表 return first;if ((e first.next) ! null) {if (first instanceof TreeNode)//如果是红黑树返回红黑树节点return ((TreeNodeK,V)first).getTreeNode(hash, key);do {//如果是链表从链表循环找到我的数据 if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;
}
put原理
第一步首先将k,v封装到Node对象当中节点。
第二步它的底层会调用K的hashCode()方法得出hash值。
第三步通过哈希表函数/哈希算法将hash值转换成数组的下标下标位置上如果没有任何元素就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true那么这个节点的value将会被覆盖。
因此放在hashMap集合key部分的元素如果是自定义对象的话都需要重写hashCode和equal方法。 get原理
第一步先调用k的hashCode()方法得出哈希值并通过哈希算法转换成数组的下标。
第二步通过上一步哈希算法转换成数组的下标之后在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有则返回null。如果这个位置上有单向链表那么它就会拿着参数K和单向链表上的每一个节点的K进行equals如果所有equals方法都返回false则get方法返回null。如果其中一个节点的K和参数K进行equals返回true那么此时该节点的value就是我们要找的value了get方法最终返回这个要找的value。 在hashMap添加元素的时候会计算添加元素的hash值通过hash值确定放在哪个hash桶中当不同的元素计算出相同的hash桶的时候这样就发生了哈希碰撞
哈希碰撞 开放地址发
当冲突发生时使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找直到找到给定的地址。
开放地执法有一个公式:Hi(H(key)di) MOD m i1,2,…,k(km-1)
其中m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1称线性探测再散列。
如果di取1则每次冲突之后向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(km/2)称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
链地址法拉链法hashMap使用的就这这种方法
将相同hash值的对象组织成一个链表放在hash值对应的槽位
再哈希法
当发生冲突时使用第二个、第三个、哈希函数计算地址直到无冲突时。缺点计算时间增加。
比如上面第一次按照姓首字母进行哈希如果产生冲突可以按照姓字母首字母第二位进行哈希再冲突第三位直到不冲突为止
建立一个公共溢出区:
假设哈希函数的值域为[0,m-1],则设向量HashTable[0…m-1]为基本表另外设立存储空间向量OverTable[0…v]用以存储发生冲突的记录。 HashMap中的“死锁”
HashMap是非线程安全死锁一般都是产生于并发情况下。我们假设有二个进程T1、T2HashMap容量为2,T1线程放入key A、B、C、D、E。在T1线程中A、B、C Hash值相同于是形成一个链接假设为A-C-B而D、E Hash值不同于是容量不足需要新建一个更大尺寸的hash表然后把数据从老的Hash表中 迁移到新的Hash表中(refresh)。这时T2进程闯进来了T1暂时挂起T2进程也准备放入新的key这时也 发现容量不足也refresh一把。refresh之后原来的链表结构假设为C-A之后T1进程继续执行链接结构 为A-C,这时就形成A.nextB,B.nextA的环形链表。一旦取值进入这个环形链表就会陷入死循环。
解决办法
使用线程安全的ConcurrentHashMap
hashMap的容量怎么扩充
table 数组大小是由 capacity 这个参数确定的默认是16也可以构造
时传入最大限制是130并且必须是2的幂次方
loadFactor 是装载因子主要目的是用来确认table 数组是否需要动态
扩展默认值是0.75比如table 数组大小为 16装载因子为 0.75
时threshold 就是12当 table 的实际大小超过 12时table就需要
动态扩容
扩容时调用 resize() 方法将 table 长度变为原来的两倍并且根据
新的容量计算新的数据索引值
hashMap 在JDK1.8跟1.7的区别chm在JDK1.8跟1.7的区别
1.7采用数组单链表1.8在单链表超过8并且数组长度超过64时单1.7扩容时需要重新计算哈希值和索引位置1.8不重新计算哈希值而 是采用和扩容后容量进行操作来计算新的索引位置。1.7插入元素到单链表中采用头插入法1.8采用的是尾插入法。1.7重 新计算hash值并发有闭环链表风险
chm 上述hashMap的变更也是chm的变更还有锁
1.7采用分段锁的机制锁住的是一个segment数组采用重入锁
ReentrantLock重入锁
1.8.采用Node CAS Synchronized来保证并发安全,取消类 Segment 直接锁entry
为什么取消重入锁采用synchronized?
粒度降低了
JVM 开发团队没有放弃 synchronized而且基于 JVM 的 synchronized
优化空间更大更加自然。
在大量的数据操作下对于 JVM 的内存压力基于 API 的
ReentrantLock 会开销更多的内存。
