В C# базовый словарь (хэш) осуществление


Я реализовал очень простой хэш-структура данных с базовым набором/получить методы. Хорошим примером использования этой реализации будет в телефонной книге. Я использовал как под структуры хранения данных в массив, состоящий из связанных списков.

Пожалуйста, просмотрите код в эти требования.

public class MyHash
{
    private LinkedList<string>[] storage;

    public MyHash()
    {
        storage = new LinkedList<string>[26]; //english alphabet
    }

    private int HashFunction(string key)
    {
        //maps first character of name to a 0:25 index
        return key.ToLower().ToCharArray()[0] - 97;
    }

    public string this[string key]
    {
        get {
            var list = storage[HashFunction(key)];
            if (list != null)
            {
                foreach (var item in list)
                {
                    if (item.Split(':')[0] == key)
                        return item.Split(':')[1];
                }
            }
            return "Not found!";
        }
        set {
            if (storage[HashFunction(key)] == null)
                storage[HashFunction(key)] = new LinkedList<string>();
            storage[HashFunction(key)].AddLast(key + ":" + value);
        }
    }
}


362
3
задан 23 февраля 2018 в 10:02 Источник Поделиться
Комментарии
1 ответ

Есть несколько (основных) проблем с этим классом:


  • Ключи, которые содержат : символ не может быть использован, чтобы посмотреть их значения, и значений, которые содержат : характер лишь частично возвращаются. Кроме того, этот класс не может обрабатывать null значения (она возвращает пустую строку вместо). Не маш ключей и значений в одно значение, используя ключ-значение объекта вместо (например, KeyValuePair<TKey, TValue>).

  • Ключи, которые начинаются с ничего, кроме [a-zA-Z] вызвать IndexOutOfRangeException. Это нигде не задокументирован, и нет никаких очевидных причин, почему такие ключи нельзя (телефонной книги не только в странах с латинским алфавитом, в конце концов). Почему бы не использовать модуль хэш-значение и количество ведер?

  • Несуществующие ключи производить "магические" значения, которые не документированы в любом месте. Кроме того, абонент не сможет отличить несуществующий ключ и фактический (действительный) "Not found!" значение. Возможно, вы захотите вместо того, чтобы бросать исключение. Поочередно, вы могли бы дать TryGetValue метод вместо этого.

  • Перезапись значение для существующего ключа не представляется возможным. Ваш класс будет хранить оба значения (почему?), но поиски будем продолжать возвращать первое значение. Я ожидаю, что новая запись заменит предыдущую. Если это не обычное поведение, то я бы ожидать, что должно быть задокументировано и соответствующим исключение быть брошенным.

  • Ваш хэш-функции-это плохо выбрали. В идеале, вы хотите, чтобы распространять записи через ведра как можно более равномерно, так что каждый запрос уходит примерно одинаковое количество времени в среднем. Если элементы сосредоточены только в нескольких ведер (некоторые символы используются более часто, чем другие), то для поиска таких ключей будет медленнее. Почему бы не использовать key.GetHashCode() вместо того, или пусть абонент обеспечивает хеширование метод в конструкторе?

  • Через определенное количество ведер означает, что время поиска существенно \$О(П)\ долл \$О(1)\$. Поиск ведро занимает постоянное время, при поиске через несколько записей в ведро занимает линейное время, так что вы хотите, чтобы ограничить количество записей в ведро (в идеале до 1). Что требуется какое-то изменение стратегии.

Другие незначительные проблемы:


  • По телефону Split(':') и HashFunction несколько раз вы делаете ту же работу несколько раз. Только один раз им позвонить и сохранить результат в переменной.

  • Некоторые имена могли бы уточнить немного: MyHashTable или MyHashMap вместо MyHashи buckets вместо storage.

  • Отправляясь на обычную реализацию не только удобен в использовании, его бы тоже вам помогли избежать некоторых из перечисленных проблем: вы бы не смогли Маш ключи и значения вместе или использовать суб-оптимальные-символ 'хэш'.

4
ответ дан 23 февраля 2018 в 09:02 Источник Поделиться