Используя только стандартные английские буквы и подчеркивание, максимальное количество символов можно использовать, не вызывая потенциальной коллизии в хеш-таблице/словаре.
Итак, строки типа:
blur
Blur
b
Blur_The_Shades_Slightly_With_A_Tint_Of_Blue
...
Нет никакой гарантии, что вы не получите коллизию между отдельными буквами.
Вы вероятно этого не сделаете, но алгоритм, используемый в string.GetHashCode, не указан и может измениться. (В частности, он изменился между .NET 1.1 и .NET 2.0, что обожгло людей, полагавших, что это не изменится.)
Обратите внимание, что коллизии хеш-кода не остановят работу хорошо спроектированных хеш-таблиц — вы все равно сможете получить правильные значения, просто потенциально потребуется проверить более одного ключа, используя равенство, если они имеют один и тот же хеш. код.
В любом словаре, который полагается на уникальность хэш-кодов, отсутствует важная информация о хеш-кодах, IMO :) (если только он не работает в очень специфических условиях, когда он абсолютно знает, что они будут уникальным, то есть использует идеальную хеш-функцию.)
Имея идеальную функцию хеширования (которую вы обычно не будете иметь, как упоминали другие ), вы можете найти максимально возможное количество символов, при котором никакие две строки не вызовут конфликта, следующим образом:
Количество доступных уникальных хэш-кодов = 2 ^ 32 = 4294967296 (при условии, что для хэш-кодов используется 32-битное целое число) Размер набора символов = 2 * 26 + 1 = 53 (26 строчных букв латинского алфавита в верхнем регистре, плюс подчеркивание)
Тогда вы должны учитывать, что строка длиной l (или меньше) имеет в общей сложности 54 ^ l представлений. Обратите внимание, что база равна 54, а не 53, потому что строка может заканчиваться после любого символа, добавляя дополнительную возможность для каждого символа - не то, чтобы это сильно повлияло на результат.
Принимая нет. уникальных хэш-кодов как максимальное количество строковых представлений, вы получите следующее простое уравнение:
54 ^ l = 2 ^ 32
И решить это:
log2 (54 ^ l) = 32
l * log2 54 = 32
l = 32 / log2 54 = 5.56
(Где log2 — логарифмическая функция по основанию 2.)
Поскольку длина строки явно не может быть дробной, вы берете целую часть, чтобы получить максимальную длину всего 5. Действительно, очень короткое, но заметьте, что это ограничение предотвратило бы даже малейшую вероятность коллизии при идеальной хэш-функции.
Однако, как я уже упоминал, это в значительной степени теоретически, и я не уверен, насколько это может быть полезно при рассмотрении дизайна чего-либо. Сказав это, надеюсь, это должно помочь вам понять вопрос с теоретической точки зрения, поверх которой вы можете добавить практические соображения (например, несовершенные хеш-функции, неравномерность распределения).
Чтобы вычислить вероятность коллизий между S строками длины L с W битами на символ и хэшем длиной H бит при оптимальном универсальный хэш (1), вы можете рассчитать вероятность коллизии на основе хэш-таблицы размера (количество сегментов) 'N`.
Прежде всего, мы можем предположить идеальную реализацию хеш-таблицы (2), которая идеально разбивает H битов хэша на доступные сегменты N(3). Это означает, что H становится бессмысленным, за исключением ограничения для N. W и 'L' - это просто основа для верхней границы S. Для более простой математики предположим, что строки длиной ‹ L просто дополняются до L специальным нулевым символом. Если бы нас это интересовало, нас бы интересовал худший случай, это 54^L (26*2+'_'+ null), очевидно, это смехотворное число, фактическое количество записей более полезно, чем набор символов и длина поэтому мы просто будем работать так, как если бы S была переменной сама по себе.
Осталось попытаться поместить S предметов в N ведер. Затем это становится очень известной проблемой, парадоксом дня рождения.
Решая это для различных вероятностей и количества ковшей поучительно, но предполагая, что мы имеем 1 миллиард сегментов (то есть около 4 ГБ памяти в 32-битной системе), тогда нам потребуется всего 37 КБ записей, прежде чем мы достигнем 50% вероятности того, что они будут хотя бы одним столкновением. Учитывая, что попытка избежать любых коллизий в хеш-таблице становится просто абсурдной.
Все это не означает, что мы не должны заботиться о поведении наших хеш-функций. Очевидно, что эти цифры предполагают идеальные реализации, они являются верхней границей того, насколько хорошо мы можем добиться. Плохая хеш-функция может привести к гораздо более серьезным коллизиям в некоторых областях, растратить часть возможного «пространства», никогда или редко используя его, все это может привести к тому, что хэши будут менее оптимальными, и даже ухудшится до производительности, которая выглядит как список, но с гораздо хуже постоянными факторами.
Реализация .NET framework хеш-функции строки не очень хороша (в том смысле, что она могла бы быть лучше), но, вероятно, приемлема для подавляющего большинства пользователей и достаточно эффективна для вычислений.
Если вы хотите генерировать так называемые идеальные хэши, вам потребуется полное знание входных значений. заранее однако так не часто полезно. По аналогии с приведенной выше математикой мы можем показать, что даже идеальное хеширование имеет свои пределы:
Напомним ограничение в 54 ^ L строк длины L. Однако у нас есть только H бит (предположим, 32), что составляет около 4 миллиардов различных чисел. Итак, если у вас может быть действительно любая строка и любое их количество, вы должны удовлетворить:
54 ^ L <= 2 ^ 32
И решить это:
log2 (54 ^ L) <= 32
L * log2 54 <= 32
L <= 32 / log2 54 <= 5.56
Поскольку длина строки явно не может быть дробной, у вас остается максимальная длина всего 5. Действительно очень короткая.
Если вы знаете, что у вас когда-либо будет набор строк размером намного меньше 4 миллиардов, то идеальное хеширование позволит вам обрабатывать любое значение L, но ограничение набора значений на практике может быть очень сложным, и вы должны знать их все на практике. продвигаться или снижаться до того, что составляет базу данных строк -> хэш, и добавлять к ней по мере обнаружения новых строк.
Для этого упражнения универсальный хэш является оптимальным, так как мы хотим уменьшить вероятность любой коллизии, то есть для любого входа вероятность того, что он имеет выход x из набора возможностей R, равна 1/R.
Обратите внимание, что выполнить оптимальную работу по хэшированию (и внутренней группировке) довольно сложно, но вы должны ожидать, что встроенные типы будут разумными, если не всегда идеальными.
В этом примере я избегал вопроса о закрытой и открытой адресации. Это имеет некоторое влияние на вовлеченные вероятности, но незначительно.
Хэш-алгоритм не должен гарантировать уникальность. Учитывая, что потенциальных строк (26^n для длины n, даже без учета специальных символов, пробелов, заглавных букв, неанглийских символов и т. д.) гораздо больше, чем мест в вашей хеш-таблице, такая гарантия не может быть выполнена. . Это только должно гарантировать хорошее распределение.
Если ваш ключ представляет собой строку (например, словарь), то будет использоваться GetHashCode(). Это 32-битное целое число. Hashtable по умолчанию использует ключ 1 для значения коэффициента загрузки и увеличивает количество сегментов для поддержания этого коэффициента загрузки. Поэтому, если вы видите коллизии, они должны иметь тенденцию возникать вокруг границ перераспределения (и уменьшаться вскоре после перераспределения).
