Java集合（二）——Map

这是我参与8月更文挑战的第13天，活动详情查看：8月更文挑战

1、Map

• HashMap：

  • JDK 1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）；
  • JDK 1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值 (默认 8)时，将链表转化成红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间

• LinkedHashMap：LinkedHashMap 继承自 HashMap ，所以它的底层仍然是基于拉链式散列结构，即由数组和链表或红黑树组成的。另外 LinkedHashMap 在上面基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑；

• HashTable（线程安全）：

  • 数组+链表组成，数组是 HashTable 主体，链表则是主要为了解决哈希冲突而存在的；
  • 不能存储null的键或值，否则报错 NullPointException；
  • JDK 1.0 开始，比 HashMap(JDK 1.2) 早；
  • 其子类 Properties 使用更广泛

• TreeMap：红黑树（自平衡的排序二叉树）

• ConcurrentHashMap：线程安全的 HashMap，底层结构与HashMap一样，但HashMap不是它的父类。

1.1 HashMap 和 Hashtable的区别

1. 线程安全：HashMap 是非线程安全的，Hashtable是线程安全的，因为Hashtable内部的方法基本都经过synchronized修饰；（如果想要保证线程安全可以使用ConcurrentHashMap）

2. 效率：因为线程安全问题，HashMap 比Hashtable效率更高一些。另外，Hashtable基本被淘汰了，使用更多的是它的子类：Properties ;

3. 对null的支持：Hashmap可以存储null的 key 和 value，但null作为键只能有一个，并存放在数组的固定位置（数组下标为0）；Hashtable不允许有null的键和值，否则抛出异常NullPointerException；

4. 初始容量和扩容大小：

   0. 创建不指定容量初始值：HashMap 默认初始容量为16，之后每次扩容为原来的 2 倍；Hashtable默认初始容量为11，之后每次扩容为原来的 2n+1;
   1. 创建指定容量初始值：如果指定容量不为 2 的幂，HashMap 则不会使用指定容量，HashMap会扩容为2的幂次方（tableSizeFor()方法），也就是说HashMap的容量大小总是 2 的幂，这是重点下面会解释；Hashtable直接使用指定大小初始值。

5. 底层数据结构：JDK 1.8以后的HashMap在特定情况下，链表会转化成红黑树；Hashtable结构仍是 数组+链表。

2、HashMap 底层源码分析

参考链接：(非常推荐观看此视频学习，评论区也都是大神)

www.bilibili.com/video/BV1kJ…

Question

1. HashMap的扩容与插入元素的顺序关系？

   • JDK 1.7 先扩容在插入；JDK 1.8 先插入再扩容

2. HashMap 往链表里插入节点的方式

   • JDK 1.7 之前是头插法，只需要将新节点的next指向原来的头部元素就行了，查重需要另写一个方法；
   • JDK 1.8 之后是尾插法，尾插法需要遍历整个链表。在 JDK 1.8 中引入红黑树后，需要判断单链表的节点个数（超过8个转红黑树），需要遍历单链表，读取节点个数，故使用尾插法，还可以判断是否有重复节点，而不像 JDK 1.7 有另外的方法。

2.1 JDK 1.7

• Q1:为什么 HashMap 扩容大小是2的指数倍？

  indexFor(int hash,int length)通过 hash 值和 数组容量，计算存入 HashMap 位置的数组下标： hash & (length - 1)，

  一般来说，我们要计算存入数组中的下标位置，使用的是与数组长度-1进行取余。而现在换成 &运算 可以大大提高计算效率。如：

  如：当容量为 16时，计算 hash & 15

  假设 hash = 0101 0101

  hash & 15

  二进制长度都该为 32 位，这里缩写一下，举例子

  => 0101 0101

  & 0000 1111

  ---

  结果为 0101 = 5，该元素在容器位置的数组下标是 5；

  1、提高计算效率：这个算法，以length=16为例子：可以控制结果在容器容量的范围内，因为容器中数组的最大下标为length - 1的二进制，而容器大小必须限制为 2 的指数幂，这就可以使得二进制的高位都为0，低位都为1，再与 hashCode 进行 & 运算，hash的二进制高28位就没有意义了，&0就是0，所以最终的结果还是以 hash的二进制低4位与length - 1的低位计算为准，取值范围在 [0,length-1].因为往哈希表里存入数据，就是对其的容量取余，而当使用容量为2的指数倍这个机制，就可以用&运算 代替取余运算，提高计算效率；

  为什么 HashMap 扩容大小是2的指数倍？这既是成因也是结果，算法的巧妙

  2、便于动态扩容后的重新计算哈希位置时能均匀分布元素：Q5（在 JDK 1.8 才被发现并使用）

