solana_address/
hasher.rs

1use {
2    crate::ADDRESS_BYTES,
3    core::{
4        cell::Cell,
5        hash::{BuildHasher, Hasher},
6        mem,
7    },
8    rand::{thread_rng, Rng},
9};
10
11/// A faster, but less collision resistant hasher for addresses.
12///
13/// Specialized hasher that uses a random 8 bytes subslice of the
14/// address as the hash value. Should not be used when collisions
15/// might be used to mount DOS attacks.
16///
17/// Using this results in about 4x faster lookups in a typical hashmap.
18#[derive(Default)]
19pub struct AddressHasher {
20    offset: usize,
21    state: u64,
22}
23
24impl Hasher for AddressHasher {
25    #[inline]
26    fn finish(&self) -> u64 {
27        self.state
28    }
29    #[inline]
30    fn write(&mut self, bytes: &[u8]) {
31        debug_assert_eq!(
32            bytes.len(),
33            ADDRESS_BYTES,
34            "This hasher is intended to be used with addresses and nothing else"
35        );
36        // This slice/unwrap can never panic since offset is < ADDRESS_BYTES - mem::size_of::<u64>()
37        let chunk: &[u8; mem::size_of::<u64>()] = bytes
38            [self.offset..self.offset + mem::size_of::<u64>()]
39            .try_into()
40            .unwrap();
41        self.state = u64::from_ne_bytes(*chunk);
42    }
43}
44
45/// A builder for faster, but less collision resistant hasher for addresses.
46///
47/// Initializes `AddressHasher` instances that use an 8-byte
48/// slice of the address as the hash value. Should not be used when
49/// collisions might be used to mount DOS attacks.
50///
51/// Using this results in about 4x faster lookups in a typical hashmap.
52#[derive(Clone)]
53pub struct AddressHasherBuilder {
54    offset: usize,
55}
56
57impl Default for AddressHasherBuilder {
58    /// Default construct the AddressHasherBuilder.
59    ///
60    /// The position of the slice is determined initially
61    /// through random draw and then by incrementing a thread-local
62    /// This way each hashmap can be expected to use a slightly different
63    /// slice. This is essentially the same mechanism as what is used by
64    /// `RandomState`
65    fn default() -> Self {
66        std::thread_local!(static OFFSET: Cell<usize>  = {
67            let mut rng = thread_rng();
68            Cell::new(rng.gen_range(0..ADDRESS_BYTES - mem::size_of::<u64>()))
69        });
70
71        let offset = OFFSET.with(|offset| {
72            let mut next_offset = offset.get() + 1;
73            if next_offset > ADDRESS_BYTES - mem::size_of::<u64>() {
74                next_offset = 0;
75            }
76            offset.set(next_offset);
77            next_offset
78        });
79        AddressHasherBuilder { offset }
80    }
81}
82
83impl BuildHasher for AddressHasherBuilder {
84    type Hasher = AddressHasher;
85    #[inline]
86    fn build_hasher(&self) -> Self::Hasher {
87        AddressHasher {
88            offset: self.offset,
89            state: 0,
90        }
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use {
97        super::AddressHasherBuilder,
98        crate::Address,
99        core::hash::{BuildHasher, Hasher},
100    };
101    #[test]
102    fn test_address_hasher_builder() {
103        let key = Address::new_unique();
104        let builder = AddressHasherBuilder::default();
105        let mut hasher1 = builder.build_hasher();
106        let mut hasher2 = builder.build_hasher();
107        hasher1.write(key.as_array());
108        hasher2.write(key.as_array());
109        assert_eq!(
110            hasher1.finish(),
111            hasher2.finish(),
112            "Hashers made with same builder should be identical"
113        );
114        // Make sure that when we make new builders we get different slices
115        // chosen for hashing
116        let builder2 = AddressHasherBuilder::default();
117        for _ in 0..64 {
118            let mut hasher3 = builder2.build_hasher();
119            hasher3.write(key.as_array());
120            std::dbg!(hasher1.finish());
121            std::dbg!(hasher3.finish());
122            if hasher1.finish() != hasher3.finish() {
123                return;
124            }
125        }
126        panic!("Hashers built with different builder should be different due to random offset");
127    }
128
129    #[test]
130    fn test_address_hasher() {
131        let key1 = Address::new_unique();
132        let key2 = Address::new_unique();
133        let builder = AddressHasherBuilder::default();
134        let mut hasher1 = builder.build_hasher();
135        let mut hasher2 = builder.build_hasher();
136        hasher1.write(key1.as_array());
137        hasher2.write(key2.as_array());
138        assert_ne!(hasher1.finish(), hasher2.finish());
139    }
140}
solana_address/hasher.rs

solana_address/
hasher.rs
