Гарантируют ли принадлежащие и заимствованные строки ha sh одинаковой стоимости? - PullRequest
Новая
       102

Гарантируют ли принадлежащие и заимствованные строки ha sh одинаковой стоимости?

3 голосов
/ 09 мая 2020

String и str реализуют Hash, поэтому мы можем получить sh любое из них. Похоже, что как собственные, так и заимствованные строки в настоящее время имеют sh одно и то же значение, поэтому это утверждение выполняется успешно: 

use std::hash::Hash;
use std::hash::Hasher;
use std::collections::hash_map::DefaultHasher;
pub fn main() {
    let hash1 = {
        let x: String = "abc".to_owned();
        let mut hasher = DefaultHasher::new();
        x.hash(&mut hasher);
        hasher.finish()
    };
    let hash2 = {
        let x: &str = "abc";
        let mut hasher = DefaultHasher::new();
        x.hash(&mut hasher);
        hasher.finish()
    };
    assert!(hash1 == hash2);
}

Я пишу код, который использует это поведение в raw_entry API HashMap. В частности, я использую HashMap, где ключи являются перечислениями, но для уменьшения избыточных выделений я хочу выполнить поиск, используя «заимствованные» версии этих перечислений.

Другими словами, в следующем коде я делаю нужна гарантия того, что оба утверждения будут успешными, независимо от используемой реализации Hasher. Мне кажется, что это будет зависеть от гарантий, предоставляемых Hash реализацией String и str. 

use std::hash::Hash;
use std::hash::Hasher;
use std::collections::hash_map::DefaultHasher;
pub fn main() {
    {
        #[derive(Hash)]
        enum E1 {
            First(i32),
            Second(String),
        }
        #[derive(Hash)]
        enum E2<'a> {
            First(i32),
            Second(&'a str),
        }
        let hash1 = {
            let x: E1 = E1::First(100);
            let mut hasher = DefaultHasher::new();
            x.hash(&mut hasher);
            hasher.finish()
        };
        let hash2 = {
            let x: E2 = E2::First(100);
            let mut hasher = DefaultHasher::new();
            x.hash(&mut hasher);
            hasher.finish()
        };
        assert!(hash1 == hash2);
        let hash3 = {
            let x: E1 = E1::Second("abc".to_owned());
            let mut hasher = DefaultHasher::new();
            x.hash(&mut hasher);
            hasher.finish()
        };
        let hash4 = {
            let x: E2 = E2::Second("abc");
            let mut hasher = DefaultHasher::new();
            x.hash(&mut hasher);
            hasher.finish()
        };
        assert!(hash3 == hash4);
    }
}

Есть ли где-нибудь документально подтверждены такие гарантии? Я бы предположил, что такие гарантии должны быть предоставлены (в противном случае я не вижу возможности правильно реализовать метод contains_key() для HashMap, поскольку аргументом может быть любая заимствованная форма ключа), но я не могу найти эту гарантию задокументированной где угодно.

1 Ответ

10 голосов
/ 09 мая 2020

Да. Это гарантировано, потому что String реализует Borrow<str>.

Часть контракта для реализации Borrow:

Кроме того, при предоставлении реализаций для дополнительных свойств необходимо рассмотреть, должны ли они вести себя идентично свойствам базового типа вследствие того, что они действуют как представление этого базового типа. Код Generi c обычно использует Borrow<T>, когда полагается на идентичное поведение этих дополнительных реализаций признаков. Эти черты, вероятно, появятся как дополнительные границы черт.

В частности, Eq, Ord и Hash должны быть эквивалентны для заимствованных и принадлежащих значений: x.borrow() == y.borrow() должно дать тот же результат, что и x == y .

В стандартной библиотеке трейт Borrow используется в HashMap::get. Borrow позволяет передать &str на get на HashMap<String, _>. Естественно, чтобы это работало, &String и &str должны давать одинаковые ha sh для одной и той же строки, отсюда и требование к Borrow. Требование повторяется в документации для HashMap::get:

Ключ может быть любой заимствованной формой типа ключа карты, но Hash и Eq в заимствованной форме должны соответствуют таковым для типа ключа.

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

...