• 目录:

    读 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、

    初始容量、

    负载系数、

    非同步的操作、

    不要遍历时并发修改、

    下面开始看代码了。。。希望能发现一些新东西。。。还有最初的目的 “HashSet(keySet)” 呀。。。

    解决哈希冲突

    一个桶里要对应多个元素。数量少的时候是链表。达到 TREEIFY_THRESHOLD = 8 个元素且容量大于64时,转换成树结构。6个元素时,变回链表。桶里存的是链表或树的根节点。

    HashSet

    HashSet 就是 HashMap 的 keySet。那么 key 的值都存在哪里?集合内元素不可以重复这个特性怎么得来的?

    key 跟 value 一起打包成了 Node 对象。Node 存到了哈希表里。

    要拿到 keySet 里所有的 key 的值,只能从哈希表里遍历额。HashIterator 会有一些遍历到空白桶位的额外消耗。

    好处是 Set 的集合内元素不可以重复这个特性,可以直接从哈希表传承到一大部分,再从处理哈希冲突的数据结构里传承到剩下的部分。

    (那 Node 里 value 存的是啥?)

    扩容

    容量翻倍

    newCap = oldCap << 1
    

    containsValue() 性能有点惨

    for(哈希桶)
        for(单个桶里所有元素)