目录

  1. 概述
  2. JDK7
    1. 附录

概述

✨HashMap 特点

  • HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在，即主要用来存放键值对
  • HashMap 的实现不是同步的，这意味着它不是线程安全的
  • HashMap 的 key、value 都可以为 null
  • HashMap 中的映射不是有序的

📓HashMap 的变更

  • JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突**(两个对象调用的 hashCode 方法计算的哈希码值一致导致计算的数组索引值相同)**而存在的（拉链法解决冲突）
  • JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于 64 时，此时此索引位置上的所有数据改为使用红黑树存储

🎶将链表转换成红黑树前会判断，即时阈值大于 8，但是数组长度小于 64，此时并不会将链表变为红黑树，而是选择进行数组扩容

JDK7

之所以把HashSet和HashMap放在一起讲解，是因为二者在 Java 里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说HashSet里面有一个HashMap(适配器模式)。因此本文将重点分析HashMap

1
2
3
4
// HashSet 构造函数
public HashSet() {
    map = new HashMap<>();
}

HashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素；除该类未实现同步外，其余跟Hashtable大致相同；跟TreeMap不同，该容器不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个HashMap的顺序可能会不同。 根据对冲突的处理方式不同，哈希表有两种实现方式，一种开放地址方式(Open addressing)，另一种是冲突链表方式(Separate chaining with linked lists)。

✨Java7 HashMap 采用的是冲突链表方式

从上图容易看出，如果选择合适的哈希函数，put()和get()方法可以在常数时间内完成。但在对HashMap进行迭代时，需要遍历整个 table 以及后面跟的冲突链表。因此对于迭代比较频繁的场景，不宜将HashMap的初始大小设的过大。

有两个参数可以影响HashMap的性能: 初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。

将对象放入到HashMap或HashSet中时，有两个方法需要特别关心: hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到HashMap或HashSet中，需要*@Override*hashCode()和equals()方法。

附录

HashTable，HashMap 和 ConcurrentHashMap 的区别？
大厂之路一由浅入深、并行基础、源码分析一 “J.U.C”之 collections 框架：ConcurrentHashMap 扩容迁移等方法的源码分析（学妹哭着对我说：太难了！！！！我要回家！！）
ConcurrentHashMap(JDK1.8)为什么要放弃 Segment
HashMap 默认加载因子为什么选择 0.75？
HashMap 与 ConcurrentHashMap 的区别
HashMap 多线程死循环问题
常见的 hash 算法及其原理