一、HashMap

介绍 https://blog.csdn.net/weixin_39819661/article/details/111249224

1、介绍

HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)而存在的（“拉链法”解决冲突）.JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。
补充：将链表转换成红黑树前会判断，即使阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树。而是选择进行数组扩容。
这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡 。同时数组长度小于64时，搜索时间相对要快些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于64时，链表才转换为红黑树。具体可以参考 treeifyBin方法。
当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于8并且数组长度大于64时，链表转换为红黑树时，效率也变的更高效。

小结： 1.存取无序的 2.键和值位置都可以是null，但是键位置只能是一个null 3.键位置是唯一的，底层的数据结构控制键的 4.jdk1.8前数据结构是：链表 + 数组 jdk1.8之后是 ： 链表 + 数组 + 红黑树 5.阈值(边界值) > 8 并且数组长度大于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。 6.HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。

2、HashMap底层数据结构

在JDK1.8 之前 HashMap 由 数组+链表 数据结构组成的。
在JDK1.8 之后 HashMap 由 数组+链表 +红黑树数据结构组成的。
image.png
image.png

  1. public class Demo01 {
  2.     public static void main(String[] args) {
  3.         HashMap<String, Integer> map = new HashMap<>();
  4.         map.put("柳岩", 18);
  5.         map.put("刘德华", 40);
  6.         map.put("杨幂", 28);
  7.         map.put("柳岩", 20);
  8.     }
  9. }

1、当创建HashMap集合对象的时候，在jDK8之前，构造方法中创建了一个长度是16的Entry[] table，来存储键值对数据。在JDK8以后不再是HashMap的构造方法底层创建数据了，是在第一次调用put方法时创建的数组，Node[] table 用来存储键值对数据的。
2、假设向哈希表中存储刘岩18数据后，根据柳岩18调用String类中重写之后的hashCode()方法计算出值，然后结合数据长度采用某种算法计算出向Node数组中存储数据的空间的索引值。如果计算出的索引空间没有数据，则直接将柳岩-18存储到数组中。

扩展 1.面试题：HashMap中hash函数是怎么实现的？还有哪些hash函数的实现方式？ 第一问：对于key的hashCode做hash操作，无符号右移16位然后做异或运算。
第二问：还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移16位异或运算效率是最高的。

什么是平方取中法？ 这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。 哈希函数 H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。

3、向哈希表中存储刘德华-40，假如刘德华计算出的hashCode方法结合数组长度计算出的索引值也是3，那么此时数组空间不是null，此时底层会比较柳岩和刘德华的hash值是否一样，如果不一致，则在此空间上划出一个节点来存储键值对刘德华-40，这种方式称为拉链法（链地址法）
4、假设向哈希表中存储柳岩-20，那么首先根据柳岩调用hashCode方法结合数组长度计算出索引肯定也是3，然后比较柳岩和已经存在的数据的hash值是否一致，如果hash值一致就会发生hash碰撞。那么底层会调用柳岩所属类String的equals方法比较两个内容是否一致，一致：则将后添加的数据的value值覆盖之前的value不一致：那么继续向下和其他数据的key进行比较，如果不相等，则划出一个节点存储数据。

hashcode一样的值，存在吗？ System.out.println(“重地”.hashCode()); System.out.println(“通话”.hashCode()); //一样的

注意：如果节点长度即链表长度大于阈值8并且数组长度大于64，则将链表变为红黑树。

常见问题： 当两个对象的hashCode相等时会怎么样？ 会产生哈希碰撞，若key值内容相同则替换旧的value，否则连接到链表后面，链表长度超过阈值8就转换为红黑树存储。 2、何时发生哈希碰撞和什么是哈希碰撞,如何解决哈希碰撞？ 只要两个元素的key计算的哈希码值相同就会发生哈希碰撞。jdk8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。 3、如果两个键的hashcode相同，如何存储键值对？ hashcode相同，通过equals比较内容是否相同。相同：则新的value覆盖之前的value不相同：则将新的键值对添加到哈希表中 4、在不断的添加数据的过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

3、引入红黑树后快在哪里

JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了 红黑树（查找时间复杂度为 O(logn)）来优化这个问题。 当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。

4、为什么使用红黑树，而不是其他树

红黑树和AVL树都是最常用的平衡二叉搜索树。
但是，两者之间有些许不同：

AVL树更加严格平衡，因此可以提供更快的査找效果。因此，对于查找密集型任务使用AVL树没毛病。 但是对于插入密集型任务，红黑树要好一些。
通常，AVL树的旋转比红黑树的旋转更难实现和调试。
红黑树更通用，再添加删除来说表现较好，AVL虽能提升一些速度但是代价太大了。

而不用B/B+树的原因：
B和B+树主要用于数据存储在磁盘上的场景，比如数据库索引就是用B+树实现的。这两种数据结构的特点就是树比较矮胖，每个结点存放一个磁盘大小的数据，这样一次可以把一个磁盘的数据读入内存，减少磁盘转动的耗时，提高效率。而红黑树多用于内存中排序，也就是内部排序。

