关键词：
主要记录hashMap的一些基本操作源码实现原理以及多线程情况下get()操作的死循环引发原因
一、hashMap简介
1.hashMap集合的主要属性及方法
（默认初始化容量）DEFAULT_INITIAL_CAPACITY = 16
（默认最大容量）MAXIMUM_CAPACITY = 1 << 30
（默认加载因子）DEFAULT_LOAD_FACTOR = 0.75f
（Entry数组）Entry[] table
（Entry实例的数量）size
put(K key, V value)方法
get(K key)方法
2.hashMap结构及操作（new方法 put方法 get方法）：
数组+链表的形式，以实例Entry<K,V>的形式存储
a.new方法：
从图中我们可以看到一个hashmap就是一个数组结构，当新建一个hashmap的时候，就会初始化一个数组（默认长度16，加载因子0.75）：
源码：
/** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
例：table[0],table[1],table[2],table[3]...table[15]
b.put方法
当执行put方法时，会先计算key值的hash值，将hash值和（数组长度减一得到的值）进行与运算，得到数组下标值，将键值对以Entry实例的形式放入数组中：
put方法源码：
/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); //计算key的hash值 int i = indexFor(hash, table.length); //根据hash值和数组长度计算数组位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { //如遇到hash冲突（e不为空），遍历链表 Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如遇到key值相等的，进行替换 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } }
indexFor方法源码(计算数组下标)，方法和简单，就把key值的hash值和数组长度-1做了与运算
/** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }
例：添加键值对为7，77，调用方法put(7，77)，7经过计算后的hash值为7（可自行验证，不多做解释），调用indexFor方法进行与运算：0111&1111=0111，下标值为7。
table[0],table[1],table[2],table[3]...table[7]=7...table[15]
再添加元素8，put(8，88)，15经过计算后的hash值仍为8，1000&1111=1000，下标值为8。
table[0],table[1],table[2],table[3]...table[7]=7，table[8]=8...table[15]
再添加元素22，put(22，2222)，22经过计算后的hash值为23，10111&1111=7，下标值为7，此时由于table[7]中已存在元素(7，77)，产生hash冲突，hashMap会将23放入table[7]中，再执行(e=e.next)，以链表形式将next指针指向之前的元素(7，77)，如下图所示：
当Entry的个数超过最大容量值*负载因子(16*0.75=12)时，hashMap会进入resize方法，重新创建一个数组并扩容为原来的2倍，再将数据拷贝到新的数组中，如下图所示：
resize方法源码：
/** * Rehashes the contents of this map into a new array with a * larger capacity. This method is called automatically when the * number of keys in this map reaches its threshold. * * If current capacity is MAXIMUM_CAPACITY, this method does not * resize the map, but sets threshold to Integer.MAX_VALUE. * This has the effect of preventing future calls. * * @param newCapacity the new capacity, MUST be a power of two; * must be greater than current capacity unless current * capacity is MAXIMUM_CAPACITY (in which case value * is irrelevant). */ void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); }
c.get方法：
当执行get方法时，根据key值的hash值，得到数组下标，将数组内的entry的key值与get中的参数做对比(如该数组内有链表，则会继续遍历链表)，若hash相等且equals，则返回。
get方法源码：
/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it‘s also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */ public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); //计算hash值 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { //这里遍历数组中的链表，若找到key值相等的，则返回 Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
二、Java多线程下的HashMap死循环
摘自：http://blog.csdn.net/xiaohui127/article/details/11928865
正常的ReHash的过程
画了个图做了个演示。
- 我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。
- 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。
- 接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程
并发下的Rehash
1）假设我们有两个线程。我用红色和浅蓝色标注了一下。
我们再回头看一下我们的 transfer(resize方法中)代码中的这个细节：
do { Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了 int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null);
而我们的线程二执行完成了。于是我们有下面的这个样子。
注意，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。
2）线程一被调度回来执行。
- 先是执行 newTalbe[i] = e;
- 然后是e = next，导致了e指向了key(7)，
- 而下一次循环的next = e.next导致了next指向了key(3)
3）一切安好。
线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。
4）环形链接出现。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)
注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
于是，当我们的线程一调用到，HashTable.get(11)时，悲剧就出现了——Infinite Loop。
多线程下hashmap的死循环问题(代码片段)
多线程下[HashMap]的问题：1、多线程put操作后，get操作导致死循环。2、多线程put非NULL元素后，get操作得到NULL值。3、多线程put操作，导致元素丢失。本次主要关注[HashMap]-死循环问题。为何出现死循环？大家都知道，HashMap采用链... 查看详情
深入理解java集合系列三：hashmap的死循环解读
由于在公司项目中偶尔会遇到HashMap死循环造成CPU100%，重启后问题消失，隔一段时间又会反复出现。今天在这里来仔细剖析下多线程情况下HashMap所带来的问题：1、多线程put操作后，get操作导致死循环。2、多线程put非null元素后，... 查看详情
jdk1.7源码分析集合hashmap的死循环(代码片段)
前言在JDK1.7&1.8源码对比分析【集合】HashMap中我们遗留了一个问题：为什么HashMap在调用resize() 方法时会出现死循环？这篇文章就通过JDK1.7的源码来分析并解释这个问题。如下，并发场景下使用HashMap造成RaceCondition，从而导... 查看详情
关于android中为什么主线程不会因为looper.loop()里的死循环卡死？引发的思考，事实可能不是一个epoll那么简单。
(转载请务必标明出处：http://www.cnblogs.com/linguanh/，本文出自:【林冠宏(指尖下的幽灵)的博客】)前序 本文将会把一下三个问题阐述清楚以及一个网上的普遍观点的补充： 1，安卓APP启动过程，对于Activity的onCreate等生命... 查看详情
hashmap为什么线程不安全？(代码片段)
...1.8中的数据覆盖举例说明总结解决线程不安全线程不安全HashMap的线程不安全体现在会造成死循环、数据丢失、数据覆盖等问题。其中死循环和数据丢失是在JDK1.7中出现的问题，在JDK1.8中已经得到解决，但是1.8中仍会有数... 查看详情
methods下的死循环
使用Vue框架时，data里的数据的改变会导致整个页面刷新一遍。<divid="app"> <div>num</div> <div>getFullName()</div> <buttonv-on:click="num++">add</button> </div> <scrip 查看详情
hashmap，hashtable，concurrenthashmap多线程下的比较（持续更新）
1.hashMap多线程下put会造成死循环，主要是扩容时transfer方法会造成死循环。http://blog.csdn.net/zhuqiuhui/article/details/51849692（具体原因）2.hashTable，使用synchornized保证线程安全，线程竞争竞争激烈的情况下，效率低下。当一下线程访问h... 查看详情
hashmap源码剖析
HashMap简介 HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。 HashMap是非线程安全的，只是用于单线程环境下，多线程... 查看详情
hashmap源码剖析
HashMap简介 HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。 HashMap是非线程安全的，只是用于单线程环境下，多线程环境... 查看详情
jdk源码解析---hashmap源码解析
HashMap简介HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurren... 查看详情
高并发下的hashmap为什么会死循环
作者| tech-bus.七十一来源| 程序员巴士前言 HashMap并发情况下产生的死循环问题在JDK1.7及之前版本是存在的，JDK1.8通过增加loHead头节点和loTail尾节点进行了修复，虽然进行了修复，但是如果涉及到并发情况下需要... 查看详情
concurrenthashmap源码分析
一、ConcurrentHashMap出现的原因 我们之前学过HashMap，也知道HashMap不是线程安全的，在多线程环境下，HashMap的put方法有可能引起死循环。于是HashTable这个类出现，它在大量的方法前都加了内置锁Synchronized，这就保证了它的线程... 查看详情
hashmap为啥不安全？
原因：JDK1.7中，由于多线程对HashMap进行扩容，调用了HashMap#transfer()，具体原因：某个线程执行过程中，被挂起，其他线程已经完成数据迁移，等CPU资源释放后被挂起的线程重新执行之前的逻辑，数据已经被改变，造成死循环、... 查看详情
记一次线上故障--hashmap在多线程条件下运行造成cpu100%(代码片段)
...般都是程序编写不规范，引发的死循环造成。为什么HashMap的组装数据及调用会造成死循环呢，这里需要从HashMap的底层数据结构分析原因。一.JDK1.8HashMap的数据结构数组+链表+红黑树二.结合问题代码与HahsMap底层结构... 查看详情
轻松把玩httpclient之封装httpclient工具类，单线程调用及多线程批量调用测试(代码片段)
...voidtestOne()throwsHttpProcessException System.out.println("--------简单方式调用（默认post）--------"); Stringurl="http://tool.oschina.net/"; //简单调用 Stringresp=HttpClientUtil.send(url); System.out.println("请求结果内容长度：... 查看详情
hashmap的resezi方法中尾部遍历出现死循环问题tailtraversing(多线程)(代码片段)
一、背景介绍：在看HashMap源码是看到了resize()的源代码，当时发现在将old链表中引用数据复制到新的链表中时，发现复制过程中时，源码是进行了反序，此时是允许反序存储的，同时这样设计的效率要高，不用采用尾部插入，每... 查看详情
concurrenthashmap源码解析(代码片段)
ConcurrentHashMap源码解析ConcurrentHashMap是什么？它是对HashMap线程安全性的增强类，保证了Map对象在多线程环境下的读写的线程安全性。在使用方法上和HashMap保持一致，都是Map接口的实现类。类结构核心数据结构核心数据结构和HashMa... 查看详情
hashmap源码学习
史上最详细的JDK1.8HashMap源码解析_程序员囧辉-CSDN博客_hashmap1.8可能是史上最详细的HashMap源码解析。https://blog.csdn.net/v123411739/article/details/78996181疫苗：JavaHashMap的死循环|酷壳-CoolShellhttps://coolshell.cn/articles/9606.html什么？HashMa... 查看详情