古时的风筝第 82 篇原创文章
作者 | 风筝
公众号:古时的风筝(ID:gushidefengzheng)
转载请联系授权,扫码文末二维码加微信
题外话
听说公众号又改版了,之前推送不是按时间线来了,也就是你在订阅号消息中看到的推送是按照某种推荐规则来的,而不是按发文顺序,这导致如果大家不往下多翻翻,可能都看不到某些号的推文了,比如我这个小号。(除非加星标)
这两天的改变是公众号底部除了「在看」外,增加了「赞」和「分享」这两个功能,这个意思就是告诉各位同学,你好不容易能看到我的文章一回,不三连一下分享、点赞、在看,实在于心不忍吧。着急的话,赶紧滑到底部 Trible Kill 一下,不着急的话,可以看完文章再说。不差这几分钟的。

正文开始
之前的 7000 字说清楚 HashMap 已经详细介绍了 HashMap 的原理和实现,本次再来说说他的同胞兄弟 HashSet,这两兄弟经常被拿出来一起说,面试的时候,也经常是两者结合着考察。难道它们两个的实现方式很类似吗,不然为什么总是放在一起比较。
实际上并不是因为它俩相似,从根本上来说,它俩本来就是同一个东西。再说的清楚明白一点, HashSet 就是个套了壳儿的 HashMap。所谓君子善假于物,HashSet 就假了 HashMap。既然你 HashMap 都摆在那儿了,那我 HashSet 何必重复造轮子,借你一样,何不美哉!

HashSet
HashSet 是什么
下面是 HashSet
的继承关系图,还是老样子,我们看一个数据结构的时候先看它的继承关系图。与 HashSet
并列的还有 TreeSet
,另外 HashSet
还有个子类型 LinkedHashSet
,这个我们后面再说。

