Struct ahash::AHasher

source ·
pub struct AHasher {
    buffer: u64,
    pad: u64,
    extra_keys: [u64; 2],
}
Expand description

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§

source§

impl AHasher

source

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

Creates a new hasher keyed to the provided key.

source

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

source

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

source

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.

source

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§

source§

impl Clone for AHasher

source§

fn clone(&self) -> AHasher

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl Debug for AHasher

source§

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

Formats the value using the given formatter. Read more
source§

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);
source§

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());
source§

impl Hasher for AHasher

Provides Hasher methods to hash all of the primitive types.

source§

fn write_u8(&mut self, i: u8)

Writes a single u8 into this hasher.
source§

fn write_u16(&mut self, i: u16)

Writes a single u16 into this hasher.
source§

fn write_u32(&mut self, i: u32)

Writes a single u32 into this hasher.
source§

fn write_u64(&mut self, i: u64)

Writes a single u64 into this hasher.
source§

fn write_u128(&mut self, i: u128)

Writes a single u128 into this hasher.
source§

fn write_usize(&mut self, i: usize)

Writes a single usize into this hasher.
source§

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

Writes some data into this Hasher. Read more
source§

fn finish(&self) -> u64

Returns the hash value for the values written so far. Read more
1.3.0 · source§

fn write_i8(&mut self, i: i8)

Writes a single i8 into this hasher.
1.3.0 · source§

fn write_i16(&mut self, i: i16)

Writes a single i16 into this hasher.
1.3.0 · source§

fn write_i32(&mut self, i: i32)

Writes a single i32 into this hasher.
1.3.0 · source§

fn write_i64(&mut self, i: i64)

Writes a single i64 into this hasher.
1.26.0 · source§

fn write_i128(&mut self, i: i128)

Writes a single i128 into this hasher.
1.3.0 · source§

fn write_isize(&mut self, i: isize)

Writes a single isize into this hasher.
source§

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. Read more
source§

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

🔬This is a nightly-only experimental API. (hasher_prefixfree_extras)
Writes a single str into this hasher. Read more

Auto Trait Implementations§

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.