Модуль MoreLabels.Hashtbl

module Hashtbl: sig .. end

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

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

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

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

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

См. раздел с примерами.

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

Несинхронизированный доступ к хеш-таблице может привести к недопустимому состоянию хеш-таблицы. Поэтому одновременный доступ к хеш-таблице необходимо синхронизировать (например, с помощью 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 — лишь начальная оценка. Если 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 параметр ~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 -> key:'a -> data:'b -> unit

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

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

Если требуется классическое поведение с заменой элементов, см. MoreLabels.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

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

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

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

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

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

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

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

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

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

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

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

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

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`.	`*)`

}

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

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

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

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

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

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

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

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

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

Начиная с версии 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 определяют компромисс между точностью и скоростью. В качестве значений по умолчанию функции 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.

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