0

我在 GrepCode.com 上检查了 HashMap 的源代码，发现它将对象哈希码存储在数组中。

transient Entry[] table;

  public V put(K key, V value) {
         if (key == null)
             return putForNullKey(value);
         int hash = hash(key.hashCode());
         int i = indexFor(hash, table.length);
         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
             }
         }

         modCount++;
         addEntry(hash, key, value, i);
         return null;
     }

 void addEntry(int hash, K key, V value, int bucketIndex) {
         Entry<K,V> e = table[bucketIndex];
         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
         if (size++ >= threshold)
             resize(2 * table.length);
}

请建议。

4

7 回答 7

4

这是一个内部实现细节。HashMap的合同不保证排序，因此允许您具有位置访问权限，实质上是允许您编写每次调整实现时都会中断的代码。

于 2013-10-07T05:09:05.513 回答
2

它确实“将对象哈希码存储在数组中”，但这并不意味着它将映射中的每个对象都存储在数组中。再看一遍。它将Entry项存储在一个数组中，但每个Entry项都是链表的头部。并非哈希表中的每个值都在数组中具有索引。所以索引访问将毫无意义。

于 2013-10-07T05:19:16.490 回答
2

为什么 HashSet 或 HashMap 不支持基于位置的访问？

  • 哈希表数组中条目的“位置”不稳定：

    • 如果添加新条目，则位置可能会以不可预测的方式发生变化。

    • 如果你复制一个哈希表，元素的位置可能会以不可预知的方式发生变化。

    • 确切的行为是特定于实现的。

  • 数组中条目的“位置”不是完整的位置，因为数组是条目链的实际值，而不是条目。一个条目的完整位置实际上是两个整数：哈希数组索引，以及距哈希链起点的距离。

  • 条目的“位置”与条目本身或添加它们的顺序没有有用的语义关系。

这些东西结合起来使“位置”实际上毫无用处……而且使用起来可能很危险。因此，支持这一点将是一个坏主意。

事实上，我稍微简化了一点。如果您知道所有哈希码是什么，以及用于将哈希表恢复到当前状态的修改操作的精确顺序，就可以计算出哈希链以及每个条目在哈希链中的位置. 但是，您必须有效地重播整个操作序列才能执行此操作。此外，即使您这样做了，您也无法将这些信息用于任何有用的目的。

于 2013-10-07T05:24:51.973 回答
1

Sets 和s的概念Map不包括任何排序，因此“基于位置”的访问没有任何意义。ASet要么有元素，要么没有元素，并且 aMap通过键查找值。如果您想要某种顺序以便您可以按位置选择元素，请使用更具体的数据结构，例如SortedMapor SortedSet，它使元素保持排序顺序并具有用于分区和选择子范围的元素。

于 2013-10-07T05:12:53.187 回答
1

是的，内部 HashMap/HashSet 确实使用数组。但是从这些数组中保存或检索都不是顺序的。原因很简单：这些集合用于hashing决定存储和检索对象的桶。为每个条目计算的哈希不是序列号。每个元素的哈希用于存储和检索这些集合中的条目。

于 2013-10-07T05:13:09.950 回答
1

没有明确的方法来使用位置索引。您拥有存储桶的索引，但一个存储桶中可以有多个条目。这意味着有些职位没有条目，但有些职位有多个条目。无论您使用什么策略，都无法以简单的方式增加索引。

如果添加条目，则可以重新排列所有位置，从而使添加条目之前和之后的位置没有用处。也没有自然的方式来表达条目的索引应该是什么。

您拥有的最接近的选项是迭代条目并将索引与每个条目相关联。问题是在更新 Map 之间没有效率或保证保留。

于 2013-10-07T05:59:48.587 回答
0

HashMap不保证您的订单。

此类不保证地图的顺序；特别是，它不保证订单会随着时间的推移保持不变。

但是，如果您愿意，您可以通过LinkedHashMap类，它按照将键插入映射的顺序（插入顺序）。

于 2013-10-07T05:12:37.140 回答