• Q2：HashMap 存值时，计算hash值：得到了 key 的hashCode，为什么还要进行右移运算、异或运算获得 hash 值？

  如 Q1 得出的结论，在计算存放位置的数组下标时，结果只与hash低位有关，hash的高位是没有参与感的，这会导致计算的数组下标重复率太高（hash冲突变多），单个节点生成的链表过程长，在get获取值时需遍历过长的链表，效率降低。

  使用右移运算、异或运算，使hash高位也参与到数组下标的计算中，使元素可以更均匀的分布在数组中，而不至于某个链表过长。

  如：hash=> 0011 1101 0101 (简写简写)

  右移 >>> 4 => 0000 0011 1101

  异或 ^ 0011 1101 0101

  ---

  提高HashMap散列性

  以上举例并没有用到 HashMap 真正的右移、异或运算方法，意思就是这么个意思。

• Q3：HashMap 的 size() 方法

  直接返回 size 属性，因为在每次put新元素时，size 都会 +1；

  并不是在调用size() 方法时，遍历整个数组的每个节点下的链表长度。

• Q4：HashMap在 put添加元素时，会进行一个覆盖的判断，当hash相等，并且key值相等时（这里的判断包括 ==，和 equals() 判断），为什么先进行 hash 判断？

  一个关于 hashCode 的规定：（hash也是通过 hashCode 计算来的嘛）

  • 两个对象相等，hashcode一定相等
  • 两个对象不等，hashcode不一定不等
  • hashcode相等，两个对象不一定相等
  • hashcode不等，两个对象一定不等

  并且， equals()一般是要有用户重写的，里面逻辑较为复杂，再根据以上几条规范，先判断hash，效率更高很多。

• Q5：HashMap 扩容之后原来元素在数组中的位置可能不变，也可能发生变化

  计算数组下标的方法：hash & (length - 1)，是与数组长度有关的，借用 Q1的例子

  如：当容量为 16时，计算 hash & 15

  假设 hash = 0101 0101

  hash & 15

  二进制长度都该为 32 位，这里缩写一下，举例子

  => 0101 0101

  & 0000 1111

  ---

  结果为 0101 = 5，该元素在容器位置的数组下标是 5；

  现在容器扩容至 32

  如：当容量为 32 时，计算 hash & 31

  假设 hash = 0101 0101

  hash & 31

  二进制长度都该为 32 位，这里缩写一下，举例子

  => 0101 0101 （其实这里第 5 位进制决定它的下标会不会改变：为0时，下标和之前一样；为1时，下标改为之前的下标+之前的容量）

  & 0001 1111

  ---

  结果为 1 0101 = 21，该元素在容器位置的数组下标是 21；

  这时可以看到 21= 5 + 16,5是没扩容前的下标，16是扩容前的容量。

  元素的位置改不改变，取决于length-1二进制最左边为1的位置，在那个位置上hash二进制是否为1。为0时，下标和之前一样；为1时，下标改为之前的下标+之前的容量（这是比较通俗的一种理解）

• Q6:HashMap的key值为null的元素，存放在数组的一个固定的位置，下标为0

2.2 JDK 1.8

实现方法与 JDK 1.7 大同小异

• Q1：为什么引入红黑树而不是其他数据结构，比如完全平衡二叉树

  既要保证put效率，也要保证get效率。

  红黑树，对于元素的查找、插入、删除，都比较不错，这是一个比较这种考虑

• Q2：较 JDK 1.7 ,JDK 1.8计算hash的方法，做了一些改动，简化了算法，但性质没有变，仍是为了提高HashMap散列性

• Q3：链表转红黑树的条件？红黑树转链表的条件

  当链表长度 >= 8，并且数组长度 >= 64，才会转化成红黑树；

  如果链表长度 >= 8，数组长度 < 64 ，则会进行扩容，不会转换为红黑树。因为数组的长度较小，应该尽量避开红黑树。因为红黑树需要进行左旋，右旋，变色操作来保持平衡，所以当数组长度小于64，使用数组加链表比使用红黑树查询速度要更快、效率要更高。

  当红黑树元素个数 <= 6时，并且是在扩容方法resize()执行时，判断红黑树长度<=UNTREEIFY_THRESHOLD(6)，转化成链表；

