模組 MoreLabels.Hashtbl

module Hashtbl: sig .. end

---

雜湊表與雜湊函數。

雜湊表是雜湊關聯表，具有原地修改的功能。由於對雜湊表的大多數操作都會修改其輸入，因此它們更常在命令式程式碼中使用。查找與鍵關聯的值（請參閱 MoreLabels.Hashtbl.find、MoreLabels.Hashtbl.find_opt）通常非常快，通常比在 MoreLabels.Map 中進行等效查找更快。

當效能或彈性是關鍵時，可以使用函子 MoreLabels.Hashtbl.Make 和 MoreLabels.Hashtbl.MakeSeeded。使用者為鍵類型提供自訂的相等和雜湊函數，並獲得此特定鍵類型的自訂雜湊表類型。

警告：雜湊表的好壞取決於雜湊函數。一個不好的雜湊函數會將表變成退化的關聯列表，導致線性時間查找而不是常數時間查找。

多型 MoreLabels.Hashtbl.t 雜湊表在較簡單的情況或互動式環境中很有用。它使用 OCaml 執行階段中定義的多型 MoreLabels.Hashtbl.hash 函數（在撰寫本文時，它是 SipHash），以及多型相等 (=)。

請參閱範例章節。

非同步存取

非同步存取雜湊表可能會導致雜湊表狀態無效。因此，必須同步對雜湊表的並行存取（例如使用 Mutex.t）。

通用介面

type ('a, 'b) t = ('a, 'b) Hashtbl.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 -> key:'a -> data:'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 -> key:'a -> data:'b -> unit

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

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

val fold : f:(key:'a -> data:'b -> 'acc -> 'acc) ->
       ('a, 'b) t -> init:'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 = 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 的儲存桶數。	*)

}

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
     and type 'a t = 'a Hashtbl.Make(H).t

module type SeededHashedType = sig .. end

module type SeededS = sig .. end

module MakeSeeded: 
functor (H : SeededHashedType) -> SeededS 
    with type key = H.t
     and type 'a t = 'a Hashtbl.MakeSeeded(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)]