java - Hashmap 是否使用随机访问？

Question

在 java 的 HashMap 中，我了解到哈希值存储在桶中，这有助于更快地搜索。
在检索时，它会检查哈希码并相应地找到桶号。

如果有从 1 到 10 的桶号，并且从哈希码中找到的桶号是桶号 5
。
控制权如何转移到 5 号桶？它是遍历存储桶 1 到存储桶 4 并到达 5 还是使用任何其他机制？

Answer 1

它是直接数组访问。没有迭代/遍历。但随后它必须遍历桶内的对象并与 比较equals。也许这让你感到困惑。

Answer 2

哈希表被实现为一个桶数组，因此它使用数组的随机访问索引来获取给定哈希的正确桶。

Answer 3

哈希函数用于定位桶。

如果有 10 个桶，例如，对于一组字符串，将字符值相加并散列到 10 个桶

让我们编写一个简单的哈希函数将字符串映射到 10 个桶中，

 For any non empty String, 

             hash function f = sum of (index of characters) % 10

示例：abc = 1+2+3 %10 = 6。所以“abc”最终出现在第 6 个桶中。xyz = 24+25+25 %10 = 7.5~ 8 。所以“xyz”最终出现在第 8 个桶中，依此类推

所以当你搜索 "xyz" 时，哈希函数直接找到这里的桶。

哈希函数是哈希映射工作的核心。

Answer 4

摘自 java.util.HashMap 代码

         /**
          * Adds a new entry with the specified key, value and hash code to
          * the specified bucket.  It is the responsibility of this
          * method to resize the table if appropriate.
          *
          * Subclass overrides this to alter the behavior of put method.
          */
         void addEntry(int hash, K key, V value, int bucketIndex) {
             Entry<K,V> e = table[bucketIndex];
             table[bucketIndex] = new Entry<>(hash, key, value, e);
             if (size++ >= threshold)
                 resize(2 * table.length);
         }

所以它是从一个数组中随机访问的。

Answer 5

在添加和检索值时有几种策略，其中一些是直接转换，开放寻址等基于这些，它存储和获取值的方式会改变。例如，在直接链接中，桶数组的每个空间都是指向链表的指针它包含散列到相同位置的键值对。因此，当您搜索该值时，它会使用给定值扫描整个列表。