Могу ли я использовать хэши в HashMap напрямую?

Question

Можно ли вставлять и получать значения в / из HashMap напрямую с помощью Hash, чтобы я мог кэшировать хэши?

Я хочу сделать что-то вроде этого:

map.insert(key, "value");

let hashed_key = {
    let mut hasher = map.hasher().build_hasher();
    key.hash(&mut hasher);
    hasher.finish()
};

assert_eq!(map.get(key).unwrap(), map.get_by_hash(hashed_key).unwrap());

детская площадка

Answer 1

номер

Это принципиально невозможно на алгоритмическом уровне.

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

При best метод get_by_hash вернет Iterator всех возможных элементов, соответствующих текущему хешу.

В случае вырожденного случая рассмотрим алгоритм хеширования, который всегда возвращает 4 (полученный путем броска справедливой кости). Какой элемент вы ожидаете, что он вернется?

---

Работа вокруг

Если кеширование - это то, что вам нужно, хитрость в языках без HashBuilder заключается в предварительном хешировании (и кешировании) хеша внутри самого ключа.

Требуется кэширование полного ключа (из-за проверки на равенство), но тогда хеширование является очень простой операцией (возвращает кэшированное значение).

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

Вы можете адаптировать шаблон к Rust, хотя вы потеряете преимущество использования HashBuilder.