silk/hash

Deterministic seeded hashing contracts for hash maps, hash sets, and user-defined key types.

When to use

Implement HashKey when a type will be stored as a hashed key. Use mix for the first integer field and combine for further fields, feeding every field that participates in equality. Word is the ready-made key for one u64.

Details

A HashSeed belongs to a collection, not to each key. The same seed, keys, and operations produce the same bucket presentation order on every engine, independent of addresses or ambient state. Interface witnesses are selected during specialization and add no runtime dispatch.

Gotchas

Whenever HashKey.equals reports two values equal, HashKey.hash must return the same value for both under every seed. The collection cannot detect a witness that violates this rule; such a key may become unreachable.

Examples

Hash the fields of one key deterministically

import silk.hash as Hash

import silk.u64 as u64

pub fn main() -> i32 {
  let seed = Hash.seed(17)
  let first = Hash.mix(&seed, 4)
    |> Hash.combine(9)
  let second = Hash.mix(&seed, 4)
    |> Hash.combine(9)
  if first != second {
    return 0
  }
  return u64.toI32(Hash.word(42).value)
}

Import as HashKey with import silk.hash.

Public declarations: 7.

HashSeed

pub struct HashSeed

A collection-wide value that changes deterministic hash and bucket results.

Details

The same seed, keys, and operation sequence produce the same bucket order on all Silk engines. A seed does not use allocation addresses, clocks, or ambient entropy.

Field value

pub value: u64

The seed value handed to every hash the collection computes.

Implementation Copy for HashSeed

impl Copy for HashSeed

seed

pub fn seed(value: u64) -> HashSeed

Creates a deterministic hash seed from one u64 value.

HashKey

pub interface HashKey

A compile-time equivalence and seeded-hash contract for hashed collection keys.

Details

The == operator selects equals. A hashed collection calls hash with its own seed.

Gotchas

For each seed, two equivalent keys must have equal hashes. A collection cannot check this rule. If a witness breaks the rule, a present key can become unreachable.

Operation equals

operator == fn equals(left: &Self, right: &Self) -> bool

Reports whether two keys name the same collection entry.

Gotchas

If this returns true, HashKey.hash must return equal hashes for both keys under each seed.

Operation hash

fn hash(value: &Self, seed: &silk/hash.HashSeed) -> u64

Computes the key's deterministic 64-bit hash under the collection seed.

Gotchas

Equivalent keys must return equal results for the same seed.

mix

pub fn mix(seed: &silk/hash.HashSeed, value: u64) -> u64

Mixes the first integer field of a key with one seed into a 64-bit hash.

When to use

Use this function to start a hash for an integer key or the first integer field of a key.

Details

The same seed and value return the same result on all Silk engines. Use combine for each additional field that participates in equality.

combine

pub fn combine(hashed: u64, value: u64) -> u64

Continues a hash with one further value, so a key of several fields folds into one hash.

When to use

Use this function after mix for each additional integer field that participates in equality.

Word

pub struct Word

A ready-made HashKey that holds one u64 value.

Field value

pub value: u64

The integer this key stands for.

Implementation Copy for Word

impl Copy for Word

word

pub fn word(value: u64) -> Word

Creates a Word key from one u64 value.

Implementation HashKey for Word

impl HashKey for Word

Operation equals

equals = Word.wordEquals

Operation hash

hash = Word.wordHash