Hash implementation testing

#1

I am trying to test if my Hash implementation is correct or not. What I came up with is to put two things in a HashMap and if they replace each other it means they have the same hash (I think at least).

With an obviously bad implementation of Hash (code below) I would expect my asserts to succeed even if I put different values in stuff. Because the hash should be the same as I am not hashing what is in stuff.

When I run the code below, it does panic. Which means that the hash is different even though I am not hashing stuff?

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

#[derive(Clone, Eq, PartialEq, Debug)]
pub struct Maps {
    pub stuff: HashMap<u32, u32>,
}

impl Hash for Maps {
    fn hash<H: Hasher>(&self, state: &mut H) {}
}

fn main() {
    let value1 = {
        let mut h = HashMap::new();
        h.insert(2, 2);
        h.insert(2, 2);
        Maps { stuff: h }
    };

    let value2 = {
        let mut h = HashMap::new();
        h.insert(1, 1);
        h.insert(1, 1);
        Maps { stuff: h }
    };

    let mut test_hash_map = HashMap::new();
    test_hash_map.insert(value1.clone(), 0);
    test_hash_map.insert(value2.clone(), 1);

    assert_eq!(1, *test_hash_map.get(&value1.clone()).unwrap());
    assert_eq!(1, test_hash_map.keys().count());
}

What is the best way to test if a Hash implementation is correct?
Why does my code seem to hash the values in stuff even though my Hash implementation does no such thing?

#2

All hash algorihms have collisions, so HashMap double-checks with Eq if the two hashes are identical. If you want to compare the calculated hashes, you’ll need to use a Hasher directly.

Your Hash implementation is “correct” in that it always computes hash value for any two objects that compare as Eq— It’s just inefficient to use because of the 100% collision rate.

1 Like
#3

A real world example of why not checking for equality when two hashes match is a serious bug is the SHA-1 Subversion attack from a few years ago (since patched).

You could use state.finish() to examine the computed hash value, if you like.

1 Like
#4

Cool link! Thank you all for the answers :slight_smile: