Модуль MoreLabels.Hashtbl

module Hashtbl: sig .. end

Хэш-таблицы и хэш-функции.

Хэш-таблицы — это хэшированные ассоциативные таблицы с модификацией на месте. Поскольку большинство операций над хэш-таблицей изменяют входные данные, они чаще используются в императивном коде. Поиск значения, связанного с ключом (см. MoreLabels.Hashtbl.find, MoreLabels.Hashtbl.find_opt), обычно очень быстрый, часто быстрее, чем эквивалентный поиск в MoreLabels.Map.

Функторы MoreLabels.Hashtbl.Make и MoreLabels.Hashtbl.MakeSeeded могут быть использованы, когда ключевыми являются производительность или гибкость. Пользователь предоставляет собственные функции равенства и хэширования для типа ключа и получает тип пользовательской хэш-таблицы для этого конкретного типа ключа.

Предупреждение хэш-таблица так же хороша, как и хэш-функция. Плохая хэш-функция превратит таблицу в вырожденный ассоциативный список с линейным временем поиска вместо постоянного.

Полиморфная MoreLabels.Hashtbl.t хэш-таблица полезна в более простых случаях или в интерактивных средах. Она использует полиморфную функцию MoreLabels.Hashtbl.hash, определённую в OCaml-런타임 (на момент написания, это SipHash), а также полиморфное равенство (=).

См. раздел примеров.

Доступ без синхронизации

Доступ к хэш-таблице без синхронизации может привести к недопустимому состоянию хэш-таблицы. Таким образом, одновременный доступ к хэш-таблицам должен быть синхронизирован (например, с помощью Mutex.t).

Общий интерфейс

type ('a, 'b) t = ('a, 'b) Hashtbl.t

Тип хэш-таблиц от типа 'a к типу 'b.

val create : ?random:bool -> int -> ('a, 'b) t

Hashtbl.create n создаёт новую пустую хэш-таблицу с начальным размером n. Для наилучших результатов, n должен быть порядка ожидаемого количества элементов, которые будут в таблице. Таблица увеличивается по мере необходимости, поэтому n — это всего лишь первоначальное предположение.

Необязательный параметр ~random (булево значение) управляет тем, случайным или детерминированным образом организована внутренняя структура хэш-таблицы при каждом выполнении Hashtbl.create.

Хэш-таблица, созданная с ~random, установленным в false, использует фиксированную хэш-функцию (MoreLabels.Hashtbl.hash) для распределения ключей по корзинам. В результате коллизии между ключами происходят детерминированно. В веб-приложениях или других приложениях, чувствительных к безопасности, детерминированные шаблоны коллизий могут быть использованы злоумышленником для создания атаки с отказом в обслуживании: злоумышленник отправляет входные данные, специально созданные для создания большого числа коллизий в таблице, что замедляет приложение.

Хэш-таблица, созданная с ~random, установленным в true, использует хэш-функцию с начальным значением MoreLabels.Hashtbl.seeded_hash, чьё значение случайным образом выбирается во время создания хэш-таблицы. По сути, используемая хэш-функция случайным образом выбирается среди 2^{30} разных хэш-функций. Все эти хэш-функции имеют разные шаблоны коллизий, что делает неэффективной описанную выше атаку с отказом в обслуживании. Однако из-за случайности перечисление всех элементов хэш-таблицы с помощью MoreLabels.Hashtbl.fold или MoreLabels.Hashtbl.iter больше не является детерминированным: элементы перечисляются в разном порядке при разных запусках программы.

Если параметр ~random не задан, хэш-таблицы создаются по умолчанию в неслучайном режиме. Это значение по умолчанию можно изменить либо программно, вызвав MoreLabels.Hashtbl.randomize, либо установив флаг R в переменной окружения OCAMLRUNPARAM.

До 4.00 параметр ~random отсутствовал, и все хэш-таблицы создавались в нерандомизированном режиме.

val clear : ('a, 'b) t -> unit

Очистить хэш-таблицу. Используйте reset вместо clear, чтобы уменьшить размер таблицы корзин до её начального размера.

val reset : ('a, 'b) t -> unit

Очистить хэш-таблицу и уменьшить размер таблицы корзин до её начального размера.

С 4.00

val copy : ('a, 'b) t -> ('a, 'b) t

Возвращает копию заданной хэш-таблицы.

val add : ('a, 'b) t -> key:'a -> data:'b -> unit

Hashtbl.add tbl ~key ~data добавляет привязку key к data в таблицу tbl.

Предупреждение: Предыдущие привязки для key не удаляются, а просто скрываются. То есть, после выполнения MoreLabels.Hashtbl.remove tbl key, предыдущая привязка для key, если она существовала, восстанавливается. (То же поведение, что и у ассоциативных списков.)

