Как передать готовый хеш в хеш-таблицу?

Question

[Eugene Usachev]

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

Comments

[Василий Банников]

А ты уверен, что считаешь именно тот хэш, который в HashMap используется?
Как вариант - ты можешь сделать свой тип для ключа, который будет кэшировать хэш в себе.

[Eugene Usachev]

Василий Банников, хеш-функцию в HashMap можно изменить (третий тип в дженерике и метод with_hasher()). Проблема не в хеше, а в том, что я не могу использовать свой хеш и ключ одновременно.

[mayton2019]

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

[Василий Банников]

Eugene-Usachev, а в чём смысл использовать такой хэш, который на столько дорого вычислять?

[Василий Банников]

mayton2019, у Eugene-Usachev немного другой вопрос. Как я понял:
1. У него есть ключ
2. В рамках обработки - он сам уже посчитал хэш этого ключа каким-то своим алгоритмом
3. Этот же алгоритм он передал в HashMap
4. Но в момент вставки HashMap повторно вычисляет этот хэш.

И вот Eugene-Usachev хочет от этого двойного вычисления избавиться и передавать в шаг 4 то что он посчитал в шаге 2

[Eugene Usachev]

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

[mayton2019]

Eugene-Usachev, что у тебя ключ? Допустим строка. Сделай себе композитный объект

trait HashedString {
    fn body(&self) -> String;
    fn hash(&self) -> i32;
}

И будет тако себе будерброд и хеша и тела ключа. Но это на самом деле tradeoff. Перенос проблемы
из области вычислений в мемоизацию. Это надо прикинуть хорошенько не ударит ли по памяти например.

[Eugene Usachev]

Василий Банников, экономлю на спичках (есть серьёзная причина для этого). Да и не совсем спички тут. Я попробовал передавать уже готовый хеш (u64), чтобы избежать вычисления (хеш от u64, само число) и получил прирост производительности примерно на 15%, однако теперь я не могу найти в коллизиях то, что мне нужно (на 3 000 000 элементов не было ни одного такого случая, но я боюсь, что коллизии неизбежны).

[Eugene Usachev]

mayton2019, интересная идея (не перестаю удивляться, как много в Rust можно изменить с помощью trait), но если бы я мог позволить в рамках задачи так расточительно использовать ресурсы, то я бы не задавал этот вопрос.

[mayton2019]

Eugene-Usachev, выше ты пишешь что коллизии неизбежны. Да. Они неизбежны по свойству множеств.
Множество значений ключа обычно (как правило) мощнее чем множество значений хеша. Принцип Дирихле! Это вообще
база хеш-таблиц. Если-бы этой базы не было - то мы ушли-бы от функции расстановки к прямому доступу
к таблице как к массиву. С другой стороны если у тебя ключ - i32 - (4 млрд значений) то выдели себе
массив на 4 млрд 4х байтных чисел (указателей?) (это будет 16 Г) и пользуся! Прямой доступ. Ключ == индекс.
Красота.

[Василий Банников]

Eugene-Usachev, а что это за задача такая, что приходится на таких спичках экономить? Может тебе вообще не HashMap нужен?

[Василий Банников]

Eugene-Usachev, ещё одна мысль возникла.
А компилятор такое не догадывается оптимизировать? Вроде если там инлайнинг произойдёт, то может увидеть два одинаковых выражения без сайд эффектов.

Answer 1

[Василий Банников]

Используя стандартный HashMap максимум что ты можешь - сделать структуру, которая хранит в себе сам ключ и хэш от него, и реализовать для неё trait Hash - так ты обменяешь процессорные такты на память.

Так что остаётся либо реализовать свою HashMap, либо попробовать реализовать алгоритм иначе.

Comments

[Roman K]

Я лишний раз напомню, что хэшам свойственны коллизии

[Василий Банников]

Roman K, а к чему тут это напоминание?

[Roman K]

Василий Банников, к тому что предрасчитывать хэш, надеясь таким образом оптимизировать получение объекта, довольно бессмысленно, потому что помимо того, что по хэшу нужно пройти к паре ключ-значение, нужно потом ещё и на == сравнить искомый ключ (или несколько ключей, если есть коллизии хэша) с тем, что нашли.

[Василий Банников]

Roman K, так тут же вопрос про запись, а не про чтение - это раз.
Два - автор хочет убрать дублирование операций:
Он перед тем как вставить в таблицу уже посчитал хэш, тк он был нужен ему ещё для чего-то => логично что он не хочет его ещё раз считать