2

假设我有一个 LinkedHashMap 对象，其中只有 8 个桶，编号从 0 到 7。现在我想添加元素。我添加了7个元素，结果如下：

1）Element_1：桶号2。这成为LinkedHashMap维护的链表的开始，以维护插入顺序。
1) Element_2：桶号 3。这链接到 Element_1
2) Element_3：桶号 1。这链接到 Element_2
3) Element_4：桶号 4。这链接到 Elemetn_3
4) Element_5：桶号 5。这链接到 Element_4
5) Element_6: Bucket Number 3. 这与 Element_5 相关联（发生碰撞）
6) Element_7: Bucket Number 3. 这与 Element_6 相关联（再次发生碰撞）

现在假设我要检索 Element_7。这个元素的散列给了我桶号 3。现在3 号桶中的元素是Element_2，Element_6，Element_7。
那么下面两个的遍历顺序是什么：
a）Element_2->Element_3->Element_4->Element_5->Element_6->Element_7。
或
b) Element_2->Element_6->Element_7。

我认为答案是（a），因为 LinkedHashMap 维护了一个链表来维护插入顺序。因此，如果顺序为 (b)，则表示特定元素正在存储两个引用，一个用于按插入顺序排列的下一个元素，一个用于同一桶中的下一个元素。

如果答案是 (b)，特定元素如何决定访问哪一个，即从两个引用中选择哪一个。

用例场景是假设性的，它可能与元素数量少于桶数的事实不相关，碰撞的机会更小。请记住上述情况进行回答。
提前致谢。

4

2 回答 2

2

LinkedHashMap 扩展了 HashMap ，因此链接与 无关get，因此在添加链接时，它们不应该降低 LinkedHashMap 的效率get- 因为 get 不需要该链接。

于 2012-04-11T17:08:48.937 回答
1

LinkedHashMap 扩展了 HashMap，它的get方法调用了 HashMap 的getEntry方法。HashMap 的实现将每个桶存储在一个单独的数组中，因此它不需要遍历整个数据集，只需要对该桶中的数据进行循环。取自 Oracle JDK 7：

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : 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 != null && key.equals(k))))
            return e;
    }
    return null;
}

编辑

e.next定义在HashMap.Entry同一个桶中，而不是e.after定义e.before在LinkedHasMap.Entry不同的桶中。

于 2012-04-11T17:10:19.050 回答