使用HashSet作为底层存储复制字典
今天有人问我一个问题，要求我重新执行字典.我的解决方案是使用一个HashSet作为存储，并使用一个类来表示KeyValue对。在这个类中，我重写GetHashCode和Equals方法，以便将KeyValue对实例添加到HashSet中。
然后，我阅读了C#字典的源代码，发现它使用数组进行存储，并通过数组循环查找匹配的键值。
我的方法正确吗？当前字典在C#中实现的优势是什么？提前谢谢。
public class MyDictionary<K,V>
{
private class KV
{
public K Key {get;set;}
public V Value {get;set;}
public override int GetHashCode()
{
return Key.GetHashCode();
}
public override bool Equals(object o)
{
var obj = ((KV)o).Key;
return Key.Equals(obj);
}
}
private readonly HashSet<KV> _store = new HashSet<KV>();
public void Add(K key, V value)
{
_store.Add(new KV{Key = key, Value = value});
}
public V this[K key]
{
get
{
KV _kv;
if (_store.TryGetValue(new KV{Key = key}, out _kv))
{
return _kv.Value;
}
else
{
return default(V);
}
}
set
{
this.Add(key, value);
}
}
}回答 3
Stack Overflow用户
发布于 2018-10-12 18:29:34
您认为HashSet是如何实现的？您在Dictionary中看到的代码将非常类似于HashSet内部的代码。两者都由一个数组支持，该数组存储共享散列的所有键项的集合，只是一个存储一个键和一个对，另一个只存储它自己的键。
如果您只是问为什么Dictionary的开发人员重新实现了一些类似于HashSet中的代码，而不是实际上在内部使用实际的HashSet，我们只能猜测。如果他们愿意的话，他们当然可以从外部观察者的角度来创造功能相同的结果。
Stack Overflow用户
发布于 2018-10-11 23:25:32
什么是优势..。使用用于存储的数组，并在数组中循环查找匹配的键值。
我可以从Java的角度来回答这个问题。我认为它在C#中非常相似。
来自哈希集的get的大O时间复杂度是O(1)，而数组是O(n)。天真地，人们可能会认为hashset会表现得更好。但没那么简单。计算哈希码的代价相对较高，每个类都提供了自己的散列算法，因此哈希分布的运行时间和质量会有很大差异。(对于每个对象来说，类返回相同的散列是低效但完全合法的。存储此类对象的基于哈希的集合将退化为数组性能。)
所有这一切的结果是，尽管理论性能不同，但对于小型集合(这是典型程序中的绝大多数集合)来说，迭代数组比计算哈希更快。Google在他们的Android中引入了一种基于数组的地图作为hashmap的替代方案，并且他们建议基于数组的版本在10到100个元素集合上表现得更好。不确定的范围是因为，正如我提到的，哈希的成本是不同的。
底线是..。如果性能很重要，忘记“大O”，相信你的基准。
Stack Overflow用户
发布于 2018-10-11 23:08:00
实现的问题是，HashSet只为指定的键存储一个条目，在您的示例中是哈希值。因此，如果调用者想要向字典中添加两个碰巧具有相同哈希值的条目，那么只存储第一个条目，而忽略第二个条目。
字典通常被实现为与哈希值匹配的条目列表，这样就可以有多个具有相同哈希值的条目。这确实使它变得更加复杂，因为在添加/删除/查找时，您需要处理列表。
https://stackoverflow.com/questions/52769812
复制相似问题
腾讯云开发者
