hashes

  Source   Edit

This module implements efficient computations of hash values for diverse Nim types. All the procs are based on these two building blocks:

  • !& proc used to start or mix a hash value, and
  • !$ proc used to finish the hash value.

If you want to implement hash procs for your custom types, you will end up writing the following kind of skeleton of code:

Example:

type
  Something = object
    foo: int
    bar: string

iterator items(x: Something): int =
  yield hash(x.foo)
  yield hash(x.bar)

proc hash(x: Something): Hash =
  ## Computes a Hash from `x`.
  var h: Hash = 0
  # Iterate over parts of `x`.
  for xAtom in x:
    # Mix the atom with the partial hash.
    h = h !& xAtom
  # Finish the hash.
  result = !$h
If your custom types contain fields for which there already is a hash proc, you can simply hash together the hash values of the individual fields:

Example:

type
  Something = object
    foo: int
    bar: string

proc hash(x: Something): Hash =
  ## Computes a Hash from `x`.
  var h: Hash = 0
  h = h !& hash(x.foo)
  h = h !& hash(x.bar)
  result = !$h
Note: If the type has a == operator, the following must hold: If two values compare equal, their hashes must also be equal.

See also

Types

Hash = int
A hash value. Hash tables using these values should always have a size of a power of two so they can use the and operator instead of mod for truncation of the hash value.   Source   Edit

Procs

proc `!&`(h: Hash; val: int): Hash {...}{.inline, raises: [], tags: [].}

Mixes a hash value h with val to produce a new hash value.

This is only needed if you need to implement a hash proc for a new datatype.

  Source   Edit
proc `!$`(h: Hash): Hash {...}{.inline, raises: [], tags: [].}

Finishes the computation of the hash value.

This is only needed if you need to implement a hash proc for a new datatype.

  Source   Edit
proc hashWangYi1(x: int64 | uint64 | Hash): Hash {...}{.inline.}

Wang Yi's hash_v1 for 64-bit ints (see https://github.com/rurban/smhasher for more details). This passed all scrambling tests in Spring 2019 and is simple.

Note: It's ok to define proc(x: int16): Hash = hashWangYi1(Hash(x)).

  Source   Edit
proc hashData(data: pointer; size: int): Hash {...}{.raises: [], tags: [].}
Hashes an array of bytes of size size.   Source   Edit
proc hash(x: pointer): Hash {...}{.inline, raises: [], tags: [].}
Efficient hashing of pointers.   Source   Edit
proc hash[T: proc](x: T): Hash {...}{.inline.}
Efficient hashing of proc vars. Closures are supported too.   Source   Edit
proc hashIdentity[T: Ordinal | enum](x: T): Hash {...}{.inline.}
The identity hash, i.e. hashIdentity(x) = x.   Source   Edit
proc hash[T: Ordinal | enum](x: T): Hash {...}{.inline.}
Efficient hashing of integers.   Source   Edit
proc hash(x: float): Hash {...}{.inline, raises: [], tags: [].}
Efficient hashing of floats.   Source   Edit
proc hash(x: string): Hash {...}{.raises: [], tags: [].}

Efficient hashing of strings.

See also:

Example:

doAssert hash("abracadabra") != hash("AbracadabrA")
  Source   Edit
proc hash(x: cstring): Hash {...}{.raises: [], tags: [].}
Efficient hashing of null-terminated strings.

Example:

doAssert hash(cstring"abracadabra") == hash("abracadabra")
doAssert hash(cstring"AbracadabrA") == hash("AbracadabrA")
doAssert hash(cstring"abracadabra") != hash(cstring"AbracadabrA")
  Source   Edit
proc hash(sBuf: string; sPos, ePos: int): Hash {...}{.raises: [], tags: [].}

Efficient hashing of a string buffer, from starting position sPos to ending position ePos (included).

hash(myStr, 0, myStr.high) is equivalent to hash(myStr).

Example:

var a = "abracadabra"
doAssert hash(a, 0, 3) == hash(a, 7, 10)
  Source   Edit
proc hashIgnoreStyle(x: string): Hash {...}{.raises: [], tags: [].}

Efficient hashing of strings; style is ignored.

Note: This uses a different hashing algorithm than hash(string).

See also:

Example:

doAssert hashIgnoreStyle("aBr_aCa_dAB_ra") == hashIgnoreStyle("abracadabra")
doAssert hashIgnoreStyle("abcdefghi") != hash("abcdefghi")
  Source   Edit
proc hashIgnoreStyle(sBuf: string; sPos, ePos: int): Hash {...}{.raises: [], tags: [].}

Efficient hashing of a string buffer, from starting position sPos to ending position ePos (included); style is ignored.

Note: This uses a different hashing algorithm than hash(string).

hashIgnoreStyle(myBuf, 0, myBuf.high) is equivalent to hashIgnoreStyle(myBuf).

Example:

var a = "ABracada_b_r_a"
doAssert hashIgnoreStyle(a, 0, 3) == hashIgnoreStyle(a, 7, a.high)
  Source   Edit
proc hashIgnoreCase(x: string): Hash {...}{.raises: [], tags: [].}

Efficient hashing of strings; case is ignored.

Note: This uses a different hashing algorithm than hash(string).

See also:

Example:

doAssert hashIgnoreCase("ABRAcaDABRA") == hashIgnoreCase("abRACAdabra")
doAssert hashIgnoreCase("abcdefghi") != hash("abcdefghi")
  Source   Edit
proc hashIgnoreCase(sBuf: string; sPos, ePos: int): Hash {...}{.raises: [], tags: [].}

Efficient hashing of a string buffer, from starting position sPos to ending position ePos (included); case is ignored.

Note: This uses a different hashing algorithm than hash(string).

hashIgnoreCase(myBuf, 0, myBuf.high) is equivalent to hashIgnoreCase(myBuf).

Example:

var a = "ABracadabRA"
doAssert hashIgnoreCase(a, 0, 3) == hashIgnoreCase(a, 7, 10)
  Source   Edit
proc hash[T: tuple](x: T): Hash
Efficient hashing of tuples. There must be a hash proc defined for each of the field types.   Source   Edit
proc hash[A](x: openArray[A]): Hash
Efficient hashing of arrays and sequences. There must be a hash proc defined for the element type A.   Source   Edit
proc hash[A](aBuf: openArray[A]; sPos, ePos: int): Hash

Efficient hashing of portions of arrays and sequences, from starting position sPos to ending position ePos (included). There must be a hash proc defined for the element type A.

hash(myBuf, 0, myBuf.high) is equivalent to hash(myBuf).

Example:

let a = [1, 2, 5, 1, 2, 6]
doAssert hash(a, 0, 1) == hash(a, 3, 4)
  Source   Edit
proc hash[A](x: set[A]): Hash
Efficient hashing of sets. There must be a hash proc defined for the element type A.   Source   Edit