前言

本文源码采用jdk1.8

Java集合是Java提供的工具包，包含了常用的数据结构：集合、链表、队列、栈、数组、映射等。Java集合工具包位置是java.util.*，Java集合主要可以划分为4个部分：List列表、Set集合、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections)。

原本我是打算先写Collection下的Set集合的，结果看了源码发现：Set集合实际上底层就是HashMap来构建的！

所以，就先介绍Map集合和红黑树吧！

一、Map简介

前面我们学习的Collection叫做集合，它可以快速查找现有的元素。

Map 是一组成对的“键值对”对象，允许使用键 (key) 来查找值 (value)。它提供了一个映射表，可以通过某个对象来查找另一个对象。它也被称作关联数组，因为它将某些对象与另外一些对象关联在一起

Map基本特性：

以 key-value 键值对的形式存储数据，可通过 key 来查找 value
键唯一，值不唯一。即一个键只能映射一个值，一个值可以对应多个键
无法保证元素的存入顺序

映射的模型图是这样的：

那为什么我们需要这种数据存储结构呢？举个例子

生活中，一个身份证号证明一个人的身份，一一对应

下面用红色框框圈住的就是Map值得关注的子类：

这只是集合包下的，是线程不安全的，在并发包下还有线程安全的ConcurrentHashMap，下面我会介绍的~

二、散列表介绍

散列表是一种不在意元素的顺序，能够快速地查找元素的数据结构

散列表为每个对象通过哈希函数计算出一个整数，称为散列码。根据这些计算出来的整数(散列码)保存在对应的位置上！

在Java中，散列表用的是链表数组实现的，每个列表称之为桶。每个桶都可能会出现被别的元素占用的情况，即此时hashCode散列码相同，会存储在同一个位置，这个现象叫散列冲突。

开放寻址：核心思想是如果出现了散列冲突，我们就重新探测一个空闲的位置，开放寻址法解决方案有线性探测法、二次探测、双重散列等方案。
链表法：散列表中，每个“桶（bucket）”都会对应一个条链表，在查找时先听过hash(key)找到位置，然后遍历链表找到对应元素

三、HashMap介绍

Hashmap定义：

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

Hashmap简介：

HashMap是基于Map接口的Key-Value的集合，允许使用null值和null键，但不保证映射的顺序，特别是它不保证该顺序恒久不变。HashMap在底层将Key-Value当成一个整体Entry来处理。
底层使用数组实现，数组中每一项是单向链表，即数组和链表的结合体，链表长度大于一定阈值时，链表转换为红黑树。
在链表和数组中可以说是有序的(存储的顺序和取出的顺序是一致的)，但同时也带来缺点：想要获取某个元素便要访问所有的元素直到找到为止（List中知道具体位置可以直接访问）。
散列表HashMap会为每一个Key计算出哈希值，即散列码，根据这些散列码保存在对应的位置上。

Hashmap核心函数：

我们先来看下属性和默认值~

注意：初始容量太高和负载因子太低的话，遍历效率不太好。

构造函数

这里我们需要注意第一个构造函数，传入初始容量和负载因子，如果初始容量小于0抛出异常，大于最大容量MAXIMUM_CAPACITY则置为MAXIMUM_CAPACITY；如果不是这两个会进入tableSizeFor()方法，一起来看看：

  int n = cap - 1;

为什么要有第一步的减一操作？目的是为了防止传入的cap已经是2的幂，如果没有执行这个减一操作，返回的将是这个cap(传入是2的幂)的2倍，不太懂？请继续读下去。

     n |= n >>> 1;
     n |= n >>> 2;
     n |= n >>> 4;
     n |= n >>> 8;
     n |= n >>> 16;

如果传入的cap为0，经过减一和后面几次的无符号移动之后会一直是0，最后返回capacity是1；主要考虑cap不为0的情况，由于cap不为0，则n的二进制中总会有一个bit位为1，我们只考虑最高bit位为1。

第一步n >>> 1是无符号右移1位，再做或运算，使得二进制中的最高位和紧邻的右边一位也是1（0000 11## #### ####这种格式）。

第二步n >>> 2是无符号右移两位，再做或操作，第一步已经将最高位和其临位变为1，这一步则会将从高位开始的4位都变成1（0000 1111 #### ####这种格式）。

第三步n >>> 4是无符号右移4位，再做或操作，同样的道理，经过这一步之后从最高位开始后面的8位都变为1（0000 1111 1111 ####这种格式）。

以此类推，容量最大是32位正数，经过n |= n >>> 16之后最多也就32个1（1+2+4+8+16=31，但是别忘了开始的那一位），此时已经是负数了。在执行tableSizeFor之前，对initialCapacity做了判断，如果大于MAXIMUM_CAPACITY(2 ^ 30)，则取MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY(2 ^ 30)，会执行移位操作。所以这里面的移位操作之后，最大30个1，不会大于等于MAXIMUM_CAPACITY。30个1，加1之后得2 ^ 30）。

