37

我意识到 C# 和 .NET 通常已经有了 Hashtable 和 Dictionary 类。

任何人都可以在 C# 中演示 Hashtable 的实现吗？

更新：澄清一下，我不一定要寻找完整的实现，只是哈希表核心功能的一个示例（即添加、删除、按键查找）。

4

5 回答 5

128

问题被问了很久之后，所以我不希望获得太多的代表。但是，我认为编写自己的非常基本的示例（不到 90 行代码）会很有趣：

    public struct KeyValue<K, V>
    {
        public K Key { get; set; }
        public V Value { get; set; }
    }

    public class FixedSizeGenericHashTable<K,V>
    {
        private readonly int size;
        private readonly LinkedList<KeyValue<K,V>>[] items;

        public FixedSizeGenericHashTable(int size)
        {
            this.size = size;
            items = new LinkedList<KeyValue<K,V>>[size];
        }

        protected int GetArrayPosition(K key)
        {
            int position = key.GetHashCode() % size;
            return Math.Abs(position);
        }

        public V Find(K key)
        {
            int position = GetArrayPosition(key);
            LinkedList<KeyValue<K, V>> linkedList = GetLinkedList(position);
            foreach (KeyValue<K,V> item in linkedList)
            {
                if (item.Key.Equals(key))
                {
                    return item.Value;
                }
            }

            return default(V);
        }

        public void Add(K key, V value)
        {
            int position = GetArrayPosition(key);
            LinkedList<KeyValue<K, V>> linkedList = GetLinkedList(position);
            KeyValue<K, V> item = new KeyValue<K, V>() { Key = key, Value = value };
            linkedList.AddLast(item);
        }

        public void Remove(K key)
        {
            int position = GetArrayPosition(key);
            LinkedList<KeyValue<K, V>> linkedList = GetLinkedList(position);
            bool itemFound = false;
            KeyValue<K, V> foundItem = default(KeyValue<K, V>);
            foreach (KeyValue<K,V> item in linkedList)
            {
                if (item.Key.Equals(key))
                {
                    itemFound = true;
                    foundItem = item;
                }
            }

            if (itemFound)
            {
                linkedList.Remove(foundItem);
            }
        }

        protected LinkedList<KeyValue<K, V>> GetLinkedList(int position)
        {
            LinkedList<KeyValue<K, V>> linkedList = items[position];
            if (linkedList == null)
            {
                linkedList = new LinkedList<KeyValue<K, V>>();
                items[position] = linkedList;
            }

            return linkedList;
        }
    }

这是一个小测试应用程序：

 static void Main(string[] args)
        {
            FixedSizeGenericHashTable<string, string> hash = new FixedSizeGenericHashTable<string, string>(20);

            hash.Add("1", "item 1");
            hash.Add("2", "item 2");
            hash.Add("dsfdsdsd", "sadsadsadsad");

            string one = hash.Find("1");
            string two = hash.Find("2");
            string dsfdsdsd = hash.Find("dsfdsdsd");
            hash.Remove("1");
            Console.ReadLine();
        }

这不是最好的实现，但它适用于添加、删除和查找。它使用链接和简单的模算法来找到合适的桶。

于 2010-01-20T12:34:21.800 回答
9

你看过C5系列吗？您可以下载包含哈希表的源代码。

于 2009-03-09T12:04:12.157 回答
8

您可以看到如何使用反射器实现 .NET 哈希表（例如在 C# 中）

http://www.red-gate.com/products/reflector/

于 2009-03-09T12:08:44.907 回答
5

当然还有 Mono 版本的类库：

于 2009-03-09T12:24:49.360 回答