模块 Hashtbl

module Hashtbl: sig .. end

---

未同步访问

对哈希表的未同步访问可能导致哈希表状态无效。因此，必须同步对哈希表的并发访问（例如使用 Mutex.t）。

泛型接口

type (!'a, !'b) t 

val create : ?random:bool -> int -> ('a, 'b) t

val clear : ('a, 'b) t -> unit

val reset : ('a, 'b) t -> unit

val copy : ('a, 'b) t -> ('a, 'b) t

val add : ('a, 'b) t -> 'a -> 'b -> unit

val find : ('a, 'b) t -> 'a -> 'b

val find_opt : ('a, 'b) t -> 'a -> 'b option

val find_all : ('a, 'b) t -> 'a -> 'b list

val mem : ('a, 'b) t -> 'a -> bool

val remove : ('a, 'b) t -> 'a -> unit

val replace : ('a, 'b) t -> 'a -> 'b -> unit

val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit

val filter_map_inplace : ('a -> 'b -> 'b option) -> ('a, 'b) t -> unit

val fold : ('a -> 'b -> 'acc -> 'acc) -> ('a, 'b) t -> 'acc -> 'acc

val length : ('a, 'b) t -> int

val randomize : unit -> unit

val is_randomized : unit -> bool

val rebuild : ?random:bool -> ('a, 'b) t -> ('a, 'b) t

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 的桶的数量。	*)

}

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

哈希表和序列

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

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

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

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

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

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

函子接口

函子接口允许使用特定的比较和哈希函数，无论是出于性能/安全考虑，还是因为键无法使用多态内置函数进行哈希/比较。

例如，可能需要为整数键专门化一个表。

      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

module type S = sig .. end

module Make: 
functor (H : HashedType) -> S  with type key = H.t

module type SeededHashedType = sig .. end

module type SeededS = sig .. end

module MakeSeeded: 
functor (H : SeededHashedType) -> SeededS  with type key = H.t

多态哈希函数

val hash : 'a -> int

val seeded_hash : int -> 'a -> int

val hash_param : int -> int -> 'a -> int

val seeded_hash_param : int -> int -> int -> 'a -> int

示例

基本示例

    (* 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 专门定制的 Char_tbl。

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