std/hashes

Этот модуль реализует эффективные вычисления хеш-значений для различных типов Nim. Все процедуры основаны на этих двух строительных блоках:

• !& proc используется для начала или смешивания хеш-значения, и
• !$ proc используется для завершения вычисления хеш-значения.

Если вы хотите реализовать процедуры хеширования для своих пользовательских типов, вам нужно будет написать нечто подобное:

Пример:

import std/hashes
type
  Something = object
    foo: int
    bar: string

iterator items(x: Something): Hash =
  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

Пример:

import std/hashes
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

См. также

• модуль md5 для алгоритма MD5 контрольной суммы
• модуль base64 для кодировщика и декодировщика Base64
• модуль sha1 для алгоритма SHA-1 контрольной суммы
• модуль tables для хеш-таблиц

Импорты

since

Типы

Hash = int

Значение хеша. Хеш-таблицы, использующие эти значения, всегда должны иметь размер, являющийся степенью двойки, чтобы они могли использовать оператор and вместо mod для усечения значения хеша. Источник Редактировать

Процедуры

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

Завершает вычисление значения хэш-функции.

Это необходимо только в том случае, если вам нужно реализовать процедуру hash для нового типа данных.

Исходный код Редактировать

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

Смешивает значение хэша h со значением val для получения нового значения хэша.

Это необходимо только в том случае, если вам нужно реализовать процедуру hash для нового типа данных.

Исходный код Редактировать

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

Эффективное хеширование буфера строки, от начальной позиции sPos до конечной позиции ePos (включительно).

hash(myStr, 0, myStr.high) эквивалентно hash(myStr).

Пример:

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

Исходный код Редактировать

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

Эффективное хеширование строк с нулевым завершением.

Пример:

doAssert hash(cstring"abracadabra") == hash("abracadabra")
doAssert hash(cstring"AbracadabrA") == hash("AbracadabrA")
doAssert hash(cstring"abracadabra") != hash(cstring"AbracadabrA")

Исходный код Редактировать

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

Эффективное хеширование чисел с плавающей точкой. Исходный код Редактировать

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

Эффективная перегрузка hash. Исходный код Редактировать

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

Эффективное хеширование строк.

См. также:

• hashIgnoreStyle
• hashIgnoreCase

Пример:

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

Исходный код Редактировать

proc hash[A](aBuf: openArray[A]; sPos, ePos: int): Hash

Эффективное хеширование частей массивов и последовательностей, от начальной позиции sPos до конечной позиции ePos (включительно). Для типа элемента A должна быть определена процедура hash.

hash(myBuf, 0, myBuf.high) эквивалентно hash(myBuf).

Пример:

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

Исходный код Редактировать

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

Исходный код Редактировать

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

Исходный код Редактировать

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

Эффективное хеширование целых чисел. Исходный код Редактировать

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

Эффективная перегрузка hash.

Пример:

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

Пример:

# proc
proc fn1() = discard
const fn1b = fn1
assert hash(fn1b) == hash(fn1)

# closure
proc outer =
  var a = 0
  proc fn2() = a.inc
  assert fn2 is "closure"
  let fn2b = fn2
  assert hash(fn2b) == hash(fn2)
  assert hash(fn2) != hash(fn1)
outer()

Исходный код Редактировать

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

Эффективная перегрузка hash.

Пример:

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

Исходный код Редактировать

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

Эффективная перегрузка hash.

Важно: Используйте -d:nimPreviewHashRef для включения хеширования ref. Ожидается, что это поведение станет новым значением по умолчанию в будущих версиях.

Пример: cmd: -d:nimPreviewHashRef

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

Пример: cmd: -d:nimPreviewHashRef

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

Исходный код Редактировать

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

Хеширует массив байтов размером size. Исходный код Редактировать

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

Идентичный хеш, т.е. hashIdentity(x) = x. Исходный код Редактировать

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

Эффективное хеширование буфера строки, от начальной позиции sPos до конечной позиции ePos (включительно); регистр игнорируется.

Примечание: Используется другой алгоритм хеширования, чем hash(string).

hashIgnoreCase(myBuf, 0, myBuf.high) эквивалентно hashIgnoreCase(myBuf).

Пример:

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

Исходный код Редактировать

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

Эффективное хеширование строк; регистр игнорируется.

Примечание: Используется другой алгоритм хеширования, чем hash(string).

См. также:

• hashIgnoreStyle

Пример:

doAssert hashIgnoreCase("ABRAcaDABRA") == hashIgnoreCase("abRACAdabra")
doAssert hashIgnoreCase("abcdefghi") != hash("abcdefghi")

Исходный код Редактировать

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

Эффективное хеширование буфера строки, от начальной позиции sPos до конечной позиции ePos (включительно); стиль игнорируется.

Примечание: Используется другой алгоритм хеширования, чем hash(string).

hashIgnoreStyle(myBuf, 0, myBuf.high) эквивалентно hashIgnoreStyle(myBuf).

Пример:

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

Исходный код Редактировать

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

Эффективное хеширование строк; стиль игнорируется.

Примечание: Используется другой алгоритм хеширования, чем hash(string).

См. также:

• hashIgnoreCase

Пример:

doAssert hashIgnoreStyle("aBr_aCa_dAB_ra") == hashIgnoreStyle("abracadabra")
doAssert hashIgnoreStyle("abcdefghi") != hash("abcdefghi")

Исходный код Редактировать

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

Хэш-функция Wang Yi's hash_v1 для 64-битных целых чисел (см. https://github.com/rurban/smhasher для получения дополнительной информации). Она прошла все тесты на сжатие весной 2019 года и проста.

Примечание: Можно определить proc(x: int16): Hash = hashWangYi1(Hash(x)).

Исходный код Редактировать