1.JDK成长记7：3张搞懂HashMap底层原理！源码
2.map和字典的源码区别
3.Java之五种遍历Map集合的方式
4.concurrenthashmap1.8源码如何详细解析?

JDK成长记7：3张搞懂HashMap底层原理！

       一句话讲，源码 HashMap底层数据结构，源码JDK1.7数组+单向链表、源码JDK1.8数组+单向链表+红黑树。源码病毒复制源码

       在看过了ArrayList、源码LinkedList的源码底层源码后，相信你对阅读JDK源码已经轻车熟路了。源码除了List很多时候你使用最多的源码还有Map和Set。接下来我将用三张图和你一起来探索下HashMap的源码底层核心原理到底有哪些？

       首先你应该知道HashMap的核心方法之一就是put。我们带着如下几个问题来看下图：

       如上图所示，源码put方法调用了putVal方法，源码之后主要脉络是源码：

       如何计算hash值？

       计算hash值的算法就在第一步，对key值进行hashCode()后，源码对hashCode的值进行无符号右移位和hashCode值进行了异或操作。为什么这么做呢？其实涉及了很多数学知识，简单的说就是尽可能让高和低位参与运算，可以减少hash值的冲突。

       默认容量和扩容阈值是多少？

       如上图所示，很明显第二步回调用resize方法，获取到默认容量为，这个在源码里是1<<4得到的，1左移4位得到的。之后由于默认扩容因子是0.，所以两者相乘就是扩容大小阈值*0.=。之后就分配了一个大小为的webapp源码 下载Node[]数组，作为Key-Value对存放的数据结构。

       最后一问题是，如何进行hash寻址的？

       hash寻址其实就在数组中找一个位置的意思。用的算法其实也很简单，就是用数组大小和hash值进行n-1&hash运算，这个操作和对hash取模很类似，只不过这样效率更高而已。hash寻址后，就得到了一个位置，可以把key-value的Node元素放入到之前创建好的Node[]数组中了。

       当你了解了上面的三个原理后，你还需要掌握如下几个问题:

       还是老规矩，看如下图：

       当hash值计算一致，比如当hash值都是时，Key-Value对的Node节点还有一个next指针，会以单链表的形式，将冲突的节点挂在数组同样位置。这就是数据结构中所提到解决hash 的冲突方法之一：单链法。当然还有探测法+rehash法有兴趣的人可以回顾《数据结构和算法》相关书籍。

       但是当hash冲突严重的时候，单链法会造成原理链接过长，导致HashMap性能下降，因为链表需要逐个遍历性能很差。所以JDK1.8对hash冲突的算法进行了优化。当链表节点数达到8个的时候，会自动转换为红黑树，色播源码自平衡的一种二叉树，有很多特点，比如区分红和黑节点等，具体大家可以看小灰算法图解。红黑树的遍历效率是O(logn)肯定比单链表的O(n)要好很多。

       总结一句话就是，hash冲突使用单链表法+红黑树来解决的。

       上面的图，核心脉络是四步，源码具体的就不粘出来了。当put一个之后，map的size达到扩容阈值，就会触发rehash。你可以看到如下具体思路：

       情况1:如果数组位置只有一个值：使用新的容量进行rehash，即e.hash & (newCap - 1)

       情况2:如果数组位置有链表，根据 e.hash & oldCap == 0进行判断，结果为0的使用原位置，否则使用index + oldCap位置,放入元素形成新链表，这里不会和情况1新的容量进行rehash与运算了，index + oldCap这样更省性能。

       情况3：如果数组位置有红黑树，根据split方法，同样根据 e.hash & oldCap == 0进行树节点个数统计，如果个数小于6，将树的结果恢复为普通Node，否则使用index + oldCap，intellij查看源码调整红黑树位置，这里不会和新的容量进行rehash与运算了，index + oldCap这样更省性能。

       你有兴趣的话，可以分别画一下这三种情况的图。这里给大家一个图，假设都出发了以上三种情况结果如下所示：

       上面源码核心脉络，3个if主要是校验了一堆，没做什么事情，之后赋值了扩容因子，不传递使用默认值0.，扩容阈值threshold通过tableSizeFor(initialCapacity);进行计算。注意这里只是计算了扩容阈值，没有初始化数组。代码如下：

       竟然不是大小*扩容因子？

       n |= n >>> 1这句话，是在干什么？n |= n >>> 1等价于n = n | n >>>1; 而|表示位运算中的或，n>>>1表示无符号右移1位。遇到这种情况，之前你应该学到了，如果碰见复杂逻辑和算法方法就是画图或者举例子。这里你就可以举个例子：假设现在指定的容量大小是,n=cap-1=，那么计算过程应该如下：

       n是int类型，java中一般是4个字节，位。所以的二进制： 。

       最后n+1=，源码屋vip方法返回，赋值给threshold=。再次注意这里只是计算了扩容阈值，没有初始化数组。

       为什么这么做呢？一句话，为了提高hash寻址和扩容计算的的效率。

       因为无论扩容计算还是寻址计算，都是二进制的位运算，效率很快。另外之前你还记得取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。即 hash%size = hash & (size-1)。这个前提条件是除数是2的幂次方。

       你可以再回顾下resize代码，看看指定了map容量，第一次put会发生什么。会将扩容阈值threshold，这样在第一次put的时候就会调用newCap = oldThr;使得创建一个容量为threshold的数组，之后从而会计算新的扩容阈值newThr为newCap*0.=*0.=。也就是说map到了个元素就会进行扩容。

       除了今天知识，技能的成长，给大家带来一个金句甜点，结束我今天的分享：坚持的三个秘诀之一目标化。

       坚持的秘诀除了上一节提到的视觉化，第二个秘诀就是目标化。顾名思义，就是需要给自己定立一个目标。这里要提到的是你的目标不要定的太高了。就比如你想要增加肌肉，给自己定了一个目标，每天5组，每次个俯卧撑，你看到自己胖的身形或者海报，很有刺激，结果开始前两天非常厉害，干劲十足，特别奥利给。但是第三天，你想到要个俯卧撑，你就不想起床，就算起来，可能也会把自己撅死过去......其实你的目标不要一下子定的太大，要从微习惯开始，比如我媳妇从来没有做过俯卧撑，就让她每天从1个开始,不能多，我就怕她收不住，做多了。一开始其实从习惯开始，先变成习惯，再开始慢慢加量。量太大养不成习惯，量小才能养成习惯。很容易做到才能养成，你想想是不是这个道理？

       所以，坚持的第二个秘诀就是定一个目标，可以通过小量目标，养成微习惯。比如每天你可以读五分钟书或者5分钟成长记，不要多，我想超过你也会睡着了的.....

       最后，大家可以在阅读完源码后，在茶余饭后的时候问问同事或同学，你也可以分享下，讲给他听听。

