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:

  1. import std/hashes
  2. type
  3.   Something = object
  4.     foo: int
  5.     bar: string
  7. iterator items(x: Something): Hash =
  8.   yield hash(x.foo)
  9.   yield hash(x.bar)
  11. proc hash(x: Something): Hash =
  12.   ## Computes a Hash from `x`.
  13.   var h: Hash = 0
  14.   # Iterate over parts of `x`.
  15.   for xAtom in x:
  16.     # Mix the atom with the partial hash.
  17.     h = h !& xAtom
  18.   # Finish the hash.
  19.   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:

  1. import std/hashes
  2. type
  3.   Something = object
  4.     foo: int
  5.     bar: string
  7. proc hash(x: Something): Hash =
  8.   ## Computes a Hash from `x`.
  9.   var h: Hash = 0
  10.   h = h !& hash(x.foo)
  11.   h = h !& hash(x.bar)
  12.   result = !$h

Important: Use -d:nimPreviewHashRef to enable hashing refs. It is expected that this behavior becomes the new default in upcoming versions.

Note: If the type has a \== operator, the following must hold: If two values compare equal, their hashes must also be equal.

See also

Imports

since

Types

  1. 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

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

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 

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

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 

  1. proc hash(sBuf: string; sPos, ePos: int): Hash {....raises: [], tags: [],
  2.     forbids: [].}

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:

  1. var a = "abracadabra"
  2. doAssert hash(a, 0, 3) == hash(a, 7, 10)

Source Edit 

  1. proc hash(x: cstring): Hash {....raises: [], tags: [], forbids: [].}

Efficient hashing of null-terminated strings.

Example:

  1. doAssert hash(cstring"abracadabra") == hash("abracadabra")
  2. doAssert hash(cstring"AbracadabrA") == hash("AbracadabrA")
  3. doAssert hash(cstring"abracadabra") != hash(cstring"AbracadabrA")

Source Edit 

  1. proc hash(x: float): Hash {.inline, ...raises: [], tags: [], forbids: [].}

Efficient hashing of floats. Source Edit 

  1. proc hash(x: pointer): Hash {.inline, ...raises: [], tags: [], forbids: [].}

Efficient hash overload. Source Edit 

  1. proc hash(x: string): Hash {....raises: [], tags: [], forbids: [].}

Efficient hashing of strings.

See also:

Example:

  1. doAssert hash("abracadabra") != hash("AbracadabrA")

Source Edit 

  1. 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:

  1. let a = [1, 2, 5, 1, 2, 6]
  2. doAssert hash(a, 0, 1) == hash(a, 3, 4)

Source Edit 

  1. proc hash[A](x: openArray[A]): Hash

Source Edit 

  1. proc hash[A](x: set[A]): Hash

Source Edit 

  1. proc hash[T: Ordinal | enum](x: T): Hash {.inline.}

Efficient hashing of integers. Source Edit 

  1. proc hash[T: tuple | object | proc | iterator {.closure.}](x: T): Hash

Efficient hash overload.

Example:

  1. # for `tuple|object`, `hash` must be defined for each component of `x`.
  2. type Obj = object
  3.   x: int
  4.   y: string
  5. type Obj2[T] = object
  6.   x: int
  7.   y: string
  8. assert hash(Obj(x: 520, y: "Nim")) != hash(Obj(x: 520, y: "Nim2"))
  9. # you can define custom hashes for objects (even if they're generic):
  10. proc hash(a: Obj2): Hash = hash((a.x))
  11. assert hash(Obj2[float](x: 520, y: "Nim")) == hash(Obj2[float](x: 520, y: "Nim2"))

Example:

  1. # proc
  2. proc fn1() = discard
  3. const fn1b = fn1
  4. assert hash(fn1b) == hash(fn1)
  6. # closure
  7. proc outer =
  8.   var a = 0
  9.   proc fn2() = a.inc
  10.   assert fn2 is "closure"
  11.   let fn2b = fn2
  12.   assert hash(fn2b) == hash(fn2)
  13.   assert hash(fn2) != hash(fn1)
  14. outer()

Source Edit 

  1. proc hash[T](x: ptr [T]): Hash {.inline.}

Efficient hash overload.

Example:

  1. var a: array[10, uint8]
  2. assert a[0].addr.hash != a[1].addr.hash
  3. assert cast[pointer](a[0].addr).hash == a[0].addr.hash

Source Edit 

  1. proc hash[T](x: ref [T]): Hash {.inline.}

Efficient hash overload.

Important: Use -d:nimPreviewHashRef to enable hashing refs. It is expected that this behavior becomes the new default in upcoming versions.

Example: cmd: -d:nimPreviewHashRef

  1. type A = ref object
  2.   x: int
  3. let a = A(x: 3)
  4. let ha = a.hash
  5. assert ha != A(x: 3).hash # A(x: 3) is a different ref object from `a`.
  6. a.x = 4
  7. assert ha == a.hash # the hash only depends on the address

Example: cmd: -d:nimPreviewHashRef

  1. # you can overload `hash` if you want to customize semantics
  2. type A[T] = ref object
  3.   x, y: T
  4. proc hash(a: A): Hash = hash(a.x)
  5. assert A[int](x: 3, y: 4).hash == A[int](x: 3, y: 5).hash

Source Edit 

  1. proc hashData(data: pointer; size: int): Hash {....raises: [], tags: [],
  2.     forbids: [].}

Hashes an array of bytes of size size. Source Edit 

  1. proc hashIdentity[T: Ordinal | enum](x: T): Hash {.inline.}

The identity hash, i.e. hashIdentity(x) = x. Source Edit 

  1. proc hashIgnoreCase(sBuf: string; sPos, ePos: int): Hash {....raises: [], tags: [],
  2.     forbids: [].}

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:

  1. var a = "ABracadabRA"
  2. doAssert hashIgnoreCase(a, 0, 3) == hashIgnoreCase(a, 7, 10)

Source Edit 

  1. proc hashIgnoreCase(x: string): Hash {....raises: [], tags: [], forbids: [].}

Efficient hashing of strings; case is ignored.

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

See also:

Example:

  1. doAssert hashIgnoreCase("ABRAcaDABRA") == hashIgnoreCase("abRACAdabra")
  2. doAssert hashIgnoreCase("abcdefghi") != hash("abcdefghi")

Source Edit 

  1. proc hashIgnoreStyle(sBuf: string; sPos, ePos: int): Hash {....raises: [],
  2.     tags: [], forbids: [].}

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:

  1. var a = "ABracada_b_r_a"
  2. doAssert hashIgnoreStyle(a, 0, 3) == hashIgnoreStyle(a, 7, a.high)

Source Edit 

  1. proc hashIgnoreStyle(x: string): Hash {....raises: [], tags: [], forbids: [].}

Efficient hashing of strings; style is ignored.

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

See also:

Example:

  1. doAssert hashIgnoreStyle("aBr_aCa_dAB_ra") == hashIgnoreStyle("abracadabra")
  2. doAssert hashIgnoreStyle("abcdefghi") != hash("abcdefghi")

Source Edit 

  1. 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