java - Java中的哈希—结构和访问时间

Question

我正在寻找对两个不同但相关的论点进行验证的方法-Q的第一行注释行在(A)之上和(B)之下。

(A) HashMap 的结构方式为:

HashMap 是普通表。多数民众赞成在直接内存访问(DMA)。

HashMap (或通常的哈希)背后的整个思想
是为了将这种恒定时间的内存访问用于

a。)通过自己的数据内容( )访问记录，
而不是根据它们在DMA中的位置(表索引)

b。)管理可变数量的记录-
记录不是给定大小的，并且可能/不保持恒定
整个使用此结构的大小。

因此，Java Hash的总体结构为:

一个表: 表 // //我使用 中使用的标识符HashMap

该表的每个单元格都是 存储桶。

每个 存储桶是 类型的链接列表条目-
也就是说，此链接列表的每个节点(不是Java / API的链接列表，而是数据结构)的类型为 条目，而该对又是 对。

当有一对新配对添加到哈希中时，
为此 对计算唯一的 hashCode 。
此 哈希码是 表中此 的索引的键-它告诉
此 将存储在哪个存储桶中。
注意: hashCode 通过函数 hash()(在 中的HashMap 中)被“规范化”
以更好地适合 表的当前长度。 indexFor()也正在使用
确定 将进入哪个存储区，即表的单元格。

确定存储桶后，会将 添加到此存储桶中链接列表的开头-结果，它是此存储桶中的第一个 条目，也是链接的第一个条目-list-已经存在的列表
此新添加的指向的“下一个”条目。

// ================================================ ===============

(B)
根据我在 HashMap 中看到的内容，重新调整 表的大小-仅根据基于
哈希大小和容量，这是当前值和最大值整个哈希中的＃个条目。

无需对各个存储桶大小进行重组或调整大小，例如“当存储桶中的最大条目数超过此类时，将使用resize()”。

可能性不大，但有可能在存储桶中堆积大量条目，而其余的哈希值几乎是空的。

如果是这种情况，即每个存储桶的大小没有上限，则哈希值不是常数而是线性访问-从理论上讲是一回事。获取哈希中的条目需要$ O(n)$的时间，其中$ n $是条目的总数。但是那不应该。

// ================================================ ===============

我不认为我会在上面的(A)部分中遗漏任何内容。

我不确定(B)部分。这是一个重要的问题，我正在寻找该论证的准确性。

我正在寻找两部分的验证。

提前致谢。

// ================================================ ===============

编辑:

固定的最大存储桶大小，即无论何时只要重新构造哈希
#bucket中的#entries达到最大值将解决该问题-访问时间很简单
在理论上和使用中保持不变。

这不是一个结构合理但可以快速解决的方法，并且为了持续访问而很好地工作。

hashCode可能会在整个存储桶中平均分配，并且不太可能
在达到哈希的总大小阈值之前，任何存储桶都将达到存储桶最大值​​。
这是当前HashMap设置也正在使用的假设。

同样基于彼得·劳瑞(Peter Lawrey)在下面的讨论。

Answer 1

HashMap中的冲突仅在诸如拒绝服务攻击之类的病理情况下才是问题。

在Java 7中，您可以更改哈希策略，以使外部方无法预测您的哈希算法。

AFAIK，在Java 8中，用于String键的HashMap将使用树映射而不是链接列表进行碰撞。这意味着O(ln N)最坏的情况，而不是O(n)访问时间。