map和字典的区别

       第一个区别就先来说说继承关系吧

       如果你baidu一下，会发现网上的大致说法与“由于Java发展的历史原因。Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现。”相同。

       这种说法没有错，但是不够准确，特别是对于我们这种大众菜鸟来说，如果不去深究的话，可能就会造成一些理解上的差异。简单的认为Hashtable没有继承Map接口。

       我们可以参考一下最新的JDK1.6的源码，看看这两个类的定义：

       public class Hashtable<K,V>extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { …}

       public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { …}

       可以看到hashtable也是继承了Map接口。

       它们的不同是Hashtable（since JDK1.0）就继承了Dictionary这个抽象类，

       而HashMap（since JDK1.2）继承的则是AbstractMap这个抽象类。

       第二个区别我们从同步和并发性上来说说它们两个的不同。

       可以通过这两个类得源码来分析，Hashtable中的主要方法都做了同步处理，而HashMap则没有。

       可以说Hashtable在默认情况支持同步，而HashMap在默认情况下是不支持的。

       我们在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。

       对HashMap的同步处理可以使用Collections类提供的synchronizedMap静态方法；

       或者直接使用JDK5.0之后提供的java.util.concurrent包里的ConcurrentHashMap类。

Java之五种遍历Map集合的方式

       在Java中，所有的Map类型都实现了Map接口，因此我们可以采用以下几种方法来遍历Map集合。本文将详细介绍五种遍历方式，并通过示例代码进行详细说明，以供读者参考学习。

       方式一：通过Map.keySet使用iterator遍历

       方式二：通过Map.entrySet使用iterator遍历

       方式三：通过Map.keySet遍历

       方式四：通过For-Each迭代entries，使用Map.entrySet遍历

       方式五：使用lambda表达式forEach遍历

       forEach 源码

       从源码中可以看出，这种方式在传统的迭代方式上增加了一层壳，使得代码更加简洁。（开发中推荐使用）

       总结

       推荐使用entrySet遍历Map类集合KV（文章中的第四种方式），而不是keySet方式进行遍历。keySet实际上是遍历了两次，第一次是将key转换为Iterator对象，第二次是从hashMap中取出key所对应的value值。而entrySet只是遍历了一次，就将key和value都放在了entry中，效率更高。values()返回的是V值集合，是一个List集合对象；keySet()返回的是K值集合，是一个Set集合对象；entrySet()返回的是K-V值组合集合。如果是JDK8，推荐使用Map.forEach方法（文章中的第五种方式）。

concurrenthashmap1.8源码如何详细解析?

       ConcurrentHashMap在JDK1.8的线程安全机制基于CAS+synchronized实现，而非早期版本的分段锁。

       在JDK1.7版本中，ConcurrentHashMap采用分段锁机制，包含一个Segment数组，每个Segment继承自ReentrantLock，并包含HashEntry数组，每个HashEntry相当于链表节点，用于存储key、value。默认支持个线程并发，每个Segment独立，互不影响。

       对于put流程，与普通HashMap相似，首先定位至特定的Segment，然后使用ReentrantLock进行操作，后续过程与HashMap基本相同。

       get流程简单，通过hash值定位至segment，再遍历链表找到对应元素。需要注意的是，value是volatile的，因此get操作无需加锁。

       在JDK1.8版本中，线程安全的关键在于优化了put流程。首先计算hash值，遍历node数组。若位置为空，则通过CAS+自旋方式初始化。

       若数组位置为空，尝试使用CAS自旋写入数据；若hash值为MOVED，表示需执行扩容操作；若满足上述条件均不成立，则使用synchronized块写入数据，同时判断链表或转换为红黑树进行插入。链表操作与HashMap相同，链表长度超过8时转换为红黑树。

       get查询流程与HashMap基本一致，通过key计算位置，若table对应位置的key相同则返回结果；如为红黑树结构，则按照红黑树规则获取；否则遍历链表获取数据。