Поиск HashTable медленнее, когда ключом являются строки, а строки содержат пробелы

Question

Сегодня я обсуждал с другим разработчиком ограничение в сторонней библиотеке, где мы не могли использовать пробелы в строке. Это объясняется тем, что строки использовались в качестве ключей в .NET Hashtable, и что поиск в .NET HashTable был значительно медленнее, когда ключи содержали пробелы.

Теперь, когда мне лень писать тест, но я все еще хочу понять, почему это так, я задаю свой вопрос здесь:

Медленнее ли искать в Hashtable, когда используемая строка содержит пробел?

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

Спасибо!

Answer 1

Прямо из Источник ротора , ядро ​​метода String.GetHashcode:

                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;
                }

Что я могу из этого сделать: пробелы не получают никакой специальной обработки.

Вывод:

• Третья сторона не использует HashTable или оборачивает что-то в строку, чтобы сделать пробелы медленнее.
• Или они пытаются запутать свою реализацию, рассказывая истории.

Answer 2

Это не должно быть медленнее. Он использует GetHashCode () внутри, поэтому набор символов в строке не имеет значения.

При этом производительность зависит только от реализации GetHashCode для String. Вы можете получить разные результаты для разных версий фреймворка (из MSDN):

Поведение GetHashCode: зависит от его реализации, которая может измениться от одной версии общеязыковая среда выполнения для другого. Причина, по которой это может произойти, заключается в улучшить производительность GetHashCode.

Answer 3

Пробел увеличивает длину строки, замедляя хеш-функцию, но я ожидаю, что это будет действительно незначительным. С другой стороны, оставляя пробелы в строке, можно получить лучший хэш с меньшим количеством коллизий. Поэтому я не думаю, что есть какая-либо проблема с использованием строки с пробелами в HashTable.