Base.Hash · base v0.14.3 · OCaml Packages

base

Full standard library replacement for OCaml

Version

IN THIS PACKAGE

library base
- module Base
  - module Applicative
    
    module type Applicative_infix
    
    module type Applicative_infix2
    
    module type Applicative_infix3
    
    module type Basic
    
    module type Basic2
    
    module type Basic2_using_map2
    
    module type Basic3
    
    module type Basic3_using_map2
    
    module type Basic_using_map2
    
    module Compose
    
    argument 1-F
    
    module Applicative_infix
    
    argument 2-G
    
    module Applicative_infix
    
    module Applicative_infix
    
    module type Let_syntax
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs_intf
    
    module type Let_syntax2
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs_intf
    
    module type Let_syntax3
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs_intf
    
    module Make
    
    argument 1-X
    
    module Applicative_infix
    
    module Make2
    
    argument 1-X
    
    module Applicative_infix
    
    module Make2_using_map2
    
    argument 1-X
    
    module Applicative_infix
    
    module Make3
    
    argument 1-X
    
    module Applicative_infix
    
    module Make3_using_map2
    
    argument 1-X
    
    module Applicative_infix
    
    module Make_let_syntax
    
    argument 1-X
    
    argument 2-Intf
    
    module Let_syntax
    
    module Let_syntax
    
    module Make_let_syntax2
    
    argument 1-X
    
    argument 2-Intf
    
    module Let_syntax
    
    module Let_syntax
    
    module Make_let_syntax3
    
    argument 1-X
    
    argument 2-Intf
    
    module Let_syntax
    
    module Let_syntax
    
    module Make_using_map2
    
    argument 1-X
    
    module Applicative_infix
    
    module Of_monad
    
    argument 1-M
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Applicative_infix
    
    module Of_monad2
    
    argument 1-M
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Applicative_infix
    
    module Pair
    
    argument 1-F
    
    module Applicative_infix
    
    argument 2-G
    
    module Applicative_infix
    
    module Applicative_infix
    
    module type S
    
    module Applicative_infix
    
    module type S2
    
    module Applicative_infix
    
    module S2_to_S
    
    argument 1-X
    
    module Applicative_infix
    
    module Applicative_infix
    
    module S2_to_S3
    
    argument 1-X
    
    module Applicative_infix
    
    module Applicative_infix
    
    module type S3
    
    module Applicative_infix
    
    module S3_to_S2
    
    argument 1-X
    
    module Applicative_infix
    
    module Applicative_infix
    
    module S_to_S2
    
    argument 1-X
    
    module Applicative_infix
    
    module Applicative_infix
  - module Array
  - module Avltree
  - module Backtrace
    
    module Exn
  - module Binary_search
  - module Binary_searchable
    
    module type Indexable
    
    module type Indexable1
    
    module Make
    
    argument 1-T
    
    module Make1
    
    argument 1-T
    
    module type S
    
    module type S1
  - module Blit
    
    module Make
    
    argument 1-Sequence
    
    module Make1
    
    argument 1-Sequence
    
    module Make1_generic
    
    argument 1-Sequence
    
    module Make_distinct
    
    argument 1-Src
    
    argument 2-Dst
    
    module Make_to_string
    
    argument 1-T
    
    argument 2-To_bytes
    
    module type S
    
    module type S1
    
    module type S1_distinct
    
    module type S_distinct
    
    module type S_to_string
    
    module type Sequence
    
    module type Sequence1
  - module Bool
    
    module Non_short_circuiting
  - module Buffer
    
    module type S
    
    module To_string
    
    module To_string
  - module Bytes
    
    module From_string
    
    module To_string
  - module Char
    
    module Caseless
    
    module O
  - module Comparable
    
    module Infix
    
    argument 1-T
    
    module Inherit
    
    argument 1-C
    
    argument 2-T
    
    module Make
    
    argument 1-T
    
    module Make_using_comparator
    
    argument 1-T
    
    module Poly
    
    argument 1-T
    
    module Polymorphic_compare
    
    argument 1-T
    
    module type S
    
    module Validate
    
    argument 1-T
    
    module Validate_with_zero
    
    argument 1-T
    
    module With_zero
    
    argument 1-T
  - module Comparator
    
    module Derived
    
    argument 1-M
    
    module Derived2
    
    argument 1-M
    
    module Derived_phantom
    
    argument 1-M
    
    module Make
    
    argument 1-M
    
    module Make1
    
    argument 1-M
    
    module Poly
    
    module type S
    
    module type S1
    
    module type S_fc
    
    module S_to_S1
    
    argument 1-S
  - module Comparisons
    
    module type Infix
    
    module type S
  - module Container
    
    module Continue_or_stop
    
    module type Generic
    
    module type Generic_phantom
    
    module Make
    
    argument 1-T
    
    module Make0
    
    argument 1-T
    
    module Elt
    
    module type S0
    
    module type S0_phantom
    
    module type S1
    
    module type S1_phantom
    
    module type S1_phantom_invariant
    
    module type Summable
  - module Continue_or_stop
  - module Either
    
    module First
    
    module Applicative_infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type Focused
    
    module Applicative_infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Second
    
    module Applicative_infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
  - module Equal
    
    module type S
    
    module type S1
    
    module type S2
    
    module type S3
  - module Error
    
    module Internal_repr
  - module Exn
  - module Export
  - module Field
  - module Float
    
    module Class
    
    module O
    
    module O_dot
    
    module Parts
    
    module Terse
  - module Floatable
    
    module type S
  - module Fn
  - module Formatter
  - module Hash
    
    module Builtin
    
    module F
    
    argument 1-Hash
    
    module For_tests
    
    module Builtin
    
    module For_tests
    
    module For_tests
    
    module type Full
    
    module Builtin
    
    module For_tests
    
    module type S
    
    module For_tests
  - module Hash_set
    
    module type Accessors
    
    module Creators
    
    argument 1-Elt
    
    module type Creators_generic
    
    module Key
    
    module type S
    
    module M
    
    argument 1-Elt
    
    module type M_of_sexp
    
    module Poly
    
    module type Sexp_of_m
  - module Hashable
    
    module type Hashable
    
    module type Key
  - module Hasher
    
    module type S
    
    module type S1
  - module Hashtbl
    
    module type Accessors
    
    module Creators
    
    argument 1-Key
    
    module type For_deriving
    
    module type M_of_sexp
    
    module type Sexp_of_m
    
    module Key
    
    module type S
    
    module M
    
    argument 1-K
    
    module type M_of_sexp
    
    module Merge_into_action
    
    module type Multi
    
    module Poly
    
    module type S_poly
    
    module type S_without_submodules
    
    module type Sexp_of_m
  - module Identifiable
    
    module Make
    
    argument 1-M
    
    module Make_using_comparator
    
    argument 1-M
    
    module type S
  - module Indexed_container
    
    module Make
    
    argument 1-T
    
    module type S1
  - module Info
    
    module Internal_repr
    
    module type S
    
    module Internal_repr
  - module Int
    
    module Hex
    
    module type Hexable
    
    module Hex
    
    module type Int_without_module_types
    
    module Hex
    
    module O
    
    module O
    
    module type Operators
    
    module type Operators_unbounded
    
    module type Round
    
    module type S
    
    module Hex
    
    module O
    
    module type S_common
    
    module Hex
    
    module type S_unbounded
    
    module Hex
    
    module O
  - module Int32
    
    module Hex
    
    module O
  - module Int63
    
    module Hex
    
    module O
    
    module Overflow_exn
  - module Int64
    
    module Hex
    
    module O
  - module Int_conversions
    
    module Make
    
    argument 1-I
    
    module Make_hex
    
    argument 1-I
    
    module Hex
  - module Int_math
    
    module Make
    
    argument 1-X
    
    module type Make_arg
    
    module Private
    
    module Pow_overflow_bounds
  - module Intable
    
    module type S
  - module Invariant
    
    module type S
    
    module type S1
    
    module type S2
    
    module type S3
  - module Lazy
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module T_unforcing
  - module Linked_queue
  - module List
    
    module Assoc
    
    module Infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Or_unequal_lengths
  - module Map
    
    module type Accessors1
    
    module type Accessors2
    
    module type Accessors3
    
    module type Accessors3_with_comparator
    
    module type Accessors_generic
    
    module type Compare_m
    
    module Continue_or_stop
    
    module type Creators1
    
    module type Creators2
    
    module type Creators3_with_comparator
    
    module type Creators_and_accessors1
    
    module type Creators_and_accessors2
    
    module type Creators_and_accessors3_with_comparator
    
    module type Creators_and_accessors_generic
    
    module type Creators_generic
    
    module type Equal_m
    
    module Finished_or_unfinished
    
    module type For_deriving
    
    module type Compare_m
    
    module type Equal_m
    
    module type M_of_sexp
    
    module type Sexp_of_m
    
    module M
    
    argument 1-K
    
    module type M_of_sexp
    
    module Or_duplicate
    
    module Poly
    
    module type S_poly
    
    module type Sexp_of_m
    
    module Symmetric_diff_element
    
    module Using_comparator
    
    module Empty_without_value_restriction
    
    argument 1-K
    
    module Tree
    
    module With_comparator
    
    module With_first_class_module
    
    module Without_comparator
  - module Maybe_bound
  - module Monad
    
    module type Basic
    
    module type Basic2
    
    module type Basic3
    
    module type Basic_indexed
    
    module Ident
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type Infix
    
    module type Infix2
    
    module type Infix3
    
    module type Infix_indexed
    
    module Make
    
    argument 1-X
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Make2
    
    argument 1-X
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Make3
    
    argument 1-X
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Make_indexed
    
    argument 1-X
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S2
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S3
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S_indexed
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module type S_without_syntax
    
    module Monad_infix
    
    module type Syntax
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module type Syntax2
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module type Syntax3
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module type Syntax_indexed
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
  - module Nativeint
    
    module Hex
    
    module O
  - module Nothing
  - module Option
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
  - module Option_array
  - module Or_error
    
    module Applicative_infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
  - module Ordered_collection_common
    
    module Private
  - module Ordering
    
    module Export
  - module Poly
  - module Popcount
  - module Pretty_printer
    
    module Register
    
    argument 1-M
    
    module Register_pp
    
    argument 1-M
    
    module type S
  - module Printf
  - module Queue
    
    module type S
  - module Random
    
    module State
  - module Ref
    
    module And_value
  - module Result
    
    module Export
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
  - module Sequence
    
    module Expert
    
    module Generator
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Monad_infix
    
    module Infix
    
    module Let_syntax
    
    module Let_syntax
    
    module Open_on_rhs
    
    module Merge_with_duplicates_element
    
    module Monad_infix
    
    module Step
  - module Set
    
    module type Accessors0
    
    module Named
    
    module type Accessors1
    
    module Named
    
    module type Accessors2
    
    module Named
    
    module type Accessors2_with_comparator
    
    module Named
    
    module type Accessors_generic
    
    module Named
    
    module type Compare_m
    
    module type Creators0
    
    module type Creators1
    
    module type Creators2
    
    module type Creators2_with_comparator
    
    module type Creators_and_accessors0
    
    module Named
    
    module type Creators_and_accessors1
    
    module Named
    
    module type Creators_and_accessors2
    
    module Named
    
    module type Creators_and_accessors2_with_comparator
    
    module Named
    
    module type Creators_generic
    
    module type Elt_plain
    
    module type Equal_m
    
    module type For_deriving
    
    module type Compare_m
    
    module type Equal_m
    
    module type M_of_sexp
    
    module type Sexp_of_m
    
    module M
    
    argument 1-Elt
    
    module type M_of_sexp
    
    module Merge_to_sequence_element
    
    module Named
    
    module Poly
    
    module Named
    
    module type S_poly
    
    module Named
    
    module type Sexp_of_m
    
    module Using_comparator
    
    module Empty_without_value_restriction
    
    argument 1-Elt
    
    module Named
    
    module Tree
    
    module Named
    
    module With_comparator
    
    module With_first_class_module
    
    module Without_comparator
  - module Sexp
    
    module Private
    
    module Raw_grammar
    
    module Atom
    
    module Builtin
  - module Sexpable
    
    module Of_sexpable
    
    argument 1-Sexpable
    
    argument 2-M
    
    module Of_sexpable1
    
    argument 1-Sexpable
    
    argument 2-M
    
    module Of_sexpable2
    
    argument 1-Sexpable
    
    argument 2-M
    
    module Of_sexpable3
    
    argument 1-Sexpable
    
    argument 2-M
    
    module Of_stringable
    
    argument 1-M
    
    module type S
    
    module type S1
    
    module type S2
    
    module type S3
  - module Sign
  - module Sign_or_nan
  - module Source_code_position
  - module Stack
    
    module type S
  - module Staged
  - module String
    
    module Caseless
    
    module Escaping
    
    module Search_pattern
  - module Stringable
    
    module type S
  - module Sys
  - module type T
    
    module type T
    
    module type T1
    
    module type T2
    
    module type T3
  - module type T1
  - module type T2
  - module type T3
  - module Type_equal
    
    module Composition_preserves_injectivity
    
    argument 1-M1
    
    argument 2-M2
    
    module Id
    
    module Uid
    
    module type Injective
    
    module type Injective2
    
    module Lift
    
    argument 1-X
    
    module Lift2
    
    argument 1-X
    
    module Lift3
    
    argument 1-X
  - module Uchar
  - module Uniform_array
  - module Unit
  - module Validate
    
    module Infix
  - module Variant
  - module With_return
  - module Word_size
