Что является примером реализации Hashtable в C #?

Question

Я понимаю, что C # и .NET в целом уже имеют классы Hashtable и Dictionary.

Может ли кто-нибудь продемонстрировать в C # реализацию Hashtable?

Обновление: Чтобы уточнить, я не обязательно ищу полную реализацию, просто пример основных функций хеш-таблицы (то есть добавление, удаление, поиск по ключу).

Answer 1

Вскоре после того, как вопрос задан, я не ожидаю много повторений. Однако я решил, что было бы интересно написать собственный базовый пример (менее чем в 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();
        }

Это не лучшая реализация, но она работает для Add, Remove и Find. Он использует цепочку и простой алгоритм по модулю, чтобы найти соответствующий сегмент.

Answer 2

Вы можете увидеть, как реализована .NET Hashtable (например, в C #) с помощью отражателя

http://www.red -gate.com / продукты / отражатель /

Answer 3

Вы смотрели коллекции C5 ? Вы можете загрузить исходный код , который включает в себя хеш-таблицу.

Answer 4

Конечно, есть также Mono-версия библиотек классов:

• System.Collections.Hashtable

• System.Collections.Generic.Dictionary

Answer 5

Вы также можете посмотреть реализацию Hashtable из Mono здесь:

http://anonsvn.mono -project.com / ViewVC / багажник / MCS / класс / corlib / System.Collections / Hashtable.cs? Пересмотр = 111788 & вид = Разметка

Answer 6

Вы можете просмотреть простую хеш-таблицу «только для роста» здесь , которая должна дать вам представление о простой реализации.

Отказ от ответственности: Возможно, в коде есть несколько ошибок, но принцип тот же:)