HashMap、HashTable、ConcurrentHashMap你学废了吗

素颜马尾好姑娘i 2022-11-10 05:33 226阅读 0赞

## Map ##

*  Map实现类保存的都是key-value对的
 *  key是不可重复的，key的底层是Set集合，Set的一大特性就是具有去重功能
 *  value是可重复的，value的底层是Collection集合，是允许重复数据保存的
 *  用来标识map里的每项数据

## HashMap、HashTable、ConcurrentHashMap ##

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>HashMap</th> 
   <th>HashTable</th> 
   <th>ConcurrentHashMap</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>底层</td> 
   <td>JAVA8前：数组+链表<br>JAVA8后：数组+链表+红黑树</td> 
   <td></td> 
   <td>8前：+分段锁<br>8后：+CAS+synchronized</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>数组长度默认16;存储的内容是链表的头节点<br>通过hash函数计算要存的位置，再遍历链表来获得元素，时间复杂度O(n)<br>JAVA8之后，引入红黑树，通过常量<strong>TREEIFY_THRESHOLO</strong>判断是否将链表转化为红黑树来存储，阀值&gt;8转红黑,&lt;6转链表，时间复杂度O(logn)</td> 
   <td></td> 
   <td>通过锁细粒度化优化<br>分段锁：将锁一段一段存储。segments默认长度为16，逻辑上将table数组拆分成多个子数组，每个子数组配置一把锁<br>table中每个bucket都用一把不同的锁来管理</td> 
  </tr> 
  <tr> 
   <td>构造函数</td> 
   <td>仅仅给一些变量赋值，采用Lacy_load的原则，在首次使用时才初始化</td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>函数</td> 
   <td>resize():具备初始化和扩容(2x)两个功能<br>hash():计算在数组中的位置</td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>安全性</td> 
   <td>不安全<br>多线程下调用put触发调整大小时可能会存在条件竞争，容易导致死锁</td> 
   <td>安全<br>public方法都加入了synchronized修饰符，锁住整个对象</td> 
   <td>安全：<br>锁拆的更细，首先使用无锁操作CAS插入头节点，失败就循环重试<br>若头节点已存在，则尝试获取头节点的同步锁，再进行操作</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>Collections.synchronizedMap(hashMap),就可以将它包装成一个线程安全的map实例：mutex互斥对象成员，对其中的public方法加入synchronized对mutex进行加锁。<strong>串行效率低</strong></td> 
   <td>不允许插入null键<br><strong>串行效率低</strong></td> 
   <td>不允许插入null键<br>sizeCtl标识符<br><strong>串行效率高</strong></td> 
  </tr> 
 </tbody> 
</table>

## HashMap的put方法 ##

1.  如果HashMap未被初始化过，则初始化
2.  对Key求Hash值，然后再计算下标
3.  如果没有碰撞，直接放入桶中
4.  如果碰撞了，以链表的方式链接到后面
5.  如果链表长度超过阀值8，就把链表转成红黑树
6.  如果链表长度低于6，就把红黑树转回链表
7.  如果节点已经存在就替换旧值
8.  如果桶满了（容量16\*加载因子0.75)，就需要resize(扩容2倍后重排）

## HashMap减小碰撞 ##

1.  扰动函数，使元素位置分布均匀，减小碰撞的几率
2.  使用final对象作为key，采用合适的equals()和hashCode()方法，因为final的不可变性，能缓存不同键的hashcode，可以提高获取的速度，String、Integer

## HashMap的hash ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE0MjA3NQ_size_16_color_FFFFFF_t_70][]

本质：使用 **与操作**来代替取模：

## HashMap的扩容resize ##

*  默认负载因子是0.75，当一个map填满了75%的bucket时扩容
 *  扩容：创建两倍的原来大小的数组来重新调整map的大小，并调用rehash将原来的对象放入到原来的bucket数组中
 *  假设现在是4个元素，扩容一倍，变成8个元素，那么之前的元素可能要重新计算它在数组中的位置。
    
     *  对于1来说，1在4个元素时排序在第1位，它在8个元素时还是排序在第一个。
     *  对于6来说，它在4个元素时排在第2位，在8个元素时就需要排在第6位。6从2迁移到6，移动了4个位置，刚好是扩容一倍的长度。
     *  所以，对于扩容2倍的情况来说，所有的元素，位置要么不变，要么是变化为旧的位置+扩容长度。当然，实际上这里的操作是二进制的位运算，这里只是拿十进制举例。

## ConcurrentHashMap特性 ##

*  大小控制标识符sizeCtl：
    
     *  含义：-1正在初始化，-n表示有n-1个线程正在进行扩容操作，n或0表示的是初始化或者扩容的大小
     *  volatile修饰：多线程之间可见
 *  不允许null key
 *  CAS更新需要不断重试，直到成功为止
 *  通过computeIfAbsent、compute可以构建java本地缓存

## ConcurrentHashMap的put方法 ##

1.  判断Node\[\]数组是否初始化，没有则进行初始化操作
2.  通过hash定位数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加（链表的头节点），添加失败则进入下次循环。
3.  检查到内部正在扩容，就帮助它一块扩容。
4.  如果f!=null,则使用synchronized锁住f元素（链表／红黑二叉树的头元素）
5.  如果是Node(链表结构）则执行链表的添加操作。
6.  如果是TreeNode(树型结构）则执行树添加操作。
7.  判断链表长度已经达到临界值8，当节点数超过这个值就需要把链表转换为树结构。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE0MjA3NQ_size_16_color_FFFFFF_t_70]: /images/20221023/f7e99dd8448d484298ebd34bcc21f0c4.png