转载

和阿里面试官对线,多亏看完这篇HashSet源码解析

这个世上没有无用的齿轮,也只有齿轮本身能决定自己的用途.
——东野圭吾《嫌疑犯X的献身》

0 前言

HashSet 是一个没有重复元素的集合.主要由 HashMap 实现,不保证元素顺序,而允许 null 元素.非线程安全,如果需要安全请自行加锁,或者使用 Collections.synchronizedSet包装.最好在创建时完成这一操作,以防止对该 set 进行意外的不同步访问.

1 继承体系

HashSet继承自AbstractSet,并且实现了Set接口.HashSet的本质是一个"没有重复元素"的集合,它是通过HashMap实现的。HashSet中含有一个"HashMap类型的成员变量"map,HashSet的操作函数,实际上都是通过map实现的.

2 属性

  • HashSet 组合了 HashMap,把 HashMap 当作自己的一个局部变量

可以在基础类方法的基础上进行扩展,而且方法命名可以任意命名,无需和基础类的方法名称保持一致.

  • 与后备Map中的对象关联的虚拟 value

3 构造方法

3.1 无参

  • 直接 new HashMap

3.2 有参

  • 当有原始集合数据进行初始化的情况下

计算 HashMap 的容量:取括号中两个数的最大值
(期望值 / 0.75+1,默认值 16)
若给定 HashMap 初始容量
< 16 按照 HashMap 默认的 16 初始化
> 16 按给定值初始化

HashMap 扩容阈值:Map容量 * 0.75f,而此处的计算值正好比阀值大1,就不会立即扩容.

HashSet 的 API 都比较简单,就是对 HashMap 的进行了简单的包装.我们简单看几个,

4 add(E e)

  • 直接使用 HashMap 的 put 方法并判断

如果指定的元素尚不存在,则将其添加到该 set 中.更确切地说

  • 如果此元素集中不包含任何元素e2,使得
    (e==null ? e2==null : e.equals(e2))
    则将指定元素e添加到该元素集合中
  • 如果此集合已包含该元素,则调用将使该集合保持不变并返回false

5 remove

  • 直接调用 HashMap 的 remove 方法并判断

如果存在,则从此set中删除指定的元素.更确切地讲,如果此set包含这样的元素
(o==null ? e==null : o.equals(e))
则删除元素.
如果此集合包含该元素(或者说,如果此集合由于方法的调用而被更改),则返回true.(一旦调用返回,此集合将不包含该元素)

其他方法实现类似如此,不再赘述.

6 总结

HashSet 的实现给我们留下了一些最佳实践

  • 组合有时比继承更加适用
  • 注意封装复杂逻辑,使对外接口充满用户体验
  • 要对组合的其他数据结构十分了解,才能使代码设计达到 1+1>2 奇效.
正文到此结束
本文目录