[Java数据结构和算法] HashMap 和 HashSet

认识 HashMap 和 HashSet

HashMap官方文档

HashSet官方文档

HashMap 和 HashSet 是Java中利用哈希表实现的 Map 和 Set。

由于哈希表的 插入/查找/删除 操作的时间复杂度均为 O（1），因此 HashMap 和 HashSet 相关操作的时间复杂度也是 O（1）。

HashMap

构造方法

1. 无参构造方法

创建一个空的 HashMap，长度为数组默认值16，载荷因子为0.75

2. 传入指定长度的构造方法

可见该方法内部调用的是带有两个参数的构造方法（一个是传入的指定长度值，一个是默认的载荷因子）

3. 带有两个参数的构造方法

该构造方法将指定的原来默认的载荷因子改成传入的指定载荷因子，然后将传入的指定数组长度改成2的幂次（比如传入的指定长度为10，返回的值是16，因为16是2的4次方）

4. 传入一个Map的构造方法

所创建的HashMap中将包含所传入的Map中的所有元素。

HashMap源码分析

数组的初始化

若调用无参构造方法，默认的数组长度是16.

当调用put方法，会计算value的哈希值，并且给数组table分配内存

调用put方法后，会给数组分配默认内存大小，为16。

put方法

get方法

若getNode返回的为空，表示没有找到，返回空；若返回一个节点，则返回该节点的value。

以下是具体操作图示：

HashSet

和 TreeSet 底层是 TreeMap 一样，HashSet 的底层也是 HashSet。

它的四个构造方法都是通过 HashMap 来实现的。

1. 无参构造方法

2. 传入指定数组长度的构造方法

3. 传入指定数组长度和载荷因子的构造方法

4. 传入一个集合的构造方法

add 和 remove 等操作也都是通过 Map 的操作来实现的

与 TreeMap/TreeSet 的区别

HashMap 和 TreeMap 的区别

HashSet 和 TreeSet 的区别

感谢观看！希望读者朋友们能够学到东西。

若有不对的，请尽管指出 ~

完