如何评估自定义哈希函数

Question

我有一个带有自定义哈希函数的Dictionary。我想测试散列函数，因为即使它为我的测试值返回不同的散列结果，由于模%运算，其中一些结果可能仍然映射到同一个bucket。那么，如何检查C#Dictionary中是否存在与自定义哈希函数的冲突并改进该函数呢？

这是一个开发测试，用于微调哈希函数，不会投入生产，因此不用担心其他版本中内部实现的更改！！！

在C++中，可以获取映射的bucket大小来检查碰撞状态，但我在C#中找不到这样做的方法。我怎样才能知道Dictionary是否发生碰撞？

Answer 1

您可以通过以下方式获取内部bucket：

var dictionary = new Dictionary<string, int>();
dictionary.Add("a", 8);
dictionary.Add("b", 1);
var buckets = dictionary.GetType().GetField("_buckets", BindingFlags.NonPublic | BindingFlags.Instance)
.GetValue(dictionary); // use "buckets" for 4.x

Answer 2

您最好创建一个自定义Dictionary实现，该实现更改Add和Remove方法，以检查基于元素的计算机GetHashCode的哈希冲突。你可以用一个"；真实的"；CCD_ 9内部进行存储元素的实际工作。

这是一个示例版本。您可以根据期望的哈希类型来优化Add和Remove方法。

public class CollisionDetectingDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
private readonly Dictionary<TKey, TValue> InternalDictionary = new Dictionary<TKey, TValue>();
private readonly List<int> HashCodesInDictionary = new List<int>();
public event Action<int, TKey, IEnumerable<TKey>> HashCollision; 
public TValue this[TKey key] { get => InternalDictionary[key]; set => InternalDictionary[key] = value; }
public ICollection<TKey> Keys => InternalDictionary.Keys;
public ICollection<TValue> Values => InternalDictionary.Values;
public int Count => InternalDictionary.Count;
public bool IsReadOnly => false;
public void Add(TKey key, TValue value)
{
Add(new KeyValuePair<TKey, TValue>(key, value));
}
public void Add(KeyValuePair<TKey, TValue> item)
{
var hashCode = item.Key.GetHashCode();
if (HashCodesInDictionary.Contains(hashCode))
{
var collisions = GetKeysByHashCode(hashCode);
HashCollision?.Invoke(hashCode, item.Key, collisions);
}
Add(item);
}
private IEnumerable<TKey> GetKeysByHashCode(int hashCode)
{
foreach (var key in Keys)
{
if(key.GetHashCode() == hashCode)
{
yield return key;
}
}
}
public void Clear()
{
InternalDictionary.Clear();
}
public bool Contains(KeyValuePair<TKey, TValue> item)
{
return InternalDictionary.Contains(item);
}
public bool ContainsKey(TKey key)
{
return InternalDictionary.ContainsKey(key);
}
public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
((IDictionary<TKey,TValue>)InternalDictionary).CopyTo(array, arrayIndex);
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
return InternalDictionary.GetEnumerator();
}
public bool Remove(TKey key)
{
var hashCode = key.GetHashCode();
if(GetKeysByHashCode(hashCode).Count() == 1)
{
HashCodesInDictionary.Remove(hashCode);
}
return InternalDictionary.Remove(key);
}
public bool Remove(KeyValuePair<TKey, TValue> item)
{
return Remove(item.Key);
}
public bool TryGetValue(TKey key, out TValue value)
{
return InternalDictionary.TryGetValue(key, out value);
}
IEnumerator IEnumerable.GetEnumerator()
{
return InternalDictionary.GetEnumerator();
}
}