如何在hashmap内部保持密钥的唯一性[duplicate]

Question

每个人都知道hashmap包含唯一的键。但是我想知道它是如何保持唯一性的？

假设我们在hashmap中插入100个数据，然后在同一hashmap中插入重复的键和值。我知道它会覆盖这个值。但我想知道它会检查hashmap中已经存储的所有之前的密钥，然后覆盖新密钥。

或者如果它每次都检查以前的所有键，那么它将需要更多的时间。所以请告诉我正确的答案。

Answer 1

请看下面这张照片(https://www.bigocheatsheet.com/)

哈希集合具有O（1）插入复杂性，这意味着操作不取决于数据结构中已经存在多少数据点。顾名思义，键被散列到桶中。如果要查找keya的值，则会获取该键，并使用哈希函数将该值映射到特定的内存位置。不需要查找任何其他值。

例外情况是由于维数降低而必然发生的哈希冲突。在使用has函数后，不同的密钥max解析为相同的散列，从而落在同一个bucket中。在这种情况下，必须进行其他检查（这就是为什么您总是必须覆盖hashcode和equals的原因）。有关这方面的更多信息，请参见：https://stackoverflow.com/a/19691998/3244464

Answer 2

您需要知道HashMap的内部表示形式。

实际上，它是一个键值项列表的数组，我们可以用图形表示它，如下所示：

  bucket 
  position
  --------
  0         NULL
  1         --> (K1, V1) --> (K47, V47)
  2         NULL
  3         NULL
  ...
  54        --> (K89, V89)
  ...

当执行put操作时，put（键，值）首先由代码检索键的哈希代码。在特定存储桶的列表中搜索时，需要使用带有模块操作的该值。然后，它在该列表上逐个元素执行搜索，并执行equals方法来检查键是否已经存在。如果键存在，则只替换值，如果不存在，则会在列表末尾添加一个新的成对键和值。

HashMap的伪代码类似于以下内容：

public HashMap {
    private List<List<KeyValue<K, V>>> keyValuesBuckets;

    public void put(K key, V value) {
       int hash = key.hashCode();
       int bucketPosition = hash % keyValuesBuckets.size();
       for (KeyValue kv : keyValuesBuckets.get(bucketPosition)) {
          if (kv.getKey().equals(key)) {
             // Key is present change the value and exit
             kv.setValue(value);
             return;
          }
       }
       // Key is not present
      keyValuesBuckets.get(bucketPosition).add(new KeyValue(key, value));
}

请注意，代码不是真正的代码。例如，没有检查空值，但它让您了解如何使用hashCode和equals方法检查相等性。

要更深入地了解其工作原理，请从[hashCode][1]的定义开始：

返回对象的哈希码值。支持此方法是为了哈希表的利益，例如HashMap提供的哈希表。

和[等于][2]

在javadoc中，您可以找到equals和hashCode必须提供的契约，以便类可以用作HashMap中的键：

hashCode的一般约定是：在Java应用程序的执行过程中，每当在同一对象上多次调用hashCode时，hashCode方法必须一致地返回相同的整数，前提是在对象的equals比较中使用的信息没有被修改。从应用程序的一次执行到同一应用程序的另一次执行，此整数不需要保持一致。如果根据equals（Object）方法，两个对象相等，那么对这两个对象中的每一个调用hashCode方法必须产生相同的整数结果。如果根据equals（java.lang.Object）方法，两个对象是不等的，那么对这两个对象中的每一个调用hashCode方法都必须产生不同的整数结果，这不是必需的。然而，程序员应该知道，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。[1]: https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode-- [2]: https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#equals-爪哇。lang.反对-