Struct ahash::fallback_hash::AHasher

pub struct AHasher {
    buffer: u64,
    pad: u64,
    extra_keys: [u64; 2],
}

A Hasher for hashing an arbitrary stream of bytes.

Instances of AHasher represent state that is updated while hashing data.

Each method updates the internal state based on the new data provided. Once all of the data has been provided, the resulting hash can be obtained by calling finish()

Clone is also provided in case you wish to calculate hashes for two different items that start with the same data.

Fields

buffer: u64

pad: u64

extra_keys: [u64; 2]

Implementations

impl AHasher

pub(crate) fn new_with_keys(key1: u128, key2: u128) -> AHasher

Creates a new hasher keyed to the provided key.

pub(crate) fn test_with_keys(key1: u128, key2: u128) -> Self

pub(crate) fn from_random_state(rand_state: &RandomState) -> AHasher

fn update(&mut self, new_data: u64)

This update function has the goal of updating the buffer with a single multiply FxHash does this but is vulnerable to attack. To avoid this input needs to be masked to with an unpredictable value. Other hashes such as murmurhash have taken this approach but were found vulnerable to attack. The attack was based on the idea of reversing the pre-mixing (Which is necessarily reversible otherwise bits would be lost) then placing a difference in the highest bit before the multiply used to mix the data. Because a multiply can never affect the bits to the right of it, a subsequent update that also differed in this bit could result in a predictable collision.

This version avoids this vulnerability while still only using a single multiply. It takes advantage of the fact that when a 64 bit multiply is performed the upper 64 bits are usually computed and thrown away. Instead it creates two 128 bit values where the upper 64 bits are zeros and multiplies them. (The compiler is smart enough to turn this into a 64 bit multiplication in the assembly) Then the upper bits are xored with the lower bits to produce a single 64 bit result.

To understand why this is a good scrambling function it helps to understand multiply-with-carry PRNGs: https://en.wikipedia.org/wiki/Multiply-with-carry_pseudorandom_number_generator If the multiple is chosen well, this creates a long period, decent quality PRNG. Notice that this function is equivalent to this except the buffer/state is being xored with each new block of data. In the event that data is all zeros, it is exactly equivalent to a MWC PRNG.

This is impervious to attack because every bit buffer at the end is dependent on every bit in new_data ^ buffer. For example suppose two inputs differed in only the 5th bit. Then when the multiplication is performed the result will differ in bits 5-69. More specifically it will differ by 2^5 * MULTIPLE. However in the next step bits 65-128 are turned into a separate 64 bit value. So the differing bits will be in the lower 6 bits of this value. The two intermediate values that differ in bits 5-63 and in bits 0-5 respectively get added together. Producing an output that differs in every bit. The addition carries in the multiplication and at the end additionally mean that the even if an attacker somehow knew part of (but not all) the contents of the buffer before hand, they would not be able to predict any of the bits in the buffer at the end.

fn large_update(&mut self, new_data: u128)

Similar to the above this function performs an update using a “folded multiply”. However it takes in 128 bits of data instead of 64. Both halves must be masked.

This makes it impossible for an attacker to place a single bit difference between two blocks so as to cancel each other.

However this is not sufficient. to prevent (a,b) from hashing the same as (b,a) the buffer itself must be updated between calls in a way that does not commute. To achieve this XOR and Rotate are used. Add followed by xor is not the same as xor followed by add, and rotate ensures that the same out bits can’t be changed by the same set of input bits. To cancel this sequence with subsequent input would require knowing the keys.

Trait Implementations

impl Clone for AHasher

fn clone(&self) -> AHasher

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for AHasher

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for AHasher

Provides a default Hasher with fixed keys. This is typically used in conjunction with BuildHasherDefault to create AHashers in order to hash the keys of the map.

Generally it is preferable to use RandomState instead, so that different hashmaps will have different keys. However if fixed keys are desirable this may be used instead.

Example

use std::hash::BuildHasherDefault;
use ahash::{AHasher, RandomState};
use std::collections::HashMap;

let mut map: HashMap<i32, i32, BuildHasherDefault<AHasher>> = HashMap::default();
map.insert(12, 34);

fn default() -> AHasher

Constructs a new AHasher with fixed keys. If std is enabled these will be generated upon first invocation. Otherwise if the compile-time-rngfeature is enabled these will be generated at compile time. If neither of these features are available, hardcoded constants will be used.

Because the values are fixed, different hashers will all hash elements the same way. This could make hash values predictable, if DOS attacks are a concern. If this behaviour is not required, it may be preferable to use RandomState instead.

Examples

use ahash::AHasher;
use std::hash::Hasher;

let mut hasher_1 = AHasher::default();
let mut hasher_2 = AHasher::default();

hasher_1.write_u32(1234);
hasher_2.write_u32(1234);

assert_eq!(hasher_1.finish(), hasher_2.finish());

impl Hasher for AHasher

Provides Hasher methods to hash all of the primitive types.

fn write_u8(&mut self, i: u8)

Writes a single u8 into this hasher.

fn write_u16(&mut self, i: u16)

Writes a single u16 into this hasher.

fn write_u32(&mut self, i: u32)

Writes a single u32 into this hasher.

fn write_u64(&mut self, i: u64)

Writes a single u64 into this hasher.

fn write_u128(&mut self, i: u128)

Writes a single u128 into this hasher.

fn write_usize(&mut self, i: usize)

Writes a single usize into this hasher.

fn write(&mut self, input: &[u8])

Writes some data into this Hasher.

fn finish(&self) -> u64

Returns the hash value for the values written so far.

fn write_i8(&mut self, i: i8)

Writes a single i8 into this hasher.

fn write_i16(&mut self, i: i16)

Writes a single i16 into this hasher.

fn write_i32(&mut self, i: i32)

Writes a single i32 into this hasher.

fn write_i64(&mut self, i: i64)

Writes a single i64 into this hasher.

fn write_i128(&mut self, i: i128)

Writes a single i128 into this hasher.

fn write_isize(&mut self, i: isize)

Writes a single isize into this hasher.

fn write_length_prefix(&mut self, len: usize)

🔬This is a nightly-only experimental API. (hasher_prefixfree_extras)

Writes a length prefix into this hasher, as part of being prefix-free.

fn write_str(&mut self, s: &str)

🔬This is a nightly-only experimental API. (hasher_prefixfree_extras)

Writes a single str into this hasher.