Java 中的双重哈希

2025年3月17日 | 阅读 8 分钟

在编程中，当我们处理数据结构时，有时需要存储具有相同哈希值的两个对象。存储具有相同哈希值的两个对象是不可能的。为了解决这个问题，数据结构提供了冲突解决技术。在本节中，我们将只关注双重散列、其优点、示例和公式。

数据结构提供了以下冲突解决技术

分离链接（也称为开放散列）
开放寻址（也称为封闭散列）

线性探测
二次探测
双重散列

什么是双重散列？

它是一种用于避免冲突的开放寻址哈希表中的冲突解决技术。当两个键被散列到哈希表中的同一个索引时，就会发生冲突。发生冲突的原因是哈希表中的每个槽位都应该存储单个元素。

通常，散列技术包含一个哈希函数，该函数接受一个键并为该键生成哈希表索引。双重散列技术使用两个哈希函数，因此称为双重散列。如果第一个哈希函数产生冲突，第二个哈希函数会提供一个偏移量。换句话说，我们可以说当两个不同的对象具有相同的哈希值时，称为冲突。

哈希函数

哈希函数是一个接受一组字符（键）并将其映射到特定长度的值（称为哈希值或散列）的函数。这个过程称为散列。它用于数据库中的索引和定位项。它提供了一种简单的方法来查找与较短哈希值关联的较长值。它广泛用于加密。它也被称为哈希算法或消息摘要函数。

双重哈希函数

第一个哈希函数确定查找键的初始位置，第二个哈希函数用于确定探测序列中跳跃的大小。以下函数是双重散列的示例

或

在上述函数中，i 的值会不断递增，直到找到一个空槽。

如果表的大小是素数，双重散列效果很好。

其中 PRIME 是小于 tableSize 的素数。

如果上述函数计算出的偏移量已被其他对象占用，则表示存在冲突。一个好的哈希函数必须具备以下属性

快速计算。
与原始哈希函数不同。
永远不等于 0。

双重散列的优点

该技术不会产生任何聚集。
它是最好的探测形式，因为它比线性探测更快地找到哈希表中的下一个可用槽。
它在整个哈希表中产生记录的均匀分布。

双重散列示例

假设我们有一个大小为11的哈希表。我们想在哈希表中插入键20, 34, 45, 70, 56。让我们使用以下双重哈希函数将键插入哈希表中

h₁(k) = k mod 11 (第一个哈希函数)

h₂(k) = 8 - (k mod 8) (第二个哈希函数)

首先，我们将创建一个大小为 11 的哈希表。

让我们逐个插入键。

步骤：	键	哈希函数	索引	描述
1	20	h₁(20) = 20 mod 11	9	没有发生冲突。
2	34	h₁(34) = 34 mod 11	1	没有发生冲突。
3	45	h₁(45) = 45 mod 11	1	发生冲突，因为索引 1 已被 34 占用。现在我们将使用第二个哈希函数计算键 45 的索引。
3	45	h₂(45) = 8 - (45 mod 8) = 3 h(45, 1) = (1 + 1 * 3) mod 11	4	这里，我们取 i 的值为 1，因为发生了第一次冲突。请注意，此处 h₂ (k) 和 11 是互质的。h₂ (k) 的值必须小于表的大小。
4	70	h₁(70) = 70 mod 11	4	发生冲突，因为索引 4 已被 45 占用。现在我们将使用第二个哈希函数计算键 70 的索引。
4	70	h₂(70) = 8 - (70 mod 8) = 2 h(70, 1) = (4 + 1 * 2) mod 11	6	这里，我们取 i 的值为 1，因为发生了第一次冲突。请注意，此处 h₂ (k) 和 11 是互质的。h₂ (k) 的值必须小于表的大小。
5	56	h₁(56) = 56 mod 11	1	发生冲突，因为索引 1 已被 34 占用。现在我们将使用第二个哈希函数计算键 56 的索引。
		h₂(56) = 8 - (56 mod 8) = 8 h(56, 1) = (1 + 1 * 8) mod 11	9	再次发生冲突。索引 9 已被 20 占用。
		h(56, 2) = (1 + 2 * 8) mod 11	6	此处，i 的值增加 1，因为发生了第二次冲突。我们注意到又发生了冲突，因为索引 6 已被 70 占用。
		h(56, 3) = (1 + 3 * 8) mod 11	3	此处，i 的值增加 1。第三个索引是空的。因此，我们将 56 存储在索引 3。

