首页 / JAVA / java – ImmutableCollections SetN实现细节

java – ImmutableCollections SetN实现细节

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – ImmutableCollections SetN实现细节，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3602字，纯文字阅读大概需要6分钟。

内容图文

我很难理解java-9 ImmutableCollections.SetN中的实现细节.具体为什么需要两次增加内部数组.

假设你这样做：

Set.of(1,2,3,4) // 4 elements, but internal array is 8

更准确地说,我完全理解为什么在HashMap的情况下完成(双重扩展) – 你从来没有(几乎)希望load_factor是一个.值=！= 1可以改善搜索时间,因为条目更好地分散到例如桶中.

但是在一个不可变的集合的情况下 – 我无法真正说出来.特别是因为选择了内部数组的索引.

让我提供一些细节.首先如何搜索索引：

 int idx = Math.floorMod(pe.hashCode() ^ SALT, elements.length);

pe是我们放入集合的实际值. SALT在启动时只生成32位,每个JVM一次(如果需要,这是实际的随机化).我们的例子中的elements.length是8(4个元素,但这里8个 – 大小加倍).

这个表达式就像一个负安全的模运算.请注意,在选择存储桶时,在HashMap中执行相同的逻辑操作,例如((n – 1)& hash).

因此,如果elements.length对于我们的情况是8,那么这个表达式将返回任何小于8的正值(0,1,2,3,4,5,6,7).

现在剩下的方法：

 while (true) {
        E ee = elements[idx];
        if (ee == null) {
            return -idx - 1;
        } else if (pe.equals(ee)) {
            return idx;
        } else if (++idx == elements.length) {
            idx = 0;
        }
    }

让我们分解一下：

if (ee == null) {
    return -idx - 1;

这很好,这意味着数组中的当前插槽是空的 – 我们可以将值放在那里.

} else if (pe.equals(ee)) {
    return idx;

这很糟糕 – 插槽被占用,已经就位的条目等于我们要放置的条目.集合不能包含重复元素 – 因此稍后会抛出异常.

 else if (++idx == elements.length) {
      idx = 0;
 }

这意味着此插槽已被占用(哈希冲突),但元素不相等.在HashMap中,此条目将与LinkedNode或TreeNode放在同一个存储桶中 – 但不是这里的情况.

因此索引递增并尝试下一个位置(当它到达最后位置时,它以圆形方式移动的小警告).

这里有一个问题：在搜索索引时,如果没有什么太花哨(除非我遗漏了什么),为什么需要有两倍大的数组？或者为什么函数不是这样编写的：

int idx = Math.floorMod(pe.hashCode() ^ SALT, input.length);

// notice the diff elements.length (8) and not input.length (4)

解决方法:

SetN的当前实现是一个相当简单的闭合散列方案,而不是HashMap使用的单独链接方法. (“封闭散列”也混淆地称为“open addressing”.)在封闭散列方案中,元素存储在表本身中,而不是存储在从每个表槽链接的元素列表或树中,这是单独链接.

这意味着如果两个不同的元素散列到同一个表槽,则需要通过为其中一个元素找到另一个槽来解决此冲突.当前的SetN实现使用线性探测解决了这个问题,其中顺序检查表槽(在末尾回绕),直到找到打开的槽.

如果你想存储N个元素,它们肯定会适合大小为N的表.你总是可以找到集合中的任何元素,尽管你可能需要探测几个(或许多)连续的表槽来找到它,因为会有很多碰撞.但是,如果探测到的是不是成员的对象,则线性探测必须先检查每个表槽,然后才能确定该对象不是成员.使用完整表,大多数探测操作将降级到O(N)时间,而大多数基于散列的方法的目标是操作为O(1)时间.

因此,我们有一个类时空权衡.如果我们把桌子做得更大,整个桌子上都会有空的插槽.存储项目时,应该有更少的冲突,线性探测将更快地找到空槽.彼此相邻的完整时隙簇将更小.非成员的探测器将更快地进行,因为他们更可能在线性探测时更快地遇到空槽 – 可能在完全不需要重新探测之后.

在提出实施时,我们使用不同的扩展因子运行了一系列基准测试. (我在代码中使用了术语EXPAND_FACTOR,而大多数文献都使用了加载因子.原因是扩展因子是负载因子的倒数,如HashMap中所使用的那样,并且对于这两种含义使用“加载因子”会令人困惑.)当扩展因子接近1.0时,探测器性能非常缓慢,如预期的那样.随着扩展系数的增加,它得到了显着改善.到达3.0或4.0时,这种改进确实很平坦.我们选择2.0,因为它获得了大部分性能提升(接近O(1)时间),同时与HashSet相比提供了良好的空间节省. (对不起,我们没有在任何地方公布这些基准数字.)

当然,所有这些都是实现细节,并且可能会从一个版本更改为下一个版本,因为我们找到了更好的方法来优化系统.我确信有办法改进当前的实施. (幸运的是,当我们这样做时,我们不必担心preserving iteration order.)

有关负载因子的开放寻址和性能折衷的详细讨论可以在3.4节中找到

Sedgewick, Robert and Kevin Wayne. Algorithms, Fourth Edition. Addison-Wesley, 2011.

在线图书网站是here,但请注意印刷版有更多细节.

内容总结

以上是互联网集市为您收集整理的java – ImmutableCollections SetN实现细节全部内容，希望文章能够帮你解决java – ImmutableCollections SetN实现细节所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/700904.html

来源：【匿名】