二、ConcurrentHashMap

参考 https://blog.csdn.net/weixin_30819085/article/details/95117136
ConcurrentHashMap的大部分操作和HashMap是相同的，例如初始化，扩容和链表向红黑树的转变等。但是，在ConcurrentHashMap中，大量使用了U.compareAndSwapXXX的方法，这个方法是利用一个CAS算法实现无锁化的修改值的操作，他可以大大降低锁代理的性能消耗。这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作。因为当前线程中的值已经不是最新的值，你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁，SVN的思想是比较类似的。
简单看下ConcurrentHashMap中的put方法

  1. final V putVal(K key, V value, boolean onlyIfAbsent) {
  2.     if (key == null || value == null) throw new NullPointerException();
  3.     // 计算hash值
  4.     int hash = spread(key.hashCode());
  5.     int binCount = 0;
  6.     for (Node<K,V>[] tab = table;;) {
  7.         Node<K,V> f; int n, i, fh;
  8.         if (tab == null || (n = tab.length) == 0)
  9.             tab = initTable(); // table是在首次插入元素的时候初始化，lazy
  10.         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  11.             if (casTabAt(tab, i, null, // 如果这个位置没有值，直接放进去，由CAS保证线程安全，不需要加锁
  12.                          new Node<K,V>(hash, key, value, null)))
  13.                 break;                   // no lock when adding to empty bin
  14.         }
  15.         else if ((fh = f.hash) == MOVED)
  16.             tab = helpTransfer(tab, f);
  17.         else {
  18.             V oldVal = null;
  19.             synchronized (f) {  // 节点上锁，这里的节点可以理解为hash值相同组成的链表的头节点，锁的粒度为头节点。
  20.                 if (tabAt(tab, i) == f) {
  21.                     if (fh >= 0) {
  22.                         binCount = 1;
  23.                         for (Node<K,V> e = f;; ++binCount) {
  24.                             K ek;
  25.                             if (e.hash == hash &&
  26.                                 ((ek = e.key) == key ||
  27.                                  (ek != null && key.equals(ek)))) {
  28.                                 oldVal = e.val;
  29.                                 if (!onlyIfAbsent)
  30.                                     e.val = value;
  31.                                 break;
  32.                             }
  33.                             Node<K,V> pred = e;
  34.                             if ((e = e.next) == null) {
  35.                                 pred.next = new Node<K,V>(hash, key,
  36.                                                           value, null);
  37.                                 break;
  38.                             }
  39.                         }
  40.                     }
  41.                     else if (f instanceof TreeBin) {
  42.                         Node<K,V> p;
  43.                         binCount = 2;
  44.                         if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  45.                                                        value)) != null) {
  46.                             oldVal = p.val;
  47.                             if (!onlyIfAbsent)
  48.                                 p.val = value;
  49.                         }
  50.                     }
  51.                 }
  52.             }
  53.             if (binCount != 0) {
  54.                 if (binCount >= TREEIFY_THRESHOLD)
  55.                     treeifyBin(tab, i);
  56.                 if (oldVal != null)
  57.                     return oldVal;
  58.                 break;
  59.             }
  60.         }
  61.     }
  62.     addCount(1L, binCount);
  63.     return null;
  64. }

三、TreeMap

TreeMap是支持key排序的，作为key的对象是要实现 Comparable 接口，不然会报错，如下
底层用的 红黑树

错误示范

  1. public class House {
  2.     private String address;
  4.     public String getAddress() {
  5.         return address;
  6.     }
  8.     public void setAddress(String address) {
  9.         this.address = address;
  10.     }
  11. }
  1. public class Main {
  2.     public static void main(String[] args) {
  3.         TreeMap<House, String> map = new TreeMap<>();
  4.         House house = new House();
  5.         house.setAddress("ddddd");
  6.         map.put(house,"dddd");
  7.     }
  8. }
  10. // 报错
  11. Exception in thread "main" java.lang.ClassCastException: test.demo.House cannot be cast to java.lang.Comparable
  12.     at java.util.TreeMap.compare(TreeMap.java:1294)
  13.     at java.util.TreeMap.put(TreeMap.java:538)
  14.     at test.Main7.main(Main7.java:17)

正确示范

需要实现 Comparable接口

  1. Public class House implements Comparable<House> {
  2.     private String address;
  4.     public String getAddress() {
  5.         return address;
  6.     }
  8.     public void setAddress(String address) {
  9.         this.address = address;
  10.     }
  12.     @Override
  13.     public int compareTo(House o) {
  14.         return o.getAddress().compareTo(this.address);
  15.     }
  16. }

内部实现

调用对象的compartTo方法进行比较
image.png

四、Hashtable

put和get方法都加了synchronized，很low，性能很差
image.png
image.png