*粗体显示的索引表示冲突。

插入所有键后，哈希表如下所示。

现在我们已经清楚地理解了双重散列。因此，我们可以轻松地区分线性探测和二次探测。

在线性探测中，如果在任何索引处发生冲突，我们会查找紧邻的下一个索引。如果下一个索引也被占用，我们会查找紧邻的下一个索引。这个过程会重复，直到找到一个空索引。

在二次探测中，如果在任何索引处发生冲突，我们会查找紧邻的下一个索引。如果下一个索引也被占用，那么我们将跳转到 i² 索引。

假设索引 2 已被占用，那么我们将查找 2²，即 4。这意味着从当前索引（即 2）向前查找 4 个索引。

同样，如果索引 3 也被占用，那么我们将查找 3²，即 9。这意味着从当前索引（即 3）向前查找 9 个索引。

双重散列插入元素的算法

设置 index = H(K); offset = H2(K)
如果表位置 index 已经包含该键，则无需插入。完成！
否则，如果表位置 index 为空，则在此处插入键。完成！
否则，发生冲突。设置 index = (index + offset) mod M。
如果 index == H(K)，则表已满！（抛出异常或扩大表。）否则转到步骤 2。

让我们在 Java 程序中实现上述算法。

双重散列 Java 程序

在以下 Java 程序中，我们在哈希表中实现了双重散列。

DoubleHashingExample.java

import java.util.Scanner;
import java.math.*;
/* Class LinkedHashEntry */
class HashEntry
{
    String key;
    int value;

   /* Constructor */
    HashEntry(String key, int value)
    {
        this.key = key;
        this.value = value;
    }
}

/* Class HashTable */
class HashTable
{
    private int TABLE_SIZE;
    private int size;
    private HashEntry[] table;
    private int primeSize;

   /* Constructor */
    public HashTable(int ts)
    {
        size = 0;
        TABLE_SIZE = ts;
        table = new HashEntry[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++)
            table[i] = null;
        primeSize = getPrime();
    }
   /* Function to get prime number less than table size for myhash2 function */
    public int getPrime()
    {
        for (int i = TABLE_SIZE - 1; i >= 1; i--)
            {
                int fact = 0;
                for (int j = 2; j <= (int) Math.sqrt(i); j++)
                    if (i % j == 0)
                        fact++;
                if (fact == 0)
                    return i;
            }
       /* Return a prime number */
        return 3;
    }
   /* Function to get number of key-value pairs */
    public int getSize()
    {
        return size;
    }
    public boolean isEmpty()
    {
        return size == 0;
    }
   /* Function to clear hash table */
    public void makeEmpty()
    {
        size = 0;
        for (int i = 0; i < TABLE_SIZE; i++)
            table[i] = null;
    }
   /* Function to get value of a key */
    public int get(String key)
    {
        int hash1 = myhash1( key );
        int hash2 = myhash2( key );
        while (table[hash1] != null && !table[hash1].key.equals(key))
            {
                hash1 += hash2;
                hash1 %= TABLE_SIZE;
            }
        return table[hash1].value;
    }
   /* Function to insert a key value pair */
    public void insert(String key, int value)
    {
        if (size == TABLE_SIZE)
            {
                System.out.println("Table full");
                return;
            }
        int hash1 = myhash1( key );
        int hash2 = myhash2( key );
        while (table[hash1] != null)
            {
                hash1 += hash2;
                hash1 %= TABLE_SIZE;
            }
        table[hash1] = new HashEntry(key, value);
        size++;
    }
   /* Function to remove a key */
    public void remove(String key)
    {
        int hash1 = myhash1( key );
        int hash2 = myhash2( key );
        while (table[hash1] != null && !table[hash1].key.equals(key))
            {
                hash1 += hash2;
                hash1 %= TABLE_SIZE;
            }
        table[hash1] = null;
        size--;
    }
   /* Function myhash which gives a hash value for a given string */
    private int myhash1(String x )
    {
        int hashVal = x.hashCode( );
        hashVal %= TABLE_SIZE;
        if (hashVal < 0)
            hashVal += TABLE_SIZE;
        return hashVal;
    }
   /* Function myhash function for double hashing */
    private int myhash2(String x )
    {
        int hashVal = x.hashCode( );
        hashVal %= TABLE_SIZE;
        if (hashVal < 0)
            hashVal += TABLE_SIZE;
        return primeSize - hashVal % primeSize;
    }
   /* Function to print hash table */
    public void printHashTable()
    {
        System.out.println("\nHash Table");
        for (int i = 0; i < TABLE_SIZE; i++)
            if (table[i] != null)
                System.out.println(table[i].key +" "+table[i].value);
    }
}

