古时的风筝第 82 篇原创文章
作者 | 风筝
公众号:古时的风筝(ID:gushidefengzheng)
转载请联系授权,扫码文末二维码加微信
听说公众号又改版了,之前推送不是按时间线来了,也就是你在订阅号消息中看到的推送是按照某种推荐规则来的,而不是按发文顺序,这导致如果大家不往下多翻翻,可能都看不到某些号的推文了,比如我这个小号。(除非加星标)
这两天的改变是公众号底部除了「在看」外,增加了「赞」和「分享」这两个功能,这个意思就是告诉各位同学,你好不容易能看到我的文章一回,不三连一下分享、点赞、在看,实在于心不忍吧。着急的话,赶紧滑到底部 Trible Kill 一下,不着急的话,可以看完文章再说。不差这几分钟的。
之前的 7000 字说清楚 HashMap 已经详细介绍了 HashMap 的原理和实现,本次再来说说他的同胞兄弟 HashSet,这两兄弟经常被拿出来一起说,面试的时候,也经常是两者结合着考察。难道它们两个的实现方式很类似吗,不然为什么总是放在一起比较。
实际上并不是因为它俩相似,从根本上来说,它俩本来就是同一个东西。再说的清楚明白一点, HashSet 就是个套了壳儿的 HashMap。所谓君子善假于物,HashSet 就假了 HashMap。既然你 HashMap 都摆在那儿了,那我 HashSet 何必重复造轮子,借你一样,何不美哉!
下面是 HashSet
的继承关系图,还是老样子,我们看一个数据结构的时候先看它的继承关系图。与 HashSet
并列的还有 TreeSet
,另外 HashSet
还有个子类型 LinkedHashSet
,这个我们后面再说。
为啥这么说呢,在我第一次看 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);
如果说 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
-----------------------------------------
一个兼具深度与广度的 程序员鼓励师 ,一个本打算写诗却写起了代码的田园码农! 你可选择现在就关注我,或者看看历史文章再关注也不迟。
【三连走一波吧】