Хеш-таблицы с длинными (более 100 символов) именами клавиш - PullRequest
Новая
       7

Хеш-таблицы с длинными (более 100 символов) именами клавиш

0 голосов
/ 19 сентября 2018

Я работаю над структурой данных для моей утилиты, и я ХОЧУ создать хеш-таблицу, ключом которой является очень длинная строка, в частности путь к файлу.Существует ряд причин, по которым это имеет смысл с точки зрения данных, в основном тот факт, что путь гарантированно уникален.Тем не менее, каждый пример хеш-таблицы, который я видел, имеет очень короткие ключи и потенциально длинные значения.Итак, мне интересно, если это просто функция простых примеров?Или есть эксплуатационная или техническая причина не использовать длинные ключи?Я буду использовать $variable = New-Object Collections.Specialized.OrderedDictionary для не зависящего от версии заказа, если это будет иметь значение.

1 Ответ

0 голосов
/ 19 сентября 2018

Я думаю, что у вас все в порядке, чтобы иметь ключи с длинной строкой.

Под капотом поиск ключей в OrderedDictionary делает это в 

if (objectsTable.Contains(key)) {

objectsTable имеет тип Hashtable

Если вы будете следовать цепочке получения хеша в классе Hashtable, вы получите следующее: https://referencesource.microsoft.com/#mscorlib/system/collections/hashtable.cs,4f6addb8551463cf

    // Internal method to get the hash code for an Object.  This will call
    // GetHashCode() on each object if you haven't provided an IHashCodeProvider
    // instance.  Otherwise, it calls hcp.GetHashCode(obj).
    protected virtual int GetHash(Object key)
    {
        if (_keycomparer != null)
            return _keycomparer.GetHashCode(key);
        return key.GetHashCode();
    }

Итак, вопрос становитсяКакова стоимость получения HashCode на строку?https://referencesource.microsoft.com/#mscorlib/system/string.cs

Функция GetHashCode, которую вы увидите, является циклом, но это только функция O (n), поскольку она растет только в зависимости от длины строки.Вы заметите, что вычисление для хэша немного отличается на 32-битных машинах, чем на других, но O (n) является худшим случаем для расширения алгоритма.

Есть другие части функции,но я думаю, что это ключевая часть, поскольку она может расти (src - это символ *, означающий указание на символы в строке). 

#if WIN32
                    // 32 bit machines.
                    int* pint = (int *)src;
                    int len = this.Length;
                    while (len > 2)
                    {
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0];
                        hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ pint[1];
                        pint += 2;
                        len  -= 4;
                    }

                    if (len > 0)
                    {
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0];
                    }
#else
                    int     c;
                    char *s = src;
                    while ((c = s[0]) != 0) {
                        hash1 = ((hash1 << 5) + hash1) ^ c;
                        c = s[1];
                        if (c == 0)
                            break;
                        hash2 = ((hash2 << 5) + hash2) ^ c;
                        s += 2;
                    }
#endif
...