揭秘 HashSet：基于 HashMap 的不重复魔法

说一下 HashSet 的实现原理？

HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上。使用HashMap实现HashSet时，HashMap的value统一为present=new Objec()。因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层HashMap 的相关方法来完成。我们知道HashMap的key不允许重复，因此HashSet存储的值是不允许重复的值。

HashSet如何保证元素不重复？

HashSet底层采用HashMap保存元素，HashSet中保存的元素就是HashMap中的Key，而HashMap中的Key是不重复的，所以HashSet中的元素不会重复。（Vuale存储的都的Object类型的Present）

更深层次原因是： HashSet在添加元素时，会调用，HashMap中的put方法。 在put方法中，首先会计算key的hash值，将（数组长度-1）与hash值进行&操作，得到插入哈希表的位置。

如果该位置已经存在元素，那么会进行如下判断（体现去重操作）

• 若两元素key的hash值不同，说明不重复，则存入，存入方式为链表或红黑树
• 若key的hash值相同，且equals相同，说明重复，不存在
• 若key的hash值相同，但equals不同，不重复，则存入，存入方式为链表或红黑树

注： 其实，直接用equals就可以判断出来，之所以，先用hash判断，是避免多次调用equals以增加开销。

以上内容出自本人整理的面试秘籍。 链接: https://pan.baidu.com/s/1o014Ems8diV0D3h8K15olA?pwd=fi3x 提取码: fi3x 复制这段内容后打开百度网盘手机App，操作更方便哦