哈希算法如何将哈希值转为数组索引？自定义哈希表实现疑问

一、先修正你的结构问题 #

你给出的代码存在几个语法和逻辑上的小问题，先调整成更合理的基础结构：

public class HashBucket
{
    public object Key { get; set; }
    public ICollection<object> Values { get; set; } = new List<object>();
}

public class Hashtable
{
    private readonly HashBucket[] _buckets;
    private readonly int _bucketCount;

    public Hashtable(int bucketCount = 12)
    {
        _bucketCount = bucketCount;
        _buckets = new HashBucket[bucketCount];
    }

    public void Insert(object key, object value)
    {
        var bucketIndex = GetBucketIndex(key);
        // 后续处理冲突逻辑
    }

    // 核心：生成桶索引的哈希函数
    private int GetBucketIndex(object key)
    {
        // 实现逻辑在这里
    }
}

注：哈希表本质是键值对存储，所以Insert方法需要接收key和value两个参数；同时修正了数组初始化的语法错误。

二、生成桶数组索引的哈希函数算法 #

哈希函数的核心是把任意类型的键，转换成0到桶数组长度-1之间的整数，常用实现方式如下：

1. 利用.NET内置哈希值（最常用） #

所有.NET对象都继承了object.GetHashCode()方法，它会返回一个int类型的哈希值，但这个值可能为负且范围远超桶数组长度，需要做两步处理：

private int GetBucketIndex(object key)
{
    if (key == null)
        return 0; // 约定null键固定放在索引0
    
    // 取绝对值避免负数索引
    int hash = Math.Abs(key.GetHashCode());
    // 取模运算将哈希值映射到桶数组的索引范围内
    return hash % _bucketCount;
}

这种方式优点是简单高效，.NET内置的基本类型（如string、int）都已经实现了分布均匀的GetHashCode()，自定义类型也可以重写该方法优化哈希效果。

2. 针对特定类型的自定义哈希函数 #

如果内置哈希函数不符合需求，比如需要更均匀的分布，可以针对特定类型实现自定义哈希逻辑，比如经典的DJB2字符串哈希算法：

private int GetStringHash(string key)
{
    int hash = 5381;
    foreach (char c in key)
    {
        hash = ((hash << 5) + hash) + c; // 等价于 hash = hash * 33 + c
    }
    return Math.Abs(hash) % _bucketCount;
}

调用时可根据键类型分支处理：

private int GetBucketIndex(object key)
{
    if (key == null) return 0;
    if (key is string strKey)
        return GetStringHash(strKey);
    return Math.Abs(key.GetHashCode()) % _bucketCount;
}

3. 哈希冲突的补充处理 #

无论用哪种哈希函数，都可能出现不同键生成同一个桶索引的情况（哈希冲突），所以插入逻辑需要完善：

public void Insert(object key, object value)
{
    var bucketIndex = GetBucketIndex(key);
    var bucket = _buckets[bucketIndex];
    
    if (bucket == null)
    {
        bucket = new HashBucket { Key = key };
        bucket.Values.Add(value);
        _buckets[bucketIndex] = bucket;
    }
    else
    {
        if (bucket.Key.Equals(key))
        {
            // 同一个键，追加值（支持多值场景）
            bucket.Values.Add(value);
        }
        else
        {
            // 哈希冲突，建议将HashBucket调整为存储多个键值对的结构（比如链表或列表）
            // 例：把HashBucket的Key/Values改成List<KeyValuePair<object, object>>
        }
    }
}

三、关于“通过索引反向获取哈希值”的说明 #

哈希表的设计逻辑是键→哈希值→桶索引，但反过来桶索引无法反向推导回原始哈希值或键：

1. 取模运算会丢失信息：不同的哈希值取模后可能得到同一个索引，无法区分；
2. 哈希函数是单向的：大部分哈希函数都是不可逆的，无法从哈希值还原键。

如果需要获取某个索引桶里的内容，直接遍历_buckets[index]中的键值对即可，不需要反向获取哈希值。

内容的提问来源于stack exchange，提问作者Jaylen