Реализация Dictionary на основе списка или вектора

Question

Задание: реализовать свой обобщенный Dictionary на основе списка или массива.

Вопрос: список или массив лучше выбрать за основу? На сколько знаю, если брать список то поиск будет O(n), если отсортированный - O(log n), но в Dictionary должен же быть O(1). Знаю что в .net Dictionary написан на хеш-таблице, возможно ли написать хеш-таблицу на основе массива или списка? Подскажите какой выбор будет оптимальней?

Answer 1

В итоге сделала на двухсвязном списке. Вот если кому-то интересно. Буду рада любым комментариям.

public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>
    {
        private readonly DoublyLinkedList<KeyValuePair<TKey, TValue>> _items;

        public TValue this[TKey key] 
        { 
            get => _items.FirstOrDefault(item => item.Key.Equals(key)).Value;
            set => Add(key, value);
        }

        public ICollection<TKey> Keys => (ICollection<TKey>)_items.Select(item => item.Key);

        public ICollection<TValue> Values => (ICollection<TValue>)_items.Select(item => item.Value);

        public int Count => _items.Count;

        public bool IsReadOnly => false;

        public Dictionary()
        {
            _items = new DoublyLinkedList<KeyValuePair<TKey, TValue>>();
        }

        public void Add(TKey key, TValue value)
        {
            if (key == null)
                throw new ArgumentException(nameof(key));
            if (value == null)
                throw new ArgumentException(nameof(value));
            Add(new KeyValuePair<TKey, TValue>(key, value));
        }

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            if (ContainsKey(item.Key))
                throw new ArgumentException($"The dictionary already contains a value with key {item.Key}", nameof(item));
            _items.Add(item);
        }

        public void Clear()
        {
            _items.Clear();
        }

        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            return _items.Contains(item);
        }

        public bool ContainsKey(TKey key)
        {
            if (key == null)
                throw new ArgumentNullException(nameof(key));
            return _items.Any(item => item.Key.Equals(key));
        }

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
        {
            _items.CopyTo(array, index);
        }

        public bool Remove(TKey key)
        {
            if (key == null)
                throw new ArgumentNullException(nameof(key));
            return Remove(_items.FirstOrDefault(item => item.Key.Equals(key)));
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            if(!ContainsKey(item.Key))
                return false;
            return _items.Remove(item);
        }

        public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value)
        {
            if (!ContainsKey(key))
            {
                value = default(TValue);
                return false;
            }
            value = this[key];
            return true;
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            foreach (var item in _items)
            {
                yield return item;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable)this).GetEnumerator();
        }

БЛОГ НА HUSL

Реализация Dictionary на основе списка или вектора

Ответы (1 шт):