举个例子~

现传入一个数cap为11，n=cap-1为10，则n二进制为0000 1010。

n |= n >>> 1：n >>> 1变为0000 0101，n或n>>> 1变为0000 1101，n即此值；

n |= n >>> 2：n >>> 2变为0000 0011，n或n>>> 2变为0000 1111，n即此值；

n |= n >>> 4：n >>> 4变为0000 0000，n或n>>> 4变为0000 1111，n不变；

n |= n >>> 8：n >>> 8变为0000 0000，n或n>>> 8变为0000 1111，n不变；

n |= n >>> 16：n >>> 16变为0000 0000，n或n>>> 16变为0000 1111，n不变；

看完上面可能会感到奇怪的是：为啥是将2的整数幂的数赋给threshold？

threshold这个成员变量是阈值，决定了是否要将散列表再散列。它的值应该是：capacity * load factor才对的。其实这里仅仅是一个初始化，当创建哈希表的时候，它会重新赋值的。

内部类Node

put()方法：放入Key-Value键值对

内部包含hash()函数和putVal()函数，hash函数用来求哈希值，putVal()函数用来将key-value键值对放入集合map，我们先看hash()函数：

这里直接将key的哈希值返回不就好了，为什么还要做异或运算？我们进入putVal()函数看：

这里是根据key的哈希值来保存在散列表中的，刚刚上面的key原哈希值和高16位异或运算得到的新哈希值便是用来计算保存在散列表中位置的。

我们表的默认初始容量是16，要放到散列表中即为0-15的位置，即tab[i = (n - 1) & hash]这里。我们可以发现在做&运算的时候，仅仅是后4位有效（容量32则是后5位有效，依次类推），那如果我们key的哈希值高位变化很大，低位变化很小，直接拿过去做&运算，这就会导致计算出来的Hash值相同的很多。

而设计者将key的哈希值的高位也做了运算(与高16位做异或运算，使得在做&运算时，此时的低位实际上是高位与低位的结合)，这就增加了随机性，减少了碰撞冲突的可能性！

详细理解下HashMap的put()过程吧：

put源码中还可以挖掘更多细节，比如putTreeVal()在树中插入节点、treeifyBin()转变树结构等，感兴趣的可以多多研究，关于红黑树结构及原理，文章下面会介绍。

resize()方法：扩容机制

当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作。

很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。

get()：根据Key获取Value

hash()计算key对应的哈希值，上面介绍过，我们看getNode()：

这里只讲解了最基本的函数的源码，很多常用函数我们完全没必要全部都阅读源码，学会使用，了解原理即可，但是阅读源码是一种优秀的习惯，大家还是要习惯性的养成。

三、红黑树介绍

HashMap底层的链表达到一定长度时并且数组满足长度时，会将链表转变成红黑树结构。各种常见的树的用途：

二叉查找树

在介绍红黑树之前我们要先理解二叉查找树的结构：

如上图就是一个二叉查找树。二叉查找树有如下几条特性

1、果子树上所有结点的值均小于或等于它的根结点的值

2、右子树上所有结点的值均大于或等于它的根结点的值

3、左、右子树也分别为二叉排序树

那既然他名字中是有“查找”的，那么他是怎么查找的呢？比如我们要查找10这个元素，查找过程为：首先找到根节点，然后根据二叉查找树特性，我们知道要查找的10>9所以是在根节点的右边去查找，找到13，10<13,所以接着在13的左边找，找到11,10<11,继续在11的左边查找，这样就找到了10，这其实就是二分查找的思想。最后我们要查出结果所需的最大次数就是二叉树的高度！

二分查找的思想，找到数组的中间位置的元素v，将数组分成>v和<v两部分，然后将v和要查找的数据进行一个比较，如果大于v那么就在>v的部分再次进行二分查找，否则就在<v的部分进行二分查找，直到找到对应的元素。

那既然要查出结果所需的最大次数就是二叉树的高度，那这个高度会不会有时候很长呢？比如我们依次插入根节点为9如下节点：7,6,5,4,3,2,1。依照二叉查找树的特性，结果会变成什么样呢？7,6,5,4,3,2,1一个比一个小，那么就会成一条直线，也就是成为了线性的查询，时间复杂度变成了O（N）级别。为了解决这种情况，该红黑树出场了。

红黑树：自平衡二叉树，带有颜色属性的二叉查找树，颜色是红色或者黑色

红黑树为了保持平衡，还有制定一些约束，遵守这些约束的才能叫做红黑树：

节点是红色或黑色。
根节点是黑色。
每个叶子节点都是黑色的空节点（NIL节点）。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(每一条树链上的黑色节点数量（称之为“黑高”）必须相等)。

