hashtable - 调整表大小时发现哈希函数错误

Question

在准备考试时，我遇到了一个关于哈希表的问题。我得到一个长度为 11 的表，其中包含以下哈希函数：

h(k,i) = ( k mod 13 + i * (1 + k mod 7) ) mod 11

然后将哈希表的大小调整为 12。因此新的哈希函数变为：

h'(k,i) = ( k mod 13 + i * (1 + k mod 7) ) mod 12

会出现哪些问题？

Answer 1

问题是哈希函数变得更糟。

在第一种情况下， 和 的不同组合在 11 个哈希箱中的分布k非常i均匀。在第二种情况下，分布不是那么均匀 - 特别是，散列函数的结果的组合数量k明显i更高0。

当然，在考试期间，人们可能不得不争论为什么会这样。它在某种程度上与

• k mod 13 是一个介于 0 和12之间的值
• k mod 7 是介于 0 和6之间的值（除以 12）
• 也许，不知何故：11 是一个素数，而 12 有很多除数......

但是（至少对我而言）很难找到超越这些琐碎见解的令人信服的推理。也许你有另一个基于此的想法。

import java.util.LinkedHashMap;
import java.util.Map;


public class HashTest
{
    public static void main(String[] args)
    {
        int maxK = 30;
        int maxI = 30;
        System.out.println(computeFrequencies(h0, maxK, maxI));
        System.out.println(computeFrequencies(h1, maxK, maxI));
    }

    private static Map<Integer, Integer> computeFrequencies(
        Hash hash, int maxK, int maxI)
    {
        Map<Integer, Integer> frequencies = 
            new LinkedHashMap<Integer, Integer>();
        for (int k=0; k<maxK; k++)
        {
            for (int i=0; i<maxI; i++)
            {
                int value = hash.compute(k, i);
                Integer count = frequencies.get(value);
                if (count == null)
                {
                    count = 0;
                }
                frequencies.put(value, count+1);
            }
        }
        return frequencies;
    }

    private static interface Hash
    {
        int compute(int k, int i);
    }

    private static final Hash h0 = new Hash()
    {
        @Override
        public int compute(int k, int i)
        {
            return ((k % 13) + i * (1 + (k % 7))) % 11;
        }
    };
    private static final Hash h1 = new Hash()
    {
        @Override
        public int compute(int k, int i)
        {
            return ((k % 13) + i * (1 + (k % 7))) % 12;
        }
    };

}