#Hash
Status: standard library specification draft.
This chapter defines the part of std.hash that lib/std writes in
ordinary hd over the language tier:
- what a derived
Hashhashes, through the trait's template; - how tuples hash, through the trait's tuple template;
- how lists and results hash;
- the bytes each standard implementation writes;
- the standard hasher
DefaultHasher, andhash_of; - the stable hasher
Fnv1a.
The language tier keeps Hash and Hasher, which map keys require
(Hashing), and the @derive checks.
#Derived Hashing
@derive(Hash) hashes a value member by member:
@derive(Eq, Hash)
enum Status:
Ready(code: i32)
Failed(code: i32, reason: string)
fn lookup_status(items: Map[Status, i32], status: Status) -> i32?:
items.get(status)- std-hash.derive.hash.template
std.hashdeclares the template ofHash, which@derive(Hash)instantiates. - std-hash.derive.hash.support
@derive(Hash)supports structs and enums. - std-hash.derive.hash.dataIt hashes every declared struct field in declaration order, including embedded fields.
- std-hash.derive.hash.enumFor an enum, it hashes the variant, then shared enum data in declaration order, then that variant's payload fields in declaration order.
- std-hash.derive.hash.fieldsEvery hashed field must implement
Hash; no field is implicitly excluded. - std-hash.derive.hash.cyclesLike derived equality, derived hashing does not detect cycles, so hashing a cyclic graph may exhaust the execution stack.
- std-hash.derive.hash.referencesA reference field hashes as the value it refers to, by Reference Hashing.
#Tuple Hashing
fn index(counts: Map[(i32, string), i32]) -> i32:
counts[(1, "a")]- std-hash.tuple.template
std.hashdeclares a tuple template forHash. A tuple implementsHashwhen every element does, at every size. - std-hash.tuple.rest-listA tuple's rest element hashes as its
List[T]. So a rest tuple implementsHashwhen its fixed elements do andT < Hash, and it may be a map key.
#List Hashing
fn count(counts: Map[List[i32], i32], key: List[i32]) -> i32:
match counts.get(key):
.Some(n) => n
.None => 0- std-hash.list.impl
std.hashimplementsHashforList[T]whenT < Hash. - std-hash.list.not-elementA list whose item type does not implement
Hash, such asList[f64], does not implementHash. Using it whereHashis required is an error. Error:unsatisfied-trait-bound.
fn lookup(counts: Map[List[f64], i32]) -> i32: # error: unsatisfied-trait-bound
0#Result Hashing
fn failures(counts: Map[Result[i32, string], i32], key: Result[i32, string]) -> i32:
match counts.get(key):
.Some(n) => n
.None => 0- std-hash.result.impl
std.hashimplementsHashforResult[T, E]whenT < HashandE < Hash, so aResultof hashable types may be a map key.
#Bytes Written
Each standard Hash implementation writes a fixed sequence of bytes to
its Hasher:
use std.hash.Fnv1a
fn digest() -> u64:
let key: (u8, string) = (7, "a")
let mut hasher = Fnv1a::new()
key.hash(&mut hasher)
hasher.finish() # 12920292002639229810, from the bytes 7, 1, 0, 0, 0, 0, 0, 0, 0, 97| Rule | Value | Bytes written, in order |
|---|---|---|
| std-hash.bytes.integerInteger | an i8 to i64, a u8 to u64, or a usize |
its two's-complement bytes at its own width, least significant first |
std-hash.bytes.boolbool |
false or true |
one byte, 0 or 1 |
std-hash.bytes.charchar |
a Unicode scalar value | the scalar value, written as a u32 writes it |
std-hash.bytes.stringstring |
a UTF-8 text | the number of its UTF-8 bytes as a u64, then those bytes |
std-hash.bytes.listList[T] |
a list | its length as a u64, then each item's bytes in order |
| std-hash.bytes.tupleTuple | a tuple | each element's bytes in order, with no length; a rest element writes as its List |
std-hash.bytes.optionalT? |
.None or .Some(value) |
the tag byte 0 for .None; the tag byte 1, then the bytes of value, for .Some |
| std-hash.bytes.referenceReference | &T or &mut T |
the bytes of the value it refers to |
std-hash.bytes.resultResult[T, E] |
.Ok(value) or .Err(error) |
the tag byte 0, then the bytes of value, for .Ok; the tag byte 1, then the bytes of error, for .Err |
- std-hash.bytes.exactEach standard implementation of
Hashwrites exactly the bytes of the table above. So a value'sFnv1adigest is the same in every implementation. - std-hash.bytes.typed-methodsA standard
Hashimplementation may write integer bytes or a string's bytes through the corresponding typedHashermethod, since it writes the same byte sequence aswrite. - std-hash.bytes.derive-enumA derived
Hashon an enum writes the variant's zero-based index as au32, before the members thatstd-hash.derive.hash.enumlists. - std-hash.bytes.derive-dataA derived
Hashon a struct writes no tag, only the bytes of its members in the order ofstd-hash.derive.hash.data.
Why. A string writes its length first, as a list does, so one rule covers every sequence, and
("ab", "c")writes other bytes than("a", "bc"). Rust instead ends a string with the byte0xff, which UTF-8 never contains. That is shorter, but it is a second scheme. A tuple writes no length because its type fixes its arity.
Note. These rules fix the bytes in order, not how an implementation splits them into
writecalls. ADefaultHashergives the same result for any split, bystd-hash.default.write, and so does anFnv1a, bystd-hash.fnv1a.write.
#Default Hasher
DefaultHasher is the standard Hasher. For one hd toolchain, its digest
of the same bytes never changes; its algorithm is not specified:
use std.hash.{DefaultHasher, Hasher, hash_of}
fn same_digest() -> bool:
let mut hasher = DefaultHasher::new()
"hd".hash(&mut hasher)
hasher.finish() == hash_of("hd") # true, in every run of every program
fn bucket(key: string) -> u64:
hash_of(key)- std-hash.default.declarations
std.hashdeclaresDefaultHasherwith private fields and the functionhash_of, imported withuse std.hash.{DefaultHasher, hash_of}. - std-hash.default.per-toolchainFor one hd toolchain,
DefaultHashergives the same digest of the same bytes in every run, replay, program, and platform. - std-hash.default.unspecifiedThe algorithm of
DefaultHasheris not specified, and it may change between toolchain versions. A program must not persist its digests or compare them with another toolchain's. - std-hash.default.new-empty
DefaultHasher::new() -> DefaultHasherreturns a hasher value with no bytes written to it. - std-hash.default.write
DefaultHasherimplementsHasher. Itswrite(bytes)processes each byte in order, so two writes give the state of one write of both byte lists joined. - std-hash.default.finish-digest
finish(self) -> u64returns the digest of the bytes written so far and does not change the hasher. - std-hash.default.typed-writes
DefaultHasheroverrides every typedHashermethod to process the specified bytes without building a list. - std-hash.hash-of-local
hash_of[T < Hash](value: T) -> u64hashes through a mutable borrow of a localDefaultHasher, then returns itsfinish(). - std-hash.map.foldhash-fast
MapandUniqMapbucket keys by the low 32 bits of foldhash 0.2'sfasthash. - std-hash.map.seed-wordEach map stores one 64-bit seed.
- std-hash.map.seed-newA new map takes its seed by mixing the run seed with the next value of a per-run counter.
- std-hash.map.seed-emptyWhenever a nonempty map becomes empty, it takes a fresh seed.
- std-hash.map.seed-copyA copy-on-write copy of a
Mappreserves its source's seed. - std-hash.map.seed-replayReplaying a run's recorded seed and map operations reproduces its map seeds.
- std-hash.map.order-independent
MapandUniqMapiteration order does not depend on bucket hashes or seeds.
Why. A general hash that must stay the same forever locks the language into its algorithm, as
String.hashCodelocked Java. Go, Python and Swift instead choose a random seed per process, which breaks replay. Like Rust'sDefaultHasher, hd fixes the seed but promises nothing across versions. So a digest depends on no run state, replay stays deterministic, and a later toolchain may adopt a faster algorithm.DefaultHasheruses foldhash'sfastalgorithm, the one maps use, with one constant seed.
Note. A digest is reproducible within one toolchain, so a test may compare two digests. A test that asserts a literal digest, or a program that stores one, uses
Fnv1a. With a fixed seed, keys chosen to collide stay colliding. SoMapandUniqMapdo not bucket keys byDefaultHasher, but give each map its own seed.
Why. A fixed bucket hash lets one chosen collision pattern apply to every map. Foldhash's
fastalgorithm hashes integer and string keys efficiently, while a separate seed gives each map its own bucket hash. Refreshing the seed when a map becomes empty follows Go's map seed rotation. The journal records the run seed, so rebuilding reproduces map seeds. Bucket changes preserve deterministic iteration.
Note. The
Hashercontract requires equivalent typed and raw writes. Generic key bytes use fast's sponge as repeated single-byte writes. The implementation batches words with constant state and oneHashcall.
See also: Derived Tuple Implementations, Lookup And Order, Cmp.
#FNV-1a Hasher
Fnv1a is a Hasher whose digests never change, for a program that
persists them:
use std.hash.{Fnv1a, Hasher}
fn digest() -> u64:
let mut hasher = Fnv1a::new()
hasher.write([97])
hasher.finish() # 12638187200555641996| Step | Effect on the 64-bit state |
|---|---|
| start | the FNV offset basis, 0xcbf29ce484222325 |
each byte b, in order |
XOR b into the state, then multiply by the FNV prime 0x100000001b3, modulo 2^64 |
finish |
returns the state |
- std-hash.fnv1a.declarations
std.hashdeclaresFnv1awith private fields, imported withuse std.hash.Fnv1a. - std-hash.fnv1a.algorithm
Fnv1acomputes 64-bit FNV-1a over the bytes written to it, by the table above. - std-hash.fnv1a.new-value
Fnv1a::new() -> Fnv1areturns a hasher value whose state is the offset basis. - std-hash.fnv1a.write
Fnv1aimplementsHasher. Itswrite(bytes)processes each byte in order, so two writes give the state of one write of both byte lists joined. - std-hash.fnv1a.finish
finish(self) -> u64returns the state and does not change it. - std-hash.fnv1a.typed-writes
Fnv1aoverrides every typedHashermethod to process the specified bytes without building a list. - std-hash.fnv1a.fixedThe algorithm has no seed and no key. So the same bytes give the same digest in every run, program, implementation, and toolchain version, and a program may persist it.
- std-hash.fnv1a.vectors
Fnv1agives these digests:
| Bytes written | Digest |
|---|---|
| none | 14695981039346656037 (0xcbf29ce484222325) |
97 |
12638187200555641996 (0xaf63dc4c8601ec8c) |
97, 98 |
620445648566982762 (0x089c4407b545986a) |
the UTF-8 bytes of foobar |
9625390261332436968 (0x85944171f73967e8) |
7, 1, seven 0s, 97: the Hash bytes of (7, "a") as (u8, string) |
12920292002639229810 |
Why. FNV-1a is a few lines of hd that need only XOR and one wrapping multiplication. Its published digests let any program check its own. SipHash-1-3 mixes better, but its strength is a secret key. With a fixed key it gives no defense against chosen keys, so its larger code buys little here.
#Reference Hashing
std.hash implements Hash for references by the values they refer to:
use std.hash.hash_of
fn same_hash(a: &string, b: &string) -> bool:
hash_of(a) == hash_of(b) # true when *a == *b- std-hash.reference.noncopy
std.hashimplementsHashfor each reference type,*T,*mut T,&T, and&mut T, whenT < ?Copy & Hash. A reference writes the bytes of the value it refers to, so a reference and its value hash alike. - std-hash.reference.derivedA derived
Hashreaches this implementation for a reference field, asstd-hash.derive.hash.referencesstates.