• 1. 概述
• 2. 存储结构
  • 2-1. 什么是hash冲突?
  • 2-2. 如何解决hash冲突?
  • 2-3. 负载因子的作用
  • 2-4. HashMap的数组容量(桶容量)为什么必须是2的幂次方?
  • 2-5. hash算法中16的由来?
• 3. 构造函数
• 4. 操作
  • 4-1. 添加
    • 4-1-1. 在数组上添加
    • 4-1-2. 在链表上添加
    • 4-1-3. 在红黑树上添加
    • 添加源码如下
  • 4-2. 删除
    • 4-2-1. 删除源码如下
  • 4-3. 查询
  • 4-4. 替换
• 5. 遍历
  • 5-1. 使用foreach进行遍历
  • 5-2. 使用keySet进行遍历
  • 5-3. 遍历所有的key
  • 5-4. 遍历所有的value
• 6. 扩容 & rehash
• 7. 总结

1. 概述

HashMap是一种key/value形式的存储结构. 它综合了数组(查询容易, 插入和删除困难)和链表(插入和删除容易, 查询困难)的特点.

HashMap的核心点就是hash算法和红黑树算法.

HashMap是无序的.

2. 存储结构

HashMap的存储结构为数组 + 链表/红黑树.

其中数组就是普通的数组, 链表是为了解决hash冲突而产生的, 如果冲突元素大于指定值, 就会由链表变为红黑树, 如果冲突元素少于指定的值, 就会由红黑树变为链表.

2-1. 什么是hash冲突?

当产生hash冲突的时候就产生了链表或红黑树, 一个完美的HashMap是单纯的数组结构, 并不会存在链表或红黑树结构的, 不过完美的事是不存在的, 只能尽可能的接近完美.

假设元素A被成功的添加到HashMap中, 存储在数组下标为0的地方, 这时元素B要被添加进来, 但是经过hash算法计算, 元素B要也要存储在数组下标为0的地方上, 这时候就产生了hash冲突.

2-2. 如何解决hash冲突?

出现了hash冲突, 解决方法就是在数组下标0处, 产生一个链表, 元素A为链表的表头, 新元素B放到链表的尾部.

称为拉链法.

2-3. 负载因子的作用

是这样的, 默认负载因子是0.75, 也就是HashMap中的数组填满了75%之后就会进行扩容.

• 如果负载因子过大, 则会导致hash冲突的机会越大, 但是空间使用率高;
• 如果负载因子过小, 则会导致空间的过度浪费, 但是hash冲突的机会越小.

所以, 必须在冲突的机会和空间利用率之间寻求一种平衡, 这种平衡本质上是数据结构中有名的时间和空间的平衡.

2-4. HashMap的数组容量(桶容量)为什么必须是2的幂次方?

首先给出答案: 为了使元素坐落于HashMap的承载量(size)之间.

答案和问题看起来毫无关系, 下面来分析一下是如何联系在一起的?

比如: 把"1"存入HashMap中, 会进行如下几步

1. 计算key的hashCode(key.hashCode()), 得到h
2. 然后对h进行低16位和高16位的异或运算, 得到hash (异或运算: 两个值不同为1, 相同为0)
3. 然后进行 (size - 1) & hash 的运算得到 (与运算: 只要有一个为1, 结果就是1)

第二步中的低16位与高16位进行运算是为了更好的进行散列(如果两个元素的低16位相同, 不进行高低16位运算的话, 出现hash冲突的机会就会变大), 高低16位运算之后, 可以减少hash冲突的机会.

最重要的就是第三步了, 也就是问题的答案, 如果桶容量大小是2的倍数(默认值16), 进行(size - 1)运算之后的值为15, 15的二进制为0001111, 15与第二步得到的hash进行运算后, 只会保留低4位的值, 高于4位的值都被去掉了(运算后为0). 既然只有低4位的值, 那么转化为十进制之后, 必然小于16, 正确的坐落于桶上. 完美!

2-5. hash算法中16的由来?

贴出HashMap中的hash算法源码

static final int hash(Object key) {     int h;     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

这段代码就是2-4问题中的第1,2步的实现, 那么这里的这个16数字是怎么来的呢???

答案就是因为key.hashCode()返回的是一个整数, 占4byte(32bit), 想充分打乱就要右移一半, 那就是16bit.

3. 构造函数

只说这个比较重要的构造函数

public HashMap(int initialCapacity, float loadFactor) {     if (initialCapacity < 0)         throw new IllegalArgumentException("Illegal initial capacity: " +                                            initialCapacity);     if (initialCapacity > MAXIMUM_CAPACITY)         initialCapacity = MAXIMUM_CAPACITY;     if (loadFactor <= 0 || Float.isNaN(loadFactor))         throw new IllegalArgumentException("Illegal load factor: " +                                            loadFactor);     this.loadFactor = loadFactor;     this.threshold = tableSizeFor(initialCapacity); }

默认的负载因子为: DEFAULT_LOAD_FACTOR(0.75).

用户自定义初始化容量, 但是HashMap会对传入的初始化容量进行校验(tableSizeFor), 需要确保这个值必须是2的幂次方.

4. 操作

4-1. 添加