Sự bình đẳng trong các thẻ bắt buộc Ocaml

Question

Có các hashtables trong Ocaml sử dụng == thay vì = khi kiểm tra tính bình đẳng của các khóa không? Ví dụ:

# type foo = A of int;; 
# let a = A(1);; 
# let b = A(1);; 
# a == b;; 
- : bool = false 
# a = b;; 
- : bool = true 
# let h = Hashtbl.create 8;; 
# Hashtbl.add h a 1;; 
# Hashtbl.add h b 2;; 
# Hashtbl.find h a;; 
- : int = 2 
# Hashtbl.find h b;; 
- : int = 2 

Tôi muốn một Hashtable có thể phân biệt giữa a và b. Điều đó có thể không?

Answer 1

Bạn có thể sử dụng hashtables tùy chỉnh:

module H = Hashtbl.Make(struct 
    type t = foo 
    let equal = (==) 
    let hash = Hashtbl.hash 
end) 

Và sau đó sử dụng H thay vì Hashtbl trong mã của bạn.

Answer 2

Giải pháp trong câu trả lời của Thomas và cago là chính xác về mặt chức năng. Một vấn đề có thể gây rắc rối cho bạn nếu bạn sử dụng giải pháp của họ như là bạn sẽ nhận được nhiều va chạm hơn dự kiến ​​nếu bạn băm nhiều khóa bằng nhau cho (=) và khác nhau cho (==). Thật vậy, tất cả các khóa bằng nhau cho (=) có cùng giá trị băm cho Hashtbl.hash và kết thúc trong cùng một nhóm, nơi chúng được nhận dạng là khác nhau (vì bạn đã yêu cầu (==) để sử dụng làm hàm bình đẳng) và tạo các ràng buộc khác nhau. Trong trường hợp xấu nhất, bảng băm sẽ hoạt động với độ phức tạp tương tự như danh sách liên kết (mà, bằng cách này, là một cấu trúc dữ liệu khác mà bạn có thể sử dụng, và sau đó bạn sẽ không phải lo lắng về việc cung cấp hàm băm).

Nếu bạn có thể chấp nhận khóa của giá trị thay đổi đôi khi (và do đó giá trị không thể truy xuất từ ​​bảng băm, do ràng buộc trong nhóm không đúng), bạn có thể sử dụng hàm mức thấp sau như băm:

external address_of_value: 'a -> int = "address_of_value" 

thực hiện trong C như:

#include "caml/mlvalues.h" 

value address_of_value(value v) 
{ 
    return (Val_long(((unsigned long)v)/sizeof(long))); 
} 

sau đó bạn sẽ sử dụng:

module H = Hashtbl.Make(struct 
    type t = foo 
    let equal = (==) 
    let hash = address_of_value 
end);;