HashSet 继承关系
套壳 HashMap
为啥这么说呢,在我第一次看 HashSet
源码的时候,已经准备好了笔记本,拿好了圆珠笔,准备好好探究一下 HashSet
的神奇所在。可当我按着 Ctrl
+鼠标左键进入源码的构造函数的时候,我以为我走错了地方,这构造函数有点简单,甚至还有点神奇。new 了一个 HashMap
并且赋给了 map 属性。
private transient HashMap<E,Object> map; public HashSet() { map = new HashMap<>(); }
再三确认没看错的情况下,我明白了, HashSet
就是在 HashMap
的基础上套了个壳儿,我们用的是个 HashSet
,实际上它的内部存储逻辑都是 HashMap
的那套逻辑。
除了上面的那个无参类型的构造方法,还有其他的有参构造方法,一看便知,其实就是 HashMap
包装了一层而已。
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
用法
HashSet
应该算是众多数据结构中最简单的一个了,满打满算也就那么几个方法。
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
很简单对不对,就这么几个方法,而且你看每个方法其实都是对应的操作 map,也就是内部的 HashMap
,也就是说只要你懂了 HashMap
自然也就懂了 HashSet
。
保证不重复
Set
接口要求不能有重复项,只要继承了 Set
就要遵守这个规定。我们大多数情况下使用 HashSet
也是因为它有去重的功能。
那它是如何办到的呢,这就要从它的 add
方法说起了。
// Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public boolean add(E e) { return map.put(e, PRESENT)==null; }
HashSet
的 add
方法其实就是调用了 HashMap
的 put
方法,但是我们都知道 put
进去的是一个键值对,但是 HashSet
存的不是键值对啊,是一个泛型啊,那它是怎么办到的呢?
它把你要存的值当做 HashMap
的 key,而 value 值是一个 final
的 Object
对象,只起一个占位作用。而 HashMap
本身就不允许重复键,正好被 HashSet
拿来即用。
如何保证不重复呢
HashMap
中不允许存在相同的 key 的,那怎么保证 key 的唯一性呢,判断的代码如下。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
首先通过 hash 算法算出的值必须相等,算出的结果是 int,所以可以用 == 符号判断。只是这个条件可不行,要知道哈希碰撞是什么意思,有可能两个不一样的 key 最后产生的 hash 值是相同的。
并且待插入的 key == 当前索引已存在的 key,或者 待插入的 key.equals(当前索引已存在的key),注意 ==
和 equals 是或的关系。== 符号意味着这是同一个对象, equals 用来确定两个对象内容相同。
如果 key 是基本数据类型,比如 int,那相同的值肯定是相等的,并且产生的 hashCode 也是一致的。
String
类型算是最常用的 key 类型了,我们都知道相同的字符串产生的 hashCode 也是一样的,并且字符串可以用 equals 判断相等。
但是如果用引用类型当做 key 呢,比如我定义了一个 MoonKey
作为 key 值类型
public class MoonKey { private String keyTile; public String getKeyTile() { return keyTile; } public void setKeyTile(String keyTile) { this.keyTile = keyTile; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MoonKey moonKey = (MoonKey) o; return Objects.equals(keyTile, moonKey.keyTile); } }
然后用下面的代码进行两次添加,你说 size 的长度是 1 还是 2 呢?
Map<MoonKey, String> m = new HashMap<>(); MoonKey moonKey = new MoonKey(); moonKey.setKeyTile("1"); MoonKey moonKey1 = new MoonKey(); moonKey1.setKeyTile("1"); m.put(moonKey, "1"); m.put(moonKey1, "2"); System.out.println(hash(moonKey)); System.out.println(hash(moonKey1)); System.out.println(m.size());
答案是 2 ,为什么呢,因为 MoonKey
没有重写 hashCode
方法,导致 moonkey 和 moonKey1 的 hash 值不可能一样,当不重写 hashCode
方法时,默认继承自 Object
的 hashCode 方法,而每个 Object
对象的 hash 值都是独一无二的。
划重点,正确的做法应该是加上 hashCode
的重写。
@Override public int hashCode() { return Objects.hash(keyTile); }
这也是为什么要求重写 equals
方法的同时,也必须重写 hashCode
方法的原因之一。如果两个对象通过调用equals方法是相等的,那么这两个对象调用hashCode方法必须返回相同的整数。有了这个基础才能保证 HashMap
或者 HashSet
的 key 唯一。
非线程安全
由于 HashMap
不是线程安全的,自然, HashSet
也不是线程安全啦。在多线程、高并发环境中慎用,如果要用的话怎么办呢,不像 HashMap
那样有多线程版本的 ConcurrentHashMap
,不存在 “ConcurrentHashSet`这种数据结构,如果想用的话要用下面这种方式。
Set<String> set = Collections.synchronizedSet(new HashSet<String>());
或者使用 ConcurrentHashMap.KeySetView
也可以,但是,这其实就不是 HashSet
了,而是 ConcurrentHashMap
的一个实现了 Set
接口的静态内部类,多线程情况下使用起来完全没问题。
ConcurrentHashMap.KeySetView<String,Boolean> keySetView = ConcurrentHashMap.newKeySet(); keySetView.add("a"); keySetView.add("b"); keySetView.add("c"); keySetView.add("a"); keySetView.forEach(System.out::println);
LinkedHashSet
如果说 HashSet
是套壳儿 HashMap
,那么 LinkedHashSet
就是套壳儿 LinkedHashMap
。对比 HashSet
,它的一个特点就是保证数据有序,插入的时候什么顺序,遍历的时候就是什么顺序。
看一下它其中的无参构造函数。
public LinkedHashSet() { super(16, .75f, true); }
LinkedHashSet
继承自 HashSet
,所以 super(16, .75f, true);
是调用了 HashSet
三个参数的构造函数。
HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }
这次不是 new HashMap
了,而是 new 了一个 LinkedHashMap
,这就是它能保证有序性的关键。 LinkedHashMap
用双向链表的方式在 HashMap
的基础上额外保存了键值对的插入顺序。
HashMap
中定义了下面这三个方法,这三个方法是在插入和删除键值对的时候调用的方法,用来维护双向链表,在 LinkedHashMap
中有具体的实现。
// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { }
由于 LinkedHashMap
可以保证键值对顺序,所以,用来实现简单的 LRU 缓存。
所以,如果你有场景既要保证元素无重复,又要保证元素有序,可以使用 LinkedHashSet
。
最后
其实你掌握了 HashMap
就掌握了 HashSet
,它没有什么新东西,就是巧妙的利用了 HashMap
而已,新不新不要紧,好用才是最重要的。
还可以读 :
别说你还不懂 HashMap
有趣的图说 HashMap,普通人也能看懂
跟我极速尝鲜 Spring Boot 2.3
—————————————–
公众号:古时的风筝
一个兼具深度与广度的 程序员鼓励师 ,一个本打算写诗却写起了代码的田园码农! 你可选择现在就关注我,或者看看历史文章再关注也不迟。
技术交流还可以加群或者直接加我微信。
【三连走一波吧】

原文
http://mp.weixin.qq.com/s?__biz=MzAxMjA0MDk2OA==&mid=2449470235&idx=1&sn=66ebce4eef430d9a708ae0024f7a77d1
本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » HashSet:实不相瞒,我就是个套壳 HashMap