模組 Hashtbl

module Hashtbl: sig .. end

雜湊表與雜湊函式。

雜湊表是經過雜湊處理的關聯表，支援就地修改。由於雜湊表上的大多數操作都會修改輸入，因此它們更常在命令式程式碼中使用。查詢與鍵相關聯的值（請參閱 Hashtbl.find、Hashtbl.find_opt）通常非常快速，通常比在 Map 中等效的查詢更快。

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

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

多型 Hashtbl.t 雜湊表在較簡單的情況或互動式環境中很有用。它使用 OCaml 運行時中定義的多型 Hashtbl.hash 函數（在撰寫本文時，它是 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）在儲存桶之間分發金鑰。因此，金鑰之間的碰撞是確定性發生的。在面向 Web 的應用程式或其他對安全性敏感的應用程式中，惡意使用者可能會利用確定性的碰撞模式來建立阻斷服務攻擊：攻擊者會發送精心設計的輸入，以在表格中建立許多碰撞，從而降低應用程式的速度。

使用 ~random 設定為 true 建立的雜湊表使用種子雜湊函數 Hashtbl.seeded_hash，該種子是在雜湊表建立時隨機選擇的。實際上，使用的雜湊函數是從 2^{30} 個不同的雜湊函數中隨機選擇的。所有這些雜湊函數都具有不同的碰撞模式，從而使上述阻斷服務攻擊無效。但是，由於隨機化，使用 Hashtbl.fold 或 Hashtbl.iter 列舉雜湊表的所有元素不再是確定性的：元素在程式的不同執行中會以不同的順序列舉。

如果未給定 ~random 參數，則預設情況下會在非隨機模式下建立雜湊表。可以透過呼叫 Hashtbl.randomize 以程式方式變更此預設值，或者在 OCAMLRUNPARAM 環境變數中設定 R 旗標。

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 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 可選參數。也可以透過在 OCAMLRUNPARAM 環境變數中設定 R 參數來達到相同的效果。

建議需要保護自己免受 Hashtbl.create 中所述阻斷服務攻擊的應用程式或 Web 架構在建立任何網域之前，在初始化時呼叫 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），我們想要計算每個不同的元素在序列中出現的次數。一個簡單的方法是，假設元素是可比較和可雜湊的，使用將元素對應到它們出現次數的雜湊表。

在這裡，我們使用字元 (類型 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)]