Модуль MoreLabels.Hashtbl

module Hashtbl: sig .. end

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

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

Несинхронизированные обращения

Несинхронизированные обращения к хэш-таблице могут привести к недопустимому состоянию хэш-таблицы. Таким образом, одновременные обращения к хэш-таблицам должны быть синхронизированы (например, с помощью 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.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, в tbl добавляется связывание key с data. Это функционально эквивалентно 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.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 во время итерации.

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.

С версии 4.00.0

val is_randomized : unit -> bool

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

С версии 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