Java使用什么散列函数来实现Hashtable类？

5 回答

• 26

  当在OpenJDK中向HashMap添加或请求密钥时，执行流程如下：

  • 使用开发人员定义的 hashCode() 方法将密钥转换为32位值 .

  • 然后将32位值转换为 second hash function （其中Andrew的答案包含源代码）到哈希表内的偏移量中 . 第二个哈希函数由HashMap的实现提供，并且不能被开发人员覆盖 .

  • 哈希表的相应条目包含对链表的引用或null，如果哈希表中尚不存在该键 . 如果存在冲突（具有相同偏移的多个键），则将键及其值简单地收集在单个链接列表中 .

  如果选择适当高的哈希表大小，则冲突的数量将受到限制 . 因此，单个查找平均只需要恒定的时间 . 这称为预期的恒定时间 . 但是，如果攻击者控制插入哈希表的密钥并了解正在使用的哈希算法，他可能会引发大量哈希冲突，从而迫使线性查找时间 . 这就是为什么最近一些哈希表实现已被更改为包含一个随机元素，使攻击者更难以预测哪些键会导致冲突 .

  一些ASCII艺术

  key.hashCode()
       |
       | 32-bit value
       |                              hash table
       V                            +------------+    +----------------------+
  HashMap.hash() --+                | reference  | -> | key1 | value1 | null |
                   |                |------------|    +----------------------+
                   | modulo size    | null       |
                   | = offset       |------------|    +---------------------+
                   +--------------> | reference  | -> | key2 | value2 | ref |
                                    |------------|    +---------------------+
                                    |    ....    |                       |
                                                        +----------------+
                                                        V
                                                      +----------------------+
                                                      | key3 | value3 | null |
                                                      +----------------------+
  

  回复于 2024-04-26T07:48:45+08:00
• 4

  根据hashmap的源代码，每个hashCode都使用以下方法进行哈希处理：

  /**
   * Applies a supplemental hash function to a given hashCode, which
   * defends against poor quality hash functions.  This is critical
   * because HashMap uses power-of-two length hash tables, that
   * otherwise encounter collisions for hashCodes that do not differ
   * in lower bits. Note: Null keys always map to hash 0, thus index 0.
   */
  static int hash(int h) {
      // This function ensures that hashCodes that differ only by
      // constant multiples at each bit position have a bounded
      // number of collisions (approximately 8 at default load factor).
      h ^= (h >>> 20) ^ (h >>> 12);
      return h ^ (h >>> 7) ^ (h >>> 4);
  }
  

  每个hashCode再次进行哈希处理的原因是为了进一步防止冲突（参见上面的注释）

  HashMap还使用一种方法来确定哈希码的索引（因为长度总是2的幂，你可以使用＆而不是％）：

  /**
   * Returns index for hash code h.
   */
  static int indexFor(int h, int length) {
      return h & (length-1);
  }
  

  put方法看起来像：

  int hash = hash(key.hashCode());
  int i = indexFor(hash, table.length);
  

  哈希码的目的是为给定对象提供唯一的整数表示 . 那么，有意义的是，Integer的hashCode方法只返回值，因为每个值对于该Integer对象都是唯一的 .

  回复于 2024-04-26T07:48:45+08:00
• -1

  哈希一般分为两个步骤：a . HashCode b . 压缩

  在步骤a . 生成与您的密钥对应的整数 . 这可以在Java中修改 .

  在步骤b中 . Java应用压缩技术来映射步骤a返回的整数 . 到hashmap或hashtable中的一个槽 . 这种压缩技术无法改变 .

  回复于 2024-04-26T07:48:45+08:00
• 0

  我认为这里的概念存在一些混淆 . 散列函数将可变大小的输入映射到固定大小的输出（散列值） . 对于Java对象，输出是32位有符号整数 .

  Java的Hashtable使用散列值作为存储实际对象的数组的索引，将模数算术和冲突考虑在内 . 但是，这不是散列 .

  java.util.HashMap实现在索引之前对哈希值执行一些额外的位交换，以防止在某些情况下发生过多冲突 . 它被称为“额外哈希”，但我不认为这是一个正确的术语 .

  回复于 2024-04-26T07:48:45+08:00
• 88

  换句话说，第二次散列只是查找将存储新键值对的bucket数组的索引号 . 完成此映射以从密钥obj的哈希码的较大int值获得索引号 . 现在，如果两个不相等的密钥对象具有相同的哈希码，则会发生冲突，因为它们将映射到相同的数组索引 . 在这种情况下，第二个键及其值将被添加到链接列表中 . 这里数组索引将指向添加的最后一个节点 .

  回复于 2024-04-26T07:48:45+08:00