Java中与HashMap相关的知识点

怼烎@ 2022-05-19 10:05 151阅读 0赞

![70][]

一、Java底层数据存储结构介绍

在Java语言中，数据存储方式最底层的两种结构，一种是数组，另外一种是链表。其中数组的特点是空间连续，根据下标寻址较快，但是在删除或者添加元素的时候需要较大幅度的移动，总结就是查询速度快，增删速度慢；而链表的特点是空间不连续，通过首尾指针连接前一个元素和后一个元素，因此，这样的结构寻址困难，但增删元素较快，只需修改指针的指向，总结就是查询慢，增删快。

今天的主角HashMap，它的实现就采用了Java语言中数据存储方式最底层的两种结构，也就是数组+链表的方式实现。

![70 1][]

二、关于效率

<table> 
 <thead> 
  <tr> 
   <th>&nbsp; &nbsp;</th> 
   <th>获取</th> 
   <th>查找</th> 
   <th>添加/删除</th> 
   <th>空间</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ArrayList</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>LinkedList</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
   <td>O(1)</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>HashMap</td> 
   <td>O(N/Bucket_size)</td> 
   <td>O(N/Bucket_size)</td> 
   <td>O(N/Bucket_size)</td> 
   <td>O(N)</td> 
  </tr> 
 </tbody> 
</table>

上面的表格就是对比HashMap的效率，ArrayList底层的实现结构是数组，LinkedList的底层实现结构是链表，而HashMap的底层实现结构是数组+链表，这样也就对比了数组、链表、数组+链表在各个功能上的执行效率。

三、关于HashMap<K,V>的key值

![70 2][]

从源码中我们可以看出，HashMap的key值可以是基本数据类型，也可以是引用数据类型，如果是对象，我们最好要实现两个方法，也就是Object类中的equals方法和hashCode方法，hashCode方法是用来计算存储在数组中的哪一个位置，而equals方法是用来比较数组展开的链表的元素是否相等。这样做的目的是尽量减少hash碰撞，所谓hash碰撞，也称为hash冲突，是指两个不同的key，它们计算的hash值是相同的，那么就根据equals来存到对应的链表上，如果equals值也相同，那么就会覆盖原值，如果hashCode方法实现的太不尽如人意，那么HashMap就会退化成链表了！不过JDK8中，对HashMap做了优化，如果散列表中的元素过多，会把链表转为红黑树。方法treeifyBin()就是树形化的方法：

![70 3][]

例如我们经常使用String类型做key值，String 就自个实现了equals方法和hashCode方法：

![70 4][]

![70 5][]

四、关于HashMap线程安全问题

一旦问道HashMap是否是线程安全的，我们都会异口同声的说：不是。HashMap基于效率的问题，设计的不是线程安全的，线程安全的Map有HashTable、ConcurrentHashMap、SychronizedMap，HashTable相比与HashMap是线程安全的，因为它的所有方法都加了锁，所以效率非常低，部分源码如下：

![70 6][]

SychronizedMap是在方法中加入了同步代码块，效率也可见一般：

![70 7][]

在线程安全方面，性能最好的是ConcurrentHashMap，是解决线程安全方面的大神Doug Lea的良心之作，ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响，采用分段加锁的思想提高了性能，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成，Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，Segment数组中每一个元素就是一把锁，每一个Segment元素存储的是HashEntry数组+链表。

五、关于HashMap的扩容问题

![70 8][]

![70 9][]

HashMap默认大小是16，当HashMap中的元素个数超过数组大小\*loadFactor(0.75)时，就会把数组的大小扩展为原来的两倍大小，不然效率会下降的比较快(链表的问题)，然后重新计算每个元素在数组中的位置。扩容是要遍历整个表的，并且重新计算每个元素的位置，所以要注意避免集合的扩容，它会很耗性能，根据元素的数量给它一个初始大小的值。

相信随着技术的成熟与跟进，HashMap的性能会越来越好，或者HashMap的替代集合会越来越好，毕竟不缺少智慧的大脑，只是缺少动手的设计与实现！

[70]: /images/20220519/4058dbcf59b149cb81ce8808b9ecaf87.png
[70 1]: /images/20220519/6a9af4d3ea0741ddb510c8d57bbd27f4.png
[70 2]: /images/20220519/0da62111d2ad4375bc9827b44c0b2829.png
[70 3]: /images/20220519/5b3be641baf041b095a8d571a0d9d941.png
[70 4]: /images/20220519/bef9c8f81e27486186cc340b494dda2b.png
[70 5]: /images/20220519/332b00933646446dbaf74aa9de456cf8.png
[70 6]: /images/20220519/ae66efa58a3c49c49a584ae8985689a6.png
[70 7]: /images/20220519/12610121f6cd4b67aafcd3fd58422970.png
[70 8]: /images/20220519/052004308a0b4ab491ff7ad2059778cf.png
[70 9]: /images/20220519/32024e2f48d341fcad6a2e42d90d3fdc.png