/* Class DoubleHashingHashTableTest */
public class DoubleHashingHashTableTest
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Hash Table Test\n\n");
        System.out.println("Enter size");
       /* Make object of HashTable */
        HashTable ht = new HashTable(scan.nextInt() );
        char ch;
       /*  Perform HashTable operations  */
        do
            {
                System.out.println("\nHash Table Operations\n");
                System.out.println("1. insert ");
                System.out.println("2. remove");
                System.out.println("3. get");
                System.out.println("4. check empty");
                System.out.println("5. clear");
                System.out.println("6. size");
                int choice = scan.nextInt();
                switch (choice)
                    {
                    case 1 :
                        System.out.println("Enter key and value");
                        ht.insert(scan.next(), scan.nextInt() );
                        break;
                    case 2 :
                        System.out.println("Enter key");
                        ht.remove( scan.next() );
                        break;
                    case 3 :
                        System.out.println("Enter key");
                        System.out.println("Value = "+ ht.get( scan.next() ));
                        break;
                    case 4 :
                        System.out.println("Empty Status " +ht.isEmpty());
                        break;
                    case 5 :
                        ht.makeEmpty();
                        System.out.println("Hash Table Cleared\n");
                        break;
                    case 6 :
                        System.out.println("Size = "+ ht.getSize() );
                        break;
                    default :
                        System.out.println("Wrong Entry\n ");
                        break;
                    }
               /* Display hash table */
                ht.printHashTable();
                System.out.println("\nDo you want to continue (Type y or n)\n");
                ch = scan.next().charAt(0);
            }
        while (ch == 'Y'|| ch == 'y');
    }
}

输出

下一主题Java 中的魔方

Java 中的双重哈希

什么是双重散列？

哈希函数

双重哈希函数

双重散列的优点

双重散列示例

双重散列插入元素的算法

双重散列 Java 程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的双重哈希

什么是双重散列？

哈希函数

双重哈希函数

双重散列的优点

双重散列示例

双重散列插入元素的算法

双重散列 Java 程序

相关帖子

Java 中的默认异常

Java 中 arr.length vs arr[0].length vs arr[1].length

Reference Class in Java

Java &0XFF 示例

Java 中的变量作用域

Travelling Salesman Problem

DoubleBuffer put() methods in Java with Examples

Java Program to Find Maximum Difference of Zeros and Ones in Binary String

Invert k-th Most Significant Bits of N in Java

Java Program to Find the Number of 'X' Total Shapes

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器