package bap-std

  1. Overview
  2. Docs
package bap-std
Legend:
Library
Module
Module type
Parameter
Class
Class type
val hash_fold_t : Base.Hash.state -> Elt.t -> Base.Hash.state

hash_fold_t state x mixes the content of x into the state.

By default, all our hash_fold_t functions (derived or not) should satisfy the following properties.

1. hash_fold_t state x should mix all the information present in x in the state. That is, by default, hash_fold_t will traverse the full term x (this is a significant change for Hashtbl.hash which by default stops traversing the term after after considering a small number of "significant values"). hash_fold_t must not discard the state.

2. hash_fold_t must be compatible with the associated compare function: that is, for all x y and s, compare x y = 0 must imply hash_fold_t s x = hash_fold_t s y.

3. To avoid avoid systematic collisions, hash_fold_t should expand to different sequences of built-in mixing functions for different values of x. No such sequence is allowed to be a prefix of another.

A common mistake is to implement hash_fold_t of a collection by just folding all the elements. This makes the folding sequence of a be a prefix of a @ b, thereby violating the requirement. This creates large families of collisions: all of the following collections would hash the same:

[]; [1;2;3] [1]; [2;3] [1; 2]; [3] [1; 2; 3]; [] [1]; [2]; []; [3]; ...

A good way to avoid this is to mix in the size of the collection to the beginning (fold ~init:(hash_fold_int state length) ~f:hash_fold_elem). The default in our libraries is to mix the length of the structure before folding. To prevent the afforementioned collisions, one should respect this ordering.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct