代码之家 › 专栏 › 技术社区 › Helic

使用HashSet作为底层存储来复制字典

hashset dictionary c#

Helic · 技术社区 · 7 年前

然后我阅读了C#Dictionary的源代码,发现它使用数组进行存储,并通过数组循环查找匹配的键值。

我的方法正确吗?当前在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);
        }
    }
}

4 回复 | 直到 7 年前

Servy 7 年前

你觉得呢 HashSet 实施了什么?你看到的代码 Dictionary 看起来非常类似于 哈希集 . 两者都由一个数组支持,该数组存储共享散列的所有键控项的集合,一个数组只存储一个键和一对,另一个数组只存储自己的键。

如果你只是问为什么开发商 字典 哈希集 而不是实际使用在内部,我们只能猜测。他们很自然能够如果他们愿意,他们可以从外部观察者的角度创造功能上相同的结果。

StackOverthrow 7 年前

什么是优势。。。使用数组进行存储,并在数组中循环查找匹配的键值[?]

从hashset获取数据的时间复杂度是O(1),而数组的时间复杂度是O(n)。天真地说,人们可能会认为hashset的性能会更好。但没那么简单。计算哈希代码的成本相对较高,而且每个类都提供自己的哈希算法,因此哈希分布的运行时间和质量可能会有很大的差异(一个类为每个对象返回相同的哈希值是低效的,但却是完全合法的。存储此类对象的基于哈希的集合将退化为数组性能。)

底线。。。如果性能很重要的话,忘掉Big O,相信你的基准。

hatchet - done with SOverflow 7 年前

使用字典的原因是因为它写得很好,经过了很好的测试,已经完成了,而且很有效。

替换与已添加的键关联的值时,代码出现问题。以下代码:

dict["hi"]=10;
dict["hi"]=4;
Console.WriteLine(dict["hi"]);

10 和你们班一起。字典将输出(正确) 4 .

至于数组的使用,HashSet和Dictionary都在实现中使用它们。

哈希集

    private int[] m_buckets;
    private HashSet<T>.Slot[] m_slots;

字典

    private int[] buckets;
    private Dictionary<TKey, TValue>.Entry[] entries;

HashSet和Dictionary不会通过它们的数组循环查找键/值。它们使用hashcode值的模来直接索引到bucket数组中。bucket数组中的值指向slot或entries数组。然后,它们在具有相同哈希码或冲突哈希码的键列表上循环(两个不同的哈希码在应用模后产生相同的值)。这些小冲突列表位于slot或entries数组中,通常非常小,通常只有一个元素。

为什么字典不直接实现在HashSet上?因为这两个班做两件不同的事。HashSet旨在存储一组唯一的密钥。字典面向存储与唯一键相关的值。您试图使用HashSet来存储一个值,方法是将它嵌入到键(这是一个对象)中。但我指出了为什么这行不通。这是因为HashSet不接受值的概念。它只关心钥匙。所以不适合当字典用。现在,您可以使用Dictionary来实现HashSet,但这将是一种浪费,因为Dictionary中有专门用于处理值的代码和内存。有两个类,每个类都是为了实现一个特定的目的。它们很相似,但不一样

-1

Phil Wright 7 年前

实现的问题是HashSet只存储指定键的一个条目,在本例中是hash值。因此,如果调用者希望向字典中添加两个恰好具有相同哈希值的条目,则只存储第一个条目,而忽略第二个条目。

字典通常实现为与哈希值匹配的条目列表,这样就可以有多个具有相同哈希值的条目。这确实使它更加复杂,因为在添加/删除/查找时,您需要处理列表。