Простая реализация C # HashTable

Не сдавайте один из них вместе с колледжем. Как это выглядит в целом?

public class HashTable<T, TU>
    {
        private LinkedList<Tuple<T, TU>>[] _items;
        private int _fillFactor = 3;
        private int _size;

        public HashTable()
        {
            _items = new LinkedList<Tuple<T, TU>>[4];
        }

        public void Add(T key, TU value)
        {
            var pos = GetPosition(key, _items.Length);
            if (_items[pos] == null)
            {
                _items[pos] = new LinkedList<Tuple<T, TU>>();
            }
            if (_items[pos].Any(x=>x.Item1.Equals(key)))
            {
                throw new Exception("Duplicate key, cannot insert.");
            }
            _size++;
            if (NeedToGrow())
            {
                GrowAndReHash();
            }
            pos = GetPosition(key, _items.Length);
            if (_items[pos] == null)
            {
                _items[pos] = new LinkedList<Tuple<T, TU>>();
            }
            _items[pos].AddFirst(new Tuple<T, TU>(key, value));
        }

        public void Remove(T key)
        {
            var pos = GetPosition(key, _items.Length);
            if (_items[pos] != null)
            {
                var objToRemove = _items[pos].FirstOrDefault(item => item.Item1.Equals(key));
                if (objToRemove == null) return;
                _items[pos].Remove(objToRemove);
                _size--;
            }
            else
            {
                throw new Exception("Value not in HashTable.");
            }
        }

        public TU Get(T key)
        {
            var pos = GetPosition(key, _items.Length);
            foreach (var item in _items[pos].Where(item => item.Item1.Equals(key)))
            {
                return item.Item2;
            }
            throw new Exception("Key does not exist in HashTable.");
        }

        private void GrowAndReHash()
        {
            _fillFactor *= 2;
            var newItems = new LinkedList<Tuple<T, TU>>[_items.Length * 2];
            foreach (var item in _items.Where(x=>x != null))
            {
                foreach (var value in item)
                {
                    var pos = GetPosition(value.Item1, newItems.Length);
                    if (newItems[pos] == null)
                    {
                        newItems[pos] = new LinkedList<Tuple<T, TU>>();
                    }
                    newItems[pos].AddFirst(new Tuple<T, TU>(value.Item1, value.Item2));
                }
            }
            _items = newItems;
        }

        private int GetPosition(T key, int length)
        {
            var hash = key.GetHashCode();
            var pos = Math.Abs(hash % length);
            return pos;
        }

        private bool NeedToGrow()
        {
            return _size >= _fillFactor;
        }
    }
10 голосов | спросил user103053 20 PMpWed, 20 Apr 2016 19:13:38 +030013Wednesday 2016, 19:13:38

3 ответа


14

Несколько небольших точек:

public class HashTable<T, TU>

Используйте больше мнемонических имен, таких как TKey, TValue.

public class HashTable<T, TU>

Название указывает, как реализуется класс; назовите его после того, что он делает логически. Это карта или словарь, или хранилище значений ключа, или все, что вы хотите назвать. Это хэш-таблица - это механизм; классы имен после их семантики.

public class HashTable<T, TU>

Я ожидал бы, что карта будет внедрять соответствующие общие интерфейсы IDictionary, IEnumerable, ICollection и т. д.

private int _fillFactor = 3;

Почему 3? Объясните читателю, что здесь происходит.

_items = new LinkedList<Tuple<T, TU>>[4];

Почему 4?

throw new Exception("Duplicate key, cannot insert.");