library base.base_internalhash_types
- module Base_internalhash_types
library base.caml
- module Caml
library base.md5
- module Md5_lib
library base.shadow_stdlib
- module Shadow_stdlib

Module Base . Hash

module type Full = sig ... end

module type S = sig ... end

module F
  (Hash : S) : 
  Full
    with type hash_value = Hash.hash_value
     and type state = Hash.state
     and type seed = Hash.seed

The code of ppx_hash is agnostic to the choice of hash algorithm that is used. However, it is not currently possible to mix various choices of hash algorithms in a given code base.

We experimented with:

(a) custom hash algorithms implemented in OCaml and
(b) in C;
(c) OCaml's internal hash function (which is a custom version of Murmur3, implemented in C);
(d) siphash, a modern hash function implemented in C.

Our findings were as follows:

Implementing our own custom hash algorithms in OCaml and C yielded very little performance improvement over the (c) proposal, without providing the benefit of being a peer-reviewed, widely used hash function.

Siphash (a modern hash function with an internal state of 32 bytes) has a worse performance profile than (a,b,c) above (hashing takes more time). Since its internal state is bigger than an OCaml immediate value, one must either manage allocation of such state explicitly, or paying the cost of allocation each time a hash is computed. While being a supposedly good hash function (with good hash quality), this quality was not translated in measurable improvements in our macro benchmarks. (Also, based on the data available at the time of writing, it's unclear that other hash algorithms in this class would be more than marginally faster.)

By contrast, using the internal combinators of OCaml hash function means that we do not allocate (the internal state of this hash function is 32 bit) and have the same quality and performance as Hashtbl.hash.

Hence, we are here making the choice of using this Internalhash (that is, Murmur3, the OCaml hash algorithm as of 4.03) as our hash algorithm. It means that the state of the hash function does not need to be preallocated, and makes for simpler use in hash tables and other structures.

include Full
  with type state = Base_internalhash_types.state
   and type seed = Base_internalhash_types.seed
   and type hash_value = Base_internalhash_types.hash_value

val description : string

Name of the hash-function, e.g., "internalhash", "siphash"

type state = Base_internalhash_types.state

state is the internal hash-state used by the hash function.

val fold_int : state -> int -> state

fold_<T> state v incorporates a value v of type <T> into the hash-state, returning a modified hash-state. Implementations of the fold_<T> functions may mutate the state argument in place, and return a reference to it. Implementations of the fold_<T> functions should not allocate.

val fold_int64 : state -> int64 -> state

val fold_float : state -> float -> state

val fold_string : state -> string -> state

type seed = Base_internalhash_types.seed

seed is the type used to seed the initial hash-state.

val alloc : unit -> state

alloc () returns a fresh uninitialized hash-state. May allocate.

val reset : ?seed:seed -> state -> state

reset ?seed state initializes/resets a hash-state with the given seed, or else a default-seed. Argument state may be mutated. Should not allocate.

type hash_value = Base_internalhash_types.hash_value

hash_value The type of hash values, returned by get_hash_value.

val get_hash_value : state -> hash_value

get_hash_value extracts a hash-value from the hash-state.

module For_tests : sig ... end

type 'a folder = state -> 'a -> state

val create : ?seed:seed -> unit -> state

create ?seed () is a convenience. Equivalent to reset ?seed (alloc ()).

val of_fold : ( state -> 'a -> state ) -> 'a -> hash_value

of_fold fold constructs a standard hash function from an existing fold function.

module Builtin : sig ... end

val run : ?seed:seed -> 'a folder -> 'a -> hash_value

run ?seed folder x runs folder on x in a newly allocated hash-state, initialized using optional seed or a default-seed.

The following identity exists: run [%hash_fold: T] == [%hash: T]

run can be used if we wish to run a hash-folder with a non-default seed.