Критерий эффективности сравнения по хешам

[mclaudt]

В Java объекты имеют метод boolean equals(Object obj), который классы переопределяют для реализации семантики понятия "равенства".
Контракт этого метода полностью отвечает тому, что называется отношением эквивалентности (рефлексивность, симметричность, транзитивность), т.е. отношение obj1.equals(obk2)==true определяет классы эквивалентности среди объектов.

Также имеется метод int hashCode(), его контракт подразумевает, что классы эквивалентности, образуемые отношением obj1.hashCode()==obj2.hashCode(), в лучшем случае укрупняют классы эквивалентности equals, не разрезая их. Т.е. это дает нам способ быстро выявить неравенство объектов, не обращаясь к equals: если хеши разные, то и объекты разные. Это свойство лежит в основе хеш-таблиц. Если же хеши объектов равны, то объекты могут быть равные, а могут быть разные (коллизия хешей).

Введем множество теоретически возможных объектов (т.е. все комбинации битов в шаблоне объекта с точностью до equals). Его мощность $D$.
Введем его подмножество "домен": множество реально попадущихся в программе объектов с точностью до equals. Его мощность $d$.
Такое разделение имеет смысл: например, нам никогда не попадется объект-сотрудник с именем "asfadsfadfsad". Но биты под него имеются.

Стоит задача быстро проверять пары объектов на равенство. Возникают вопросы:

1. Каков формальный критерий эффективности использования хешей перед обращением к equals, в терминах энтропии аргументов как случайной величины?
2. Как учесть алгоритмическую сложность конкретных операций? Ведь шенноновская энтропия не оперирует объектом, а только распределением вероятности абстрактного источника объектов.

Прикладной ответ на первый более-менее ясен:

Понятно, что на эффективность использования хешей влияет $\alpha=\frac{d}{N}$: отношение мощности домена $d$ к количеству возможных хешей $N$. Из-за неидеальности хеш-функции оно должно быть меньше единицы, и если к ней приближается, то имеем парадокс дней рождения: коллизии сводят на нет выигрыш в скорости за счет быстрого отсева разных хешей. В то же время теоретически уменьшать $\alpha$ за счет увеличения количества возможных хешей $N$ тоже неэффективно. Как только $N$ сравнится с количеством всех возможных объектов $D$, то хеш-функция станет лишней прослойкой. Итого, оптимальное значение $N$ лежит где-то между $d$ и $D$, причем недалеко от $d$: тем ближе, чем лучше хеш-функция.

Обобщая, вместо $d$ надо оперировать энтропией распределения пар, чтобы учесть неравномерность даже внутри домена.

В итоге выражение для количества хешей: $N =k\cdot 2^{H(p(obj1,obj2))}$, где $p(obj1,obj2)$ — плотность практической вероятности пар объектов, а $H(p)$ — шенноновская энтропия случайной величины с плотностью вероятности $p$, а $k$ — эмпирический коэффициент, стремящийся к единице справа для идеальной хеш-функции.

Тут и возникает второй вопрос. Проблема в том, что данный критерий ничего не говорит об алгоритмической сложности. Например, в классе String в equals строки сперва сравниваются по длине — фактически сравнивается хеш. Но это эвристическая придумка, а каков рецепт нахождения таких ускоряющих этапов для более сложных объектов?

[mclaudt]

Возможно, правильнее $N =k\cdot 2^{H(p(obj1,obj2))/2}$.
Но сути второго вопроса не меняет: нужно как-то перейти от decision problem, которой является операция сравнения объектов, к кодированию сигнала случайного источника с учетом сложности конкретных алгоритмов.