Если требуется классическое поведение замены элементов, см. MoreLabels.Hashtbl.replace.

val find : ('a, 'b) t -> 'a -> 'b

Hashtbl.find tbl x возвращает текущую привязку x в tbl, или поднимает Not_found если такой привязки не существует.

val find_opt : ('a, 'b) t -> 'a -> 'b option

Hashtbl.find_opt tbl x возвращает текущую привязку x в tbl, или None если такой привязки не существует.

С 4.05

val find_all : ('a, 'b) t -> 'a -> 'b list

Hashtbl.find_all tbl x возвращает список всех данных, связанных с x в tbl. Текущая привязка возвращается первой, затем предыдущие привязки в обратном порядке введения в таблицу.

val mem : ('a, 'b) t -> 'a -> bool

Hashtbl.mem tbl x проверяет, привязана ли x в tbl.

val remove : ('a, 'b) t -> 'a -> unit

Hashtbl.remove tbl x удаляет текущую привязку x в tbl, восстанавливая предыдущую привязку, если она существует. Ничего не делает, если x не привязано в tbl.

val replace : ('a, 'b) t -> key:'a -> data:'b -> unit

Hashtbl.replace tbl ~key ~data заменяет текущую привязку key в tbl привязкой key к data. Если key не привязано в tbl, привязка key к data добавляется в tbl. Это функционально эквивалентно MoreLabels.Hashtbl.remove tbl key и последующему MoreLabels.Hashtbl.add tbl key data.

val iter : f:(key:'a -> data:'b -> unit) -> ('a, 'b) t -> unit

Hashtbl.iter ~f tbl применяет f ко всем привязка в таблице tbl. f получает ключ в качестве первого аргумента, а связанное значение — как второй аргумент. Каждая привязка представляется f ровно один раз.

Порядок, в котором привязки передаются f, не определён. Однако, если таблица содержит несколько привязок к одному ключу, они передаются f в обратном порядке введения, то есть, самая последняя привязка передаётся первой.

Если хэш-таблица была создана в нерандомизированном режиме, порядок перечисления привязок воспроизводим при последующих запусках программы, а также между различными версиями OCaml. Для рандомизированных хэш-таблиц порядок перечисления полностью случайный.

Поведение не определено, если хэш-таблица изменяется с помощью f во время итерации.

