Модуль MoreLabels.Hashtbl

module Hashtbl: sig .. end

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

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

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

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.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 -> key:'a -> data:'b -> unit

Hashtbl.add tbl ~key ~data добавляет привязку key к data в таблице tbl. Предыдущие привязки для key не удаляются, а просто скрываются. То есть после выполнения MoreLabels.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 -> 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 также применимы.

Since 4.03.0

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

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

Порядок, в котором привязки передаются в f, не определён. Однако, если таблица содержит несколько привязок для одного ключа, они передаются в 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.0

val is_randomized : unit -> bool

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

Since 4.03.0

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

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

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