java基础：再哈希法解决哈希冲突代码示例

再哈希法（Rehashing）是解决哈希冲突的另一种方法。它与开放定址法不同，再哈希法使用多个哈希函数来确定冲突元素的位置，而不是在同一个哈希表中进行探测。

下面是一个使用再哈希法解决哈希冲突的示例代码：

public class RehashingHashTable {
    private Entry[] table;
    private int capacity;
    private HashFunction[] hashFunctions;

    public RehashingHashTable(int capacity) {
        this.capacity = capacity;
        table = new Entry[capacity];
        hashFunctions = new HashFunction[]{new HashFunction1(), new HashFunction2()};
    }

    public void put(int key, String value) {
        int index = hash(key);
        int probeCount = 0;
        while (table[index] != null) {
            if (table[index].key == key) {
                table[index].value = value;
                return;
            }
            index = rehash(index);  // 使用下一个哈希函数重新计算位置
            probeCount++;
            if (probeCount == capacity) {
                throw new IllegalStateException("Hash table is full.");
            }
        }
        table[index] = new Entry(key, value);
    }

    public String get(int key) {
        int index = hash(key);
        int probeCount = 0;
        while (table[index] != null) {
            if (table[index].key == key) {
                return table[index].value;
            }
            index = rehash(index);  // 使用下一个哈希函数重新计算位置
            probeCount++;
            if (probeCount == capacity || table[index] == null) {
                break;
            }
        }
        return null;
    }

    private int hash(int key) {
        return key % capacity;  // 初始哈希函数
    }

    private int rehash(int index) {
        int hashFunctionIndex = (index + 1) % hashFunctions.length;  // 切换到下一个哈希函数
        return hashFunctions[hashFunctionIndex].hash(index);  // 使用下一个哈希函数计算位置
    }

    // 哈希函数接口
    private interface HashFunction {
        int hash(int key);
    }

    // 哈希函数1
    private static class HashFunction1 implements HashFunction {
        public int hash(int key) {
            // 实现自己的哈希函数逻辑
            return key % capacity;
        }
    }

    // 哈希函数2
    private static class HashFunction2 implements HashFunction {
        public int hash(int key) {
            // 实现自己的哈希函数逻辑
            return (key + 1) % capacity;
        }
    }

    private static class Entry {
        private int key;
        private String value;

        public Entry(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        RehashingHashTable hashTable = new RehashingHashTable(10);
        hashTable.put(1, "Value 1");
        hashTable.put(11, "Value 11");
        hashTable.put(21, "Value 21");
        hashTable.put(31, "Value 31");

        System.out.println(hashTable.get(1));   // Output: Value 1
        System.out.println(hashTable.get(11));  // Output: Value 11
        System.out.println(hashTable.get(21));  // Output: Value 21
        System.out.println(hashTable.get(31));  // Output: Value 31
    }
}

在上面的示例代码中，我们创建了一个使用再哈希法解决哈希冲突的哈希表 RehashingHashTable。它包含了一个主哈希函数 hash() 和多个辅助哈希函数 hashFunctions。在插入和查找操作中，当发生哈希冲突时，我们通过切换到下一个哈希函数来重新计算元素的位置。

通过使用多个哈希函数，再哈希法可以增加哈希冲突发生的概率，从而减少冲突的数量，提高哈希表的性能。每个哈希函数可以使用不同的算法和参数，以便在不同的情况下产生再哈希法（Rehashing）是一种解决哈希冲突的方法，它使用不同的哈希函数来重新计算冲突的键的位置。简单来说，当发生哈希冲突时，再哈希法会应用另一个哈希函数，将冲突的键映射到另一个位置。

具体来说，再哈希法使用两个或多个哈希函数。当发生哈希冲突时，通过应用不同的哈希函数来重新计算键的位置，直到找到一个空槽位或者遍历完所有的哈希函数。这样可以将冲突的键映射到不同的位置，减少冲突的概率。

再哈希法的实现可以采用多种策略。一种常见的策略是使用哈希函数序列，每次发生冲突时按顺序选择下一个哈希函数。另一种策略是根据冲突次数选择哈希函数，例如，使用线性探测来选择下一个哈希函数。

再哈希法相对于开放定址法有一些优势。它可以减少聚集现象（元素集中在同一位置），并且在查找效率方面可能更好。然而，再哈希法也可能存在一些问题，如哈希函数的选择和冲突的处理等。

总的来说，再哈希法是一种使用不同的哈希函数来解决哈希冲突的方法。通过重新计算键的位置，可以降低冲突的概率，提高哈希表的性能。