val filter_map_inplace : f:(key:'a -> data:'b -> 'b option) -> ('a, 'b) t -> unit

Hashtbl.filter_map_inplace ~f tbl применяет f ко всем привязка в таблице tbl и обновляет каждую привязку в зависимости от результата f. Если f возвращает None, привязка отбрасывается. Если возвращает Some new_val, привязка обновляется, чтобы связать ключ со значением new_val.

Другие комментарии для MoreLabels.Hashtbl.iter также применимы.

С 4.03

val fold : f:(key:'a -> data:'b -> 'acc -> 'acc) ->       ('a, 'b) t -> init:'acc -> 'acc

Hashtbl.fold ~f tbl ~init вычисляет (f kN dN ... (f k1 d1 init)...), где k1 ... kN — ключи всех привязок в tbl, а d1 ... dN — связанные значения. Каждая привязка представляется f ровно один раз.

Поведение не определено, если хэш-таблица изменяется с помощью f во время итерации.

val length : ('a, 'b) t -> int

Hashtbl.length tbl возвращает количество привязок в tbl. Это занимает постоянное время. Множественные привязки учитываются по одному разу, поэтому Hashtbl.length даёт количество вызовов Hashtbl.iter своему первому аргументу.

val randomize : unit -> unit

После вызова Hashtbl.randomize(), хеш-таблицы создаются в случайном режиме по умолчанию: MoreLabels.Hashtbl.create возвращает случайные хеш-таблицы, если не задан необязательный параметр ~random:false. Тот же эффект можно достичь, установив параметр R в переменной окружения OCAMLRUNPARAM.

Рекомендуется, чтобы приложения или веб-фреймворки, которые нуждаются в защите от атаки типа "отказ в обслуживании", описанной в MoreLabels.Hashtbl.create, вызывали Hashtbl.randomize() во время инициализации перед созданием каких-либо доменов.

Обратите внимание, что после вызова Hashtbl.randomize(), нет возможности вернуться к поведению по умолчанию без случайного порядка MoreLabels.Hashtbl.create. Это сделано намеренно. Не случайные хеш-таблицы по-прежнему могут быть созданы с помощью Hashtbl.create ~random:false.

Since 4.00

val is_randomized : unit -> bool

Возвращает true, если таблицы в настоящее время создаются в случайном режиме по умолчанию, false в противном случае.

Since 4.03

val rebuild : ?random:bool ->       ('a, 'b) t -> ('a, 'b) t

Возвращает копию заданной хеш-таблицы. В отличие от MoreLabels.Hashtbl.copy, MoreLabels.Hashtbl.rebuild h перехеширует все записи (ключ, значение) исходной таблицы h. Возвращённая хеш-таблица будет случайной, если h была случайной, или необязательный параметр random имеет значение true, или если по умолчанию создаются случайные хеш-таблицы; см. MoreLabels.Hashtbl.create для получения дополнительной информации.

MoreLabels.Hashtbl.rebuild можно безопасно использовать для импорта хеш-таблицы, созданной старой версией модуля MoreLabels.Hashtbl, а затем сериализованной в постоянное хранилище. После десериализации примените MoreLabels.Hashtbl.rebuild, чтобы получить хеш-таблицу для текущей версии модуля MoreLabels.Hashtbl.

Since 4.12

type statistics = Hashtbl.statistics = {

`num_bindings : int;`	`(*`	Количество связываний в таблице. То же значение, что и возвращаемое `MoreLabels.Hashtbl.length`.	`*)`
`num_buckets : int;`	`(*`	Количество бакетов в таблице.	`*)`
`max_bucket_length : int;`	`(*`	Максимальное количество связываний на бакет.	`*)`
`bucket_histogram : int array;`	`(*`	Гистограмма размеров бакетов. Этот массив `histo` имеет длину `max_bucket_length + 1`. Значение `histo.(i)` представляет количество бакетов, размер которых равен `i`.	`*)`

}

Since 4.00

val stats : ('a, 'b) t -> statistics

Hashtbl.stats tbl возвращает статистику о таблице tbl: количество бакетов, размер наибольшего бакета, распределение бакетов по размеру.

Since 4.00

Хеш-таблицы и Последовательности

val to_seq : ('a, 'b) t -> ('a * 'b) Seq.t

Итерируется по всей таблице. Порядок, в котором связывания появляются в последовательности, не определён. Однако, если таблица содержит несколько связываний для одного ключа, они появляются в обратном порядке их ввода, то есть, последнее связывание появляется первым.

Поведение не определено, если хеш-таблица изменяется во время итерации.

Since 4.07

val to_seq_keys : ('a, 'b) t -> 'a Seq.t

То же, что и Seq.map fst (to_seq m)

Since 4.07

val to_seq_values : ('a, 'b) t -> 'b Seq.t

То же, что и Seq.map snd (to_seq m)

Since 4.07

val add_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit

Добавляет заданные связывания в таблицу, используя MoreLabels.Hashtbl.add

Since 4.07

val replace_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit

Добавляет заданные связывания в таблицу, используя MoreLabels.Hashtbl.replace

Since 4.07

val of_seq : ('a * 'b) Seq.t -> ('a, 'b) t

Создаёт таблицу из заданных связываний. Связывания добавляются в том же порядке, в котором они появляются в последовательности, используя MoreLabels.Hashtbl.replace_seq, что означает, что если у двух пар одинаковый ключ, то в таблице будет только последняя.

Since 4.07

Функторный интерфейс

Функторный интерфейс позволяет использовать определённые функции сравнения и хеширования, либо для повышения производительности/безопасности, либо потому что ключи не хешируются/сравниваются с полиморфными встроенными функциями.

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

        module IntHash =
          struct
            type t = int
            let equal i j = i=j
            let hash i = i land max_int
          end

        module IntHashtbl = Hashtbl.Make(IntHash)

        let h = IntHashtbl.create 17 in
        IntHashtbl.add h 12 "hello"

Это создаёт новый модуль IntHashtbl, с новым типом 'a IntHashtbl.t таблиц от int до 'a. В этом примере, h содержит string значения, поэтому его тип string IntHashtbl.t.

Обратите внимание, что новый тип 'a IntHashtbl.t не совместим с типом ('a,'b) Hashtbl.t универсального интерфейса. Например, Hashtbl.length h не будет проходить проверку типов, необходимо использовать IntHashtbl.length.

module type HashedType = sig .. end

Входная сигнатура функтора MoreLabels.Hashtbl.Make.

module type S = sig .. end

Выходная сигнатура функтора MoreLabels.Hashtbl.Make.

module Make: functor (H : HashedType) -> S 
    with type key = H.t
     and type 'a t = 'a Hashtbl.Make(H).t

Функтор, создающий реализацию структуры хеш-таблицы.

module type SeededHashedType = sig .. end

Входная сигнатура функтора MoreLabels.Hashtbl.MakeSeeded.

module type SeededS = sig .. end

Выходная сигнатура функтора MoreLabels.Hashtbl.MakeSeeded.

module MakeSeeded: functor (H : SeededHashedType) -> SeededS 
    with type key = H.t
     and type 'a t = 'a Hashtbl.MakeSeeded(H).t

Функтор, создающий реализацию структуры хеш-таблицы.

Полиморфные функции хеширования

val hash : 'a -> int

Hashtbl.hash x сопоставляет неотрицательное целое число любому значению любого типа. Гарантируется, что если x = y или Stdlib.compare x y = 0, то hash x = hash y. Более того, hash всегда завершается, даже на циклических структурах.

val seeded_hash : int -> 'a -> int

Вариант MoreLabels.Hashtbl.hash, дополнительно параметризованный целым числом-семенем.

Since 4.00

val hash_param : int -> int -> 'a -> int

Hashtbl.hash_param meaningful total x вычисляет хеш-значение для x, с теми же свойствами, что и для hash. Два дополнительных целых параметра meaningful и total обеспечивают более точный контроль над хешированием. Хеширование выполняет обход структуры x по принципу «ширина в глубину», слева направо, останавливаясь после обнаружения meaningful значимых узлов или total узлов (значимых или нет). Если total значение, указанное пользователем, превышает определённое значение, в настоящее время 256, то оно ограничено этим значением. Значимые узлы: целые числа; числа с плавающей запятой; строки; символы; булевы значения; и константы-конструкторы. Большие значения meaningful и total означают, что в вычислении конечного хеш-значения учитывается больше узлов, и поэтому вероятность коллизий уменьшается. Однако, хеширование занимает больше времени. Параметры meaningful и total управляют балансом между точностью и скоростью. По умолчанию, MoreLabels.Hashtbl.hash и MoreLabels.Hashtbl.seeded_hash принимают meaningful = 10 и total = 100.

val seeded_hash_param : int -> int -> int -> 'a -> int

Вариант MoreLabels.Hashtbl.hash_param, дополнительно параметризованный целым числом-семенем. Использование: Hashtbl.seeded_hash_param meaningful total seed x.

Since 4.00

Примеры

Базовый пример

      (* 0...99 *)
      let seq = Seq.ints 0 |> Seq.take 100

      (* build from Seq.t *)
      # let tbl =
          seq
          |> Seq.map (fun x -> x, string_of_int x)
          |> Hashtbl.of_seq
      val tbl : (int, string) Hashtbl.t = <abstr>

      # Hashtbl.length tbl
      - : int = 100

      # Hashtbl.find_opt tbl 32
      - : string option = Some "32"

      # Hashtbl.find_opt tbl 166
      - : string option = None

      # Hashtbl.replace tbl 166 "one six six"
      - : unit = ()

      # Hashtbl.find_opt tbl 166
      - : string option = Some "one six six"

      # Hashtbl.length tbl
      - : int = 101

Подсчёт элементов

Учитывая последовательность элементов (здесь, Seq.t), мы хотим подсчитать, сколько раз каждый уникальный элемент встречается в последовательности. Простой способ сделать это, предполагая, что элементы сравнимы и хешируемы, — использовать хеш-таблицу, которая сопоставляет элементы их количеству появлений.

Здесь мы иллюстрируем этот принцип, используя последовательность (ascii) символов (тип char). Мы используем пользовательскую Char_tbl специализированную для char.

      # module Char_tbl = Hashtbl.Make(struct
          type t = char
          let equal = Char.equal
          let hash = Hashtbl.hash
        end)

      (*  count distinct occurrences of chars in [seq] *)
      # let count_chars (seq : char Seq.t) : _ list =
          let counts = Char_tbl.create 16 in
          Seq.iter
            (fun c ->
              let count_c =
                Char_tbl.find_opt counts c
                |> Option.value ~default:0
              in
              Char_tbl.replace counts c (count_c + 1))
            seq;
          (* turn into a list *)
          Char_tbl.fold (fun c n l -> (c,n) :: l) counts []
            |> List.sort (fun (c1,_)(c2,_) -> Char.compare c1 c2)
      val count_chars : Char_tbl.key Seq.t -> (Char.t * int) list = <fun>

      (* basic seq from a string *)
      # let seq = String.to_seq "hello world, and all the camels in it!"
      val seq : char Seq.t = <fun>

      # count_chars seq
      - : (Char.t * int) list =
      [(' ', 7); ('!', 1); (',', 1); ('a', 3); ('c', 1); ('d', 2); ('e', 3);
       ('h', 2); ('i', 2); ('l', 6); ('m', 1); ('n', 2); ('o', 2); ('r', 1);
       ('s', 1); ('t', 2); ('w', 1)]

      (* "abcabcabc..." *)
      # let seq2 =
          Seq.cycle (String.to_seq "abc") |> Seq.take 31
      val seq2 : char Seq.t = <fun>

      # String.of_seq seq2
      - : String.t = "abcabcabcabcabcabcabcabcabcabca"

      # count_chars seq2
      - : (Char.t * int) list = [('a', 11); ('b', 10); ('c', 10)]