3.8 KiB
| layout | title | categories | |
|---|---|---|---|
| pages | 读 HashSet(读 HashMap) |
|
随机挑一个java类来读，今天读的是 HashSet。
HashSet 就是 HashMap 的 key。。。就。。。读完了。。。
得改个题目，读 HashMap。
翻译下 HashMap 类的注释
基于散列表实现的 Map 接口。实现了所有可选的 map 操作，并且允许 null 值 和 null key。大体上和 Hashtable 功能类似，除了 HashMap 不是线程同步的，并且允许 null。这个类不保证顺序，甚至不保证已有的元素顺序的可重复读。
假设散列函数能恰当地把元素分散到哈希桶里，那么对于基础的操作，比如 get() 和 put()，能提供 O(1) 的时间复杂度. 对于集合视图的遍历所需要的时间，跟其 “容量” （桶的数量）加上其大小（内含键值对的数量）成正比。所以如果遍历的性能比较重要，就不要把初始容量设置得太大，或者把触发扩容用的负载系数设置得太低。
一个 HashMap 的实例，有两个影响性能的参数：初始容量（initial capacity） 和 负载系数（load factor）
原文逐字翻译的话，废话太多了，接下来用自己的话说吧。。load factor 描述了哈希表有多满，是判断哈希表是否需要扩容的标准，当 键值对的数量 > load factor 乘以 HashMap 的容量，就会自动扩容，容量翻倍，这个操作需要对数据进行 rehash。
load factor 默认 0.75，是权衡的结果，较高的值减少了空间开销，但增加了查找成本（影响绝大部分的操作，包括 get 和 put）。在设置初始容量时，应考虑预期条目数量及其负载系数，以尽量减少 rehash 操作的次数。如果初始容量大于最大条目数除以负载系数，则不会发生 rehash。
如果预期要存储的条目数比较大，一开始就设置一个大的初始容量，比让它自动 rehash 并扩容要好得多。
如果大部分条目的 hashCode 是相同的（也就是hash冲突比较多），会大大降低哈希表的性能。所以如果 key 是 Comparable 的类，也会结合他们比大小的结果。（这句就有点不太理解了）
要注意它的是非同步的。多线程使用时必须自己外加同步操作。或者直接用 Collections.synchronizedMap 包一层。
除非用 iterator 对象下自带的 remove 方法，不然的话，在通过 iterator 遍历期间，如果对 Map 进行了结构修改，iterator 会尽可能快速失败，立即报错的。(总之就是说一边遍历，一边并发的修改 是很奇葩的操作。我是建议试下搞个快照出来遍历)
抽几个关键词出来:
允许null、
初始容量、
负载系数、
非同步的操作、
不要遍历时并发修改、
下面开始看代码了。。。希望能发现一些新东西。。。还有最初的目的 "keySet" 呀。。。
解决哈希冲突
一个桶里要对应多个元素。数量少的时候是链表。达到 TREEIFY_THRESHOLD = 8 个元素且容量大于64时，转换成树结构。6个元素时，变回链表。桶里存的是链表或树的根节点。
HashSet
HashSet 就是 HashMap 的 keySet。那么 key 的值都存在哪里？集合内元素不可以重复这个特性怎么得来的？
key 跟 value 一起打包成了 Node 对象。Node 存到了哈希表里。
要拿到 keySet 里所有的 key 的值，只能从哈希表里遍历额。HashIterator 会有一些遍历到空白桶位的额外消耗。
好处是 Set 的集合内元素不可以重复这个特性，可以直接从哈希表传承到一大部分，再从处理哈希冲突的数据结构里传承到剩下的部分。
扩容
容量翻倍
newCap = oldCap << 1
containsValue() 性能有点惨
for(哈希桶)
for(单个桶里所有元素)
- 文章目录 {:toc}