4

我正在寻找对两个不同但相关的论点的验证——那些高于(A)和低于(B)的第一行行注释。

(A) HashMap的结构方式是：

HashMap是一个普通的表。那就是直接内存访问（DMA）。

HashMap （或一般的散列）背后的整个想法首先是将这种恒定时间的内存访问用于

a.) 通过它们自己的数据内容（<K,V>）访问记录，而不是通过它们在 DMA 中的位置（表索引）

b.) 管理可变数量的记录——一些不具有给定大小的记录，并且在整个使用该结构的过程中可能/不保持大小不变​​。

因此，Java Hash 中的整体结构是：

a table: table // 我正在使用HashMap中使用的标识符

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

每个桶是一个Entry类型的链表——即这个链表的每个节点（不是Java/API 的链表，而是数据结构）都是Entry 类型，而Entry又是一个<K,V> 对。

当有一个新的对被添加到哈希中时，会为这个 <K,V> 对计算一个唯一的hashCode 。这个hashCode是这个<K,V>在表中的索引键——它告诉这个<K,V>将进入哪个桶。注意：hashCode通过函数hash()（在HashMap中为一个）“规范化”，以更好地适应table的当前长度。indexFor()也用于确定 < K,V > 将进入哪个桶，即表的单元格。

当bucket确定后，<K,V>被添加到这个bucket中链表的开头——结果，它是这个bucket中的第一个<K,V>条目，并且是链表的第一个条目-list-that-already-existed 现在是这个新添加的条目指向的“下一个”条目。

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

(B) 根据我在HashMap中看到的，表的大小调整——哈希仅在基于哈希大小和容量（即当前和最大值）的决定时完成。# 整个哈希中的条目。

没有对单个存储桶大小进行重组或调整大小 - 例如“当存储桶中的 max.#entries 超过此类时的“resize()”。

这是不可能的，但是有可能大量的条目可能会堆积在一个桶中，而其余的散列几乎是空的。

如果是这种情况，即每个桶的大小没有上限，则哈希不是恒定的而是线性访问——理论上是为了一件事。获取哈希中的条目需要 $O(n)$ 时间，其中 $n$ 是条目的总数。但那不应该。

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

我认为我没有遗漏上述（A）部分中的任何内容。

我不完全确定（B）部分。这是一个重要的问题，我正在寻找这个论点的准确性。

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

提前致谢。

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

编辑：

最大存储桶大小是固定的，即，只要存储桶中的#entries 达到最大值，就会重新构建散列 - 访问时间在理论上和使用中都是恒定的。

这不是一个结构良好但快速的解决方案，并且为了持续访问而工作得很好。

hashCodes 很可能均匀地分布在整个存储桶中，并且在达到哈希整体大小的阈值之前，任何存储桶都不太可能达到 bucket-max。这也是当前 HashMap 设置使用的假设。

也基于下面彼得劳里的讨论。

4

2 回答 2

3

HashMap 中的冲突只是在拒绝服务攻击等病态情况下才会出现问题。

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

AFAIK，在 Java 8 HashMap 中，String 键将使用树形图而不是链表进行冲突。这意味着 O(ln N) 最坏情况而不是 O(n) 访问时间。

于 2013-08-01T20:43:16.980 回答
1

当所有内容都在同一个哈希中时，我希望增加表大小。当表的大小发生变化时，哈希到桶的映射会发生变化。

你的想法听起来不错。这是完全正确的，基本上当表大小小于预期/每个桶的平均元素数量变得太大时，HashMap 会做什么。它不是通过查看每个桶并检查其中是否有太多东西来做到这一点，因为它很容易计算。

HashMap.get()根据this在OpenJDK中的实现是

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> 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<Entry> 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;
}

我们在这里看到的是，bucket 确实取决于.hashCode()每个 key 对象的返回值和当前表的大小。它通常会改变。但仅在不同的情况下.hashCode()。

如果您有一个包含 2^32 个元素的巨大表格，您可以简单地说bucketIndex = key.hashCode()，它会尽可能完美。不幸的是，没有足够的内存来执行此操作，因此您必须使用更少的存储桶并将 2^32 哈希映射到几个存储桶中。这就是indexFor本质上的作用。将大数空间映射到小数空间。

.hashCode()在（几乎）没有对象与其他对象相同的典型情况下，这完全没问题。但是你不能用 HashMaps 做的一件事是只添加具有完全相同哈希的元素。

如果每个哈希都相同，则基于哈希的查找会产生相同的存储桶，并且您的所有 HashMap 都变成了 LinkedList（或任何包含存储桶元素的数据结构）。现在您遇到了 O(N) 访问时间的最坏情况，因为您必须遍历所有 N 个元素。

于 2013-08-01T23:47:12.793 回答