2.3 总结

HashMap的重要属性：（JDK 1.8）

 // 默认初始容量 16 - 必须是2的幂
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 // 最大容量
 static final int MAXIMUM_CAPACITY = 1 << 30;
 // 默认加载因子
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 // 链表转变为红黑树的阈值，当前节点元素个数 > 8 是链表变为红黑树
 static final int TREEIFY_THRESHOLD = 8;
 // 红黑树转变为链表的阈值，当前节点元素个数 < 6
 static final int UNTREEIFY_THRESHOLD = 6;    
 // 桶中结构转化为红黑树对应的table的最小大小
 static final int MIN_TREEIFY_CAPACITY = 64;
 /** 存储元素的数组，长度总是2的幂次倍
   *包括属性：
       int hash;         // key 的hash值
       K key;            // 要存入的key
       V value;          // 要存入的值
       Node<K,V> next;   // 指向下一个元素
 */
 transient Node<k,v>[] table;
 // 存放具体元素的集
 transient Set<map.entry<k,v>> entrySet;
 // 容器中元素的个数
 transient int size;
 // 加载因子
 final float loadFactor;
 // 临界值， = table.length * loadFactor.大于这个值，会进行扩容
 int threshold;
复制代码

2.4 HashMap调用put 方法，执行的过程：（JDK 1.8）

以空构造函数为例

• HashMap 为空，调用 resize()初始化容器，resize() 方法中还包含了容器的扩容机制；

• (table.length - 1) & hash [(hash=key.hashCode()) ^ (hash >>> 16)]计算该元素插入到数组的下标，并判断这个位置是否为空：

  • 如果为空，直接插入元素;

     table[i] = newNode(hash,key,value,null);
    复制代码

  • 如果不为空，继续判断：

    • if 该元素与当前位置元素的 hash、key是否相等（这里的判断包括 ==，和 equals() 判断），相等则替换掉原来的值，并return原来的值；

    • else if这个位置的元素所属的类是不是 TreeNode(树结构)，如果是则按照树结构的方式进行操作；

    • else 该元素作为一个新元素，遍历当前节点链表的所有元素

      • 查看是否有重复元素：有，则跳出遍历，不用再添加了；
      • 尾插到链表最后端，并判断：链表是否需要转化成红黑树（链表长度 >= 8 ，数组长度 >= 64；如果数组长度 < 64 则还是会进行数组扩容，因为扩容一可以增加容量，二是扩容会对链表元素的位置重新计算，重新分配位置，可以减端链表的长度。链表长度 >= 8 ，数组长度 >= 64就真的转红黑树了，因为再扩容的话内存占用就比较大了）

3、ConcurrentHashMap

线程安全的 HashMap，但它不是继承HashMap

• 数据结构

  • JDK 1.7：底层采用分段的的数组+链表实现；
  • JKD 1.8：与HashMap结构一样，数组+链表/红黑树

• 线程安全

  • JDK 1.7:ConcurrentHashMap采用分段锁技术，将整个 Hash桶 进行了分段 segment，也就是将这个大数组分成了几个小的片段segment，而且每个小的片段segment上面都有锁存在，那么在插入元素时就需要先找到应该插入到哪一个片段segment，获取segment锁，然后再在这个片段上面进行插入；ConcurrentHashMap让锁的粒度更精细一些，并发性能更好；
  • JDK 1.8：使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；

ConcurrentHahsMap 与 Hahtable的区别

1. 数据结构：

• ConcurrentHashMap：JDK 1.7采用分段的的数组+链表实现；JDK 1.8 采用 数组+链表/红黑树；
• Hashtable：数组+链表，数组为主体，链表主要为了解决哈希冲突存在。

2. 实现线程安全的方式（重要）：

• ConcurrentHashMap：

  • JDK1.7 的时候，ConcurrentHashMap （分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率；ConcurrentHashMap让锁的粒度更精细一些，并发性能更好；
  • JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。

• Hashtable（同一把锁）：使用synchronized来保证线程安全，随着数组越来越大，效率也越低下。当一个线程访问同步方法，其他线程也访问同步方式时，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。