Модуль Hashtbl

module Hashtbl: sig .. end

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

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

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

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

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

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

Предупреждение 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 параметр ~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 -> 'a -> 'b -> unit

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

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

Если вам нужно классическое поведение замены элементов, см. 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 -> 'a -> 'b -> unit

Hashtbl.replace tbl key data заменяет текущую привязку key в tbl привязкой key к data. Если key не привязано в tbl, привязка key к data добавляется в tbl.

Это функционально эквивалентно 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

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

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

Обратите внимание, что после вызова Hashtbl.randomize(), нет способа вернуться к поведению по умолчанию (без случайности) 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

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

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

Since 4.12

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

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

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

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