Модуль 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 — лишь начальная оценка. Если n слишком мало или отрицательно, оно игнорируется и используется небольшой размер по умолчанию.

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

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

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

Если параметр ~random не задан, по умолчанию хеш-таблицы создаются в нерandomизированном режиме. Это значение по умолчанию можно изменить программно, вызвав 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 добавляет в таблицу tbl привязку key к data.

Предупреждение: предыдущие привязки для 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 find_and_remove : ('a, 'b) t -> 'a -> 'b option

То же, что и Hashtbl.remove, но возвращает предыдущую привязку, если она есть.

Начиная с версии 5.5

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 find_and_replace : ('a, 'b) t -> 'a -> 'b -> 'b option

То же, что и Hashtbl.replace, но возвращает предыдущую привязку, если она есть.

Начиная с версии 5.5

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.

Начиная с версии 4.00

val is_randomized : unit -> bool

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

Начиная с версии 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.

Начиная с версии 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`.	`*)`

}

Начиная с версии 4.00

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

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

Начиная с версии 4.00

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

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

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

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

Начиная с версии 4.07

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

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

Начиная с версии 4.07

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

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

Начиная с версии 4.07

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

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

Начиная с версии 4.07

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

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

Начиная с версии 4.07

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

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

Начиная с версии 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, дополнительно параметризованный целочисленным начальным значением.

Начиная с версии 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.

Начиная с версии 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)]