Модуль Hashtbl

module Hashtbl: sig .. end

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

Хеш-таблицы — это хешированные таблицы ассоциаций с модификацией на месте.

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

Несинхронизированный доступ

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

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

type ('a, 'b) t

Тип хеш-таблиц от типа 'a до типа 'b.

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

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

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

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

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

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

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

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

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

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

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

С версии 4.00.0

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

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

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

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

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 -> 'a -> 'b -> unit

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

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

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

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

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

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

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

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

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

С версии 4.03.0

val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c

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

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

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

С версии 4.00.0

val is_randomized : unit -> bool

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

С версии 4.03.0

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

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

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

Since 4.12.0

type statistics = {

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

}

Since 4.00.0

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

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

Since 4.00.0

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

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

Добавляет заданные пары ключ-значение в таблицу, используя Hashtbl.add

Since 4.07

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

Добавляет заданные пары ключ-значение в таблицу, используя Hashtbl.replace

Since 4.07

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

Строит таблицу из заданных пар ключ-значение. Пары добавляются в том же порядке, в котором они появляются в последовательности, используя 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

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

module type S = sig .. end

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

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

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

module type SeededHashedType = sig .. end

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

module type SeededS = sig .. end

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

module MakeSeeded: functor (H : SeededHashedType) -> SeededS  with type key = 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

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

Since 4.00.0

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 управляют балансом между точностью и скоростью. По умолчанию Hashtbl.hash и Hashtbl.seeded_hash принимают meaningful = 10 и total = 100.

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

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

Since 4.00.0