Java中的哈希 – 结构和访问时间
我正在寻找关于两个不同但相关的论点的validation – 上面的（A）和下面的（B）第一行 – 在Q中的注释。
（A） HashMap的结构方式是：
HashMap是一个普通表。 这就是直接内存访问（DMA）。
HashMap （或一般哈希）背后的整个想法是使用这个恒定时间内存访问
a。）通过自己的数据内容（）访问记录，而不是通过它们在DMA中的位置（表索引）
b。）管理可变数量的记录 – 许多不具有给定大小的记录，并且在整个使用该结构时可以/不保持大小不变。
因此，Java Hash中的整体结构是：
表： 表 //我正在使用HashMap中使用的标识符
该表的每个单元格都是一个桶 。
每个存储桶都是Entry类型的链接列表 – 即，此链接列表的每个节点（不是Java / API的链接列表，但数据结构）属于Entry类型，而Entry类型又是对。
当新对添加到散列中时，将为此对计算唯一的hashCode 。 这个hashCode是表中 索引的关键 – 它告诉这个哪个桶将进入哈希。 注意： hashCode通过函数hash（） （在HashMap中为一个）进行“规范化”，以更好地拟合表的当前长度。 indexFor（）也用于确定哪个桶，即表的单元格将进入。
确定存储桶后，将添加到此存储桶中链接列表的开头 – 因此，它是此存储桶中的第一个条目以及链接的第一个条目-list-已经存在的现在是这个新添加的“下一个”条目。
// ================================================ ===============
（B）从我在HashMap中看到的，调整表的大小 – 哈希仅在基于散列大小和容量（即当前和最大）的决策时完成。 整个哈希中的＃个条目。
没有对单个存储桶大小进行重新构造或resize – 例如当存储桶中的最大条目数超过此类时，“resize（）”。
这可能是不可能的，但是有可能在桶中大量填充大量条目，而散列的其余部分几乎是空的。
如果是这种情况，即每个桶的大小没有上限，则散列不是常数而是线性访问 – 理论上是一件事。 获取哈希条目需要$ O（n）$时间，其中$ n $是条目总数。 但那不应该。
// ================================================ ===============
我不认为我在上面的（A）部分中遗漏了任何内容。
我不完全确定（B）部分。 这是一个重要的问题，我正在寻找这个论点的准确性。
我正在寻找两个部分的validation。
提前致谢。
// ================================================ ===============
编辑：
最大桶大小是固定的，即每当桶中的#enits达到最大值时重构的散列将解析它 – 理论上和使用中访问时间是明显的常量。
这不是一个结构良好但快速修复，并且为了持续访问而工作得很好。
hashCodes很可能在整个存储桶中均匀分布，并且很可能任何存储桶都不会在达到哈希总体大小的阈值之前达到桶最大值。 这是HashMap的当前设置也在使用的假设。
同样基于Peter Lawrey在下面的讨论。
HashMap中的冲突只是拒绝服务攻击等病态案例中的一个问题。
在Java 7中，您可以更改散列策略，以便外部方无法预测您的散列算法。
AFAIK，在Java 8中，字符串键的HashMap将使用树映射而不是链表来进行冲突。 这意味着O（ln N）最坏情况而不是O（n）访问时间。
我希望在所有内容都在同一个哈希值时增加表大小。 当表的大小发生时，哈希到桶的映射会发生变化。
你的想法听起来不错。 并且它完全正确，基本上当表大小小于期望/每个桶的平均元素数量太大时，HashMap会做什么。 它不是通过查看每个桶并检查是否有太多因为它很容易计算它。
根据这个在OpenJDK中实现HashMap.get()
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
这表明HashMap如何找到非常好的元素，但它以非常混乱的方式编写。 经过一些重命名，评论和重写后，它看起来大致如下：
public V get(Object key) { if (key == null) return getForNullKey(); // get key's hash & try to fix the distribution. // -> this can modify every 42 that goes in into a 9 // but can't change it once to a 9 once to 8 int hash = hash(key.hashCode()); // calculate bucket index, same hash must result in same index as well // since table length is fixed at this point. int bucketIndex = indexFor(hash, table.length); // we have just found the right bucket. O(1) so far. // and this is the whole point of hash based lookup: // instantly knowing the nearly exact position where to find the element. // next see if key is found in the bucket > get the list in the bucket LinkedList bucketContentList = table[bucketIndex]; // check each element, in worst case O(n) time if everything is in this bucket. for (Entry entry : bucketContentList) { if (entry.key.equals(key)) return entry.value; } return null; }
我们在这里看到的是，存储桶确实依赖于从每个密钥对象返回的.hashCode()和当前表大小。 它通常会改变。 但仅限于.hashCode()不同的情况。
如果你有一个包含2 ^ 32个元素的巨大表格，你可以简单地说bucketIndex = key.hashCode() ，它会尽可能完美。 遗憾的是没有足够的内存来执行此操作，因此您必须使用更少的存储桶并将2 ^ 32哈希映射到几个存储桶中。 这就是indexFor本质上的作用。 将大量空间映射为小空间。
在典型的情况下（几乎）没有任何对象具有相同的.hashCode() 。 但是你不能用HashMaps做的一件事就是只添加具有完全相同哈希的元素。
如果每个散列都相同，那么基于散列的查找会产生相同的存储桶，而您的所有HashMap都变成了LinkedList（或者任何数据结构都包含存储桶的元素）。 现在你有O（N）访问时间的最坏情况，因为你必须遍历所有N个元素。