红黑树那么多规则，那么再插入和删除元素会不会破坏红黑树的规则呢？答案是肯定的，红黑树通过“变色”和“旋转”来维护红黑树的规则，变色就是让黑的变成红的，红的变成黑的，旋转又分为“左旋转”和“右旋转”。

HashMap注意问题

HashMap底层到底在何时转换成红黑树？

很多博文中只提到了链表长度大于八的条件，实际上是需要两个条件的：

1、链表长度大于8，官方源码如下：

2、当满足条件1以后调用treeifyBin方法转化红黑树。该方法中，数组如果长度小于MIN_TREEIFY_CAPACITY（64）就选择扩容，而不是转化为红黑树。

哈希冲突是什么？如何解决？

哈希表是基于数组的一种存储方式，由哈希函数和数组构成。当存储数据时，先根据函数计算出数据的地址，然后放入数组的特定地址位置里，这个函数是哈希函数。

哈希冲突很容易理解，其实就是指的是这个计算出来的位置被别人占用了的时候如何处理。举个例子，上面的HashMap是通过哈希值来寻找数组位置的，我存储(key1-va1)(key2-va2)两个键值对，若key1计算的哈希值是0，在数组第一个位置存储，然后计算key2的哈希值也是0，这时这个位置有key1了，总不能把key2覆盖key1吧，两个键值对的key值不一样，不符合。如何处理这种情况？

1、开放地址法：开放地址之线性探测法，出现Hash冲突后，依次查询这个键值后面的地址，找到一个空的或者全部查完没找到。开放地址之二次探查法，出现冲突后，对这个键值后面的地址或者前面的地址进行平方后查询

2、链表法：把哈希冲突冲突的元素都放在一个链表中，但是链表的长度不能太长，越长效率越慢。（HashMap采用这个方法，但是链表有可能转化成红黑树）

3、建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表，比较粗暴

HashMap在多线程中存在的问题？如何解决？

网上很多博客讲述的是HashMap中的死循环问题，其实HashMap中存在很多并发问题，因为HashMap设计的目的和应用场所就没有考虑并发场景。HashMap 的设计目标是简洁高效，没有采取任何措施保证 put、remove 操作的多线程安全。在各种操作的过程中都有可能存在多线程并发问题，在这些复杂的逻辑中有任何一个线程改变了散列表的结构就有可能出现并发问题。

在jdk1.8之前HashMap经常会出现死循环导致CPU利用率较高等问题，在jdk1.8及之后改善了这个问题，但是不代表不存在并发问题，多线程put时可能导致元素的丢失，put非null元素后get出来的却是null等情况都有可能会出现。

在多线程环境下如何使用呢~

1、Collections.synchronizedMap(new HashMap<String , Object>())：可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力。底层是对每一个方法使用锁，让每一个方法的操作都具有原子性，更具有安全性

2、Hashtable：遗留类，承自Dictionary类，并且是线程安全的，了解即可

3、ConcurrentHashMap ：ConcurrentHashMap 与 HashMap 相比，在高效率的基础上添加了对多线程安全的保证。下面的文章会单独拎出来讲解~

HashMap的遍历？

1、遍历HashMap的键值对：根据entrySet()获取HashMap的“键值对”的Set集合，通过Iterator迭代器遍历“第一步”得到的集合

    // map中的key是String类型，value是String类型
    String value = null;
    Iterator iter = map.entrySet().iterator();
    while(iter.hasNext()) {
        Map.Entry entry = (Map.Entry)iter.next();
        // 获取key
        key = (String)entry.getKey();
        // 获取value
        value = entry.getValue();
    }

2、遍历HashMap的键：根据keySet()获取HashMap的“键”的Set集合，通过迭代器遍历得到集合

    // map中的key是String类型，value是String类型
    String key = null;
    String value = null;
    Iterator iter = map.keySet().iterator();
    while (iter.hasNext()) {
            // 获取key
        key = (String)iter.next();
            // 根据key，获取value
        value = map.get(key);
    }

3、遍历HashMap的值：根据values()获取HashMap的“值”的集合，通过Iterator迭代器遍历“第一步”得到的集合

    // map中的key是String类型，value是String类型
    String value = null;
    Collection c = map.values();
    Iterator iter= c.iterator();
    while (iter.hasNext()) {
        value = iter.next();
    }

絮叨叨

你知道的越多，你不知道的也越多。

建议：集合之HashMap，面试之宠儿，工作之利器，非学不可，我是兄说的！

玖叶教程网

前端编程开发入门

Java中的Map集合、散列表、红黑树介绍

前言

一、Map简介

二、散列表介绍

三、HashMap介绍

三、红黑树介绍

HashMap注意问题

絮叨叨