Standard Library

#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 Hash hashes, 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, and hash_of.

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)

1. std-hash.derive.hash.templatestd.hash declares the template of Hash, which @derive(Hash) instantiates.
2. std-hash.derive.hash.support@derive(Hash) supports structs and enums.
3. std-hash.derive.hash.dataIt hashes every declared struct field in declaration order, including embedded fields.
4. 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.
5. std-hash.derive.hash.fieldsEvery hashed field must implement Hash; no field is implicitly excluded.
6. std-hash.derive.hash.cyclesLike derived equality, derived hashing does not detect cycles, so hashing a cyclic graph may exhaust the execution stack.
7. 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")]

1. std-hash.tuple.templatestd.hash declares a tuple template for Hash. A tuple implements Hash when every element does, at every size.
2. std-hash.tuple.rest-listA tuple's rest element hashes as its List[T]. So a rest tuple implements Hash when its fixed elements do and T < 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

1. std-hash.list.implstd.hash implements Hash for List[T] when T < Hash.
2. std-hash.list.not-elementA list whose item type does not implement Hash, such as List[f64], does not implement Hash. Using it where Hash is 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

1. std-hash.result.implstd.hash implements Hash for Result[T, E] when T < Hash and E < Hash, so a Result of 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.hash_of

fn digest() -> u64:
    let key: (u8, string) = (7, "a")
    hash_of(key)  # 12920292002639229810, from the bytes 7, 1, 0, 0, 0, 0, 0, 0, 0, 97

1. std-hash.bytes.sequenceEach standard implementation of Hash writes exactly the bytes of the table above, so hash_of of a value is the same in every implementation.
2. std-hash.bytes.typed-methodsA standard Hash implementation may write integer bytes or a string's bytes through the corresponding typed Hasher method, since it writes the same byte sequence as write.
3. std-hash.bytes.derive-enumA derived Hash on an enum writes the variant's zero-based index as a u32, before the members that std-hash.derive.hash.enum lists.
4. std-hash.bytes.derive-dataA derived Hash on a struct writes no tag, only the bytes of its members in the order of std-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 byte 0xff, 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 write calls. A DefaultHasher gives the same result for any split, by std-hash.default.write.

#Default Hasher

DefaultHasher is the standard Hasher, with one fixed algorithm:

use std.hash.{DefaultHasher, hash_of}

fn digest() -> u64:
    hasher := DefaultHasher::new()
    hasher.write([97])
    hasher.finish()  # 12638187200555641996

fn bucket(key: string) -> u64:
    hash_of(key)

1. std-hash.default.decl-structstd.hash declares the struct DefaultHasher with private fields, used behind *mut, and the function hash_of. Code imports them, as in use std.hash.{DefaultHasher, hash_of}.
2. std-hash.default.algorithmDefaultHasher computes 64-bit FNV-1a over the bytes written to it, by the table above.
3. std-hash.default.new-refDefaultHasher::new() -> *mut DefaultHasher returns a new object, a hasher whose state is the offset basis. Copies of the reference share it, so value.hash(hasher) changes the state that hasher.finish() then returns.
4. std-hash.default.writeDefaultHasher implements Hasher. Its write(bytes) processes each byte in order, so two writes give the state of one write of both byte lists joined.
5. std-hash.default.finishfinish(self) -> u64 returns the state and does not change it.
6. std-hash.default.typed-writesDefaultHasher overrides every typed Hasher method to process the specified bytes without building a list.
7. std-hash.default.fixedThe algorithm has no seed and no key, so the same bytes give the same result in every run, every program, and every implementation.
8. std-hash.hash-ofhash_of[T < Hash](value: T) -> u64 calls value.hash on a new DefaultHasher and returns its finish().
9. std-hash.map.bucket-hashThe hash by which the built-in Map buckets its keys is an implementation detail. It need not be hash_of, and it may differ between runs.

Why. FNV-1a is a few lines of hd that need only XOR and one wrapping multiplication. 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.

Note. A fixed algorithm makes hash values reproducible, so a test may assert one. It also means that keys chosen to collide stay colliding, so the built-in Map does not bucket keys by it.

Why. Keys chosen to collide make every insertion probe the whole table, and a map built from untrusted JSON takes its keys from the sender. So the reference implementation buckets every key by a hash under a random key that the host draws once per run, as Rust keys SipHash-1-3 per process and Go seeds its hash per map. A string, or the Hash bytes of a tuple or other key, goes through HalfSipHash-1-3; an integer through the keyed multiply mix Go uses on 32-bit platforms. A REPL session's journal records the key, so a rebuild replays exactly. Iteration order does not depend on the hash (types.map.order.deterministic), so the key changes no output.

See also: Derived Tuple Implementations, Lookup And Order, Cmp.

#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

1. std-hash.reference.implstd.hash implements Hash for &T and for &mut T when T < Hash. A reference writes the bytes of the value it refers to, so a reference and its value hash alike.
2. std-hash.reference.derivedA derived Hash reaches this implementation for a reference field, as std-hash.derive.hash.references states.