Выбросьте более конкретные исключения.

        if (_items[pos] == null)
        {
            _items[pos] = new LinkedList<Tuple<T, TU>>();
        }
        if (_items[pos].Any(x=>x.Item1.Equals(key)))
        {

Это может быть else if.

        if (NeedToGrow())
        {
            GrowAndReHash();
        }

Вы никогда не называете NeedToGrow и GrowAndRehash отдельно, что указывает на то, что они - одно и то же. Вы можете сделать один метод под названием GrowAndRehashIfNecessary ().

public TU Get(T key)
public void Add(T key, TU value)

Вы также можете реализовать индекс.

var newItems = new LinkedList<Tuple<T, TU>>[_items.Length * 2];

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

public void Add(T key, TU value)
public void Remove(T key)

Добавить размеры и переименования, если таблица слишком заполнена, но Remove не изменяет размер и не перерисовывает, если таблица становится слишком пустой. По-видимому, вы сделали неявное и недокументированное дизайнерское решение, что многие добавления более вероятны, чем многие удаляет, и что в случае, когда происходит много удалений, вполне нормально тратить память. Было ли это решение преднамеренным или несчастным случаем?

Наконец, рассмотрим возможность изучения типа словаря; доступны источники .NET, а реализация хеш-таблицы словаря - интересное чтение. Вы получаете представление о том, как полнофункциональная и надежная функция должна быть рабочей лошадкой библиотек базового класса.

ответил Eric Lippert 20 PMpWed, 20 Apr 2016 19:41:44 +030041Wednesday 2016, 19:41:44
6
public class HashTable<T, TU>

Соглашение о присвоении имен типовым параметрам типа либо запускает их с буквой T (например, ---- +: = 2 =: + ----, TKey), или , чтобы назвать первый TValue, а второй T (больше параметров, чем это, перейдите с помощью U). TMeaningfulName выглядит как комбинация двух рекомендаций, минус часть «значимого имени».

Я бы рекомендовал переименовать их TU и TKey, так что:

TValue

Может быть так приятно читать:

public void Add(T key, TU value)

Я не уверен, почему вы пошли с классом public void Add(TKey key, TValue value) , когда Tuple<TKey, TValue> была бы более подходящей, по крайней мере, на первый взгляд (это достаточно для кода KeyValuePair<TKey,TValue>, правильно?). Это сделало бы это:

Dictionary

Вместо этого прочитайте:

if (_items[pos].Any(x=>x.Item1.Equals(key)))

Обратите внимание на пробелы вокруг оператора lambda if (_items[pos].Any(item => item.Key.Equals(key))) и описательный идентификатор вместе с более значимым => (vs. KeyValuePair.Key) делают его намного проще на глазу.


Это красный флаг:

Tuple.Item1

Не бросайте throw new Exception("Duplicate key, cannot insert."); . Вместо этого создайте наиболее значимое существующее исключение или создайте свой собственный. Я считаю, что System.Exception будет идеальным, так как это означает, что ArgumentException бросает, когда вы пытаетесь добавить дублирующий ключ.

Можно также проверить для клавиши Dictionary, а также бросить null.

То же самое:

ArgumentNullException

Вместо этого введите throw new Exception("Key does not exist in HashTable."); .

ответил Mathieu Guindon 20 PMpWed, 20 Apr 2016 19:40:40 +030040Wednesday 2016, 19:40:40
4

Это прекрасно выглядит. Вы ожидали бы, что HashTable будет реализовывать некоторые интерфейсы коллекций, такие как IEnumerable, поэтому он определенно неполный. Есть только две вещи, которые я могу изменить.

  • Я думаю, что вы злоупотребляете термином «коэффициент заполнения» здесь, переменная с этим именем действует больше как максимальная емкость.
  • В функции Add я бы не увеличивал _size, пока вы не вставите этот элемент. Я не вижу, как перефразирование может потерпеть неудачу, но я бы взял параноидальный подход и не увеличивал, пока работа не будет выполнена. Это означает, что NeedToGrow использует текущий размер.
ответил Pierre Menard 20 PMpWed, 20 Apr 2016 19:31:02 +030031Wednesday 2016, 19:31:02

Похожие вопросы

0
Реализация общего атрибута DropDownList и шаблона решения. Генетический алгоритм для угадывания пароля. Составление алетических модальных логических формул с использованием true treesfgets. () AlternativeMultiple аналогичные классы менеджера для обработки списков прокрутки. Простая альтернатива C ++ для исключений для встроенных систем. Исправлено уничтожение VBEMelsort. Сортировка с перехватом списков. Простая фаза. Заблокированная LoopCompile. root для больших чиселOOP парадигма реализация модели данных словаряEarly Access: динамически расширяющийся элемент ввода table16-бит Parity GeneratorStackEgg autoclickerMacro для создания объявления типаNim в Haskell, реализующий оптимальную стратегиюCompile-time-fixed templated integer rangeConvert WKT представления геометрий в GeoJsonLoading Data Warehouse с динамическим SQLRecursively с использованием отражения для объединения полейClone of Boost VariantDisjoint устанавливает реализациюУлучшить параллельный кэш с реактивными расширениями & Unity InterceptionquerySelectorВсего прокладки для браузеров, отличных от IE. Библиотека интерполяции строк. Игра Binginner Battleship в чат-сервере и клиенте Python /terminalBasic с использованием композиции WebSocketFunction с использованием библиотеки /реализации библиотеки std :: bindJSON C ++ 14

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132