Equality in Ocaml hashtables

Question

Esistono hashtables in Ocaml che utilizzano == anziché = durante il test per l'uguaglianza di chiavi? Per esempio:

# 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 

Vorrei una tabella hash che può distinguere tra a e b. È possibile?

Answer 1

È possibile utilizzare hashtables personalizzati:

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

e quindi utilizzare H invece di Hashtbl nel codice.

Answer 2

La soluzione nelle risposte di Thomas e Cago è funzionalmente corretta. Un problema che potrebbe causare problemi se si utilizza la propria soluzione così com'è è che si otterranno più collisioni del previsto se si hanno molte chiavi uguali per (=) e diverse per (==). Infatti, tutte le chiavi uguali per (=) hanno lo stesso hash per Hashtbl.hash e finiscono nello stesso bucket, dove sono riconosciute come diverse (dal momento che hai chiesto di utilizzare (==) come funzione di uguaglianza) e creare associazioni diverse. Nei casi peggiori, la tabella hash si comporterà con la stessa complessità di una lista di associazioni (che, a proposito, è un'altra struttura dati che potresti usare, e quindi non dovresti preoccuparti di fornire una funzione hash).

Se è possibile accettare la chiave di un valore che cambia occasionalmente (e quindi il valore è impossibile da recuperare dalla tabella hash, poiché l'associazione è quindi nel bucket errato), è possibile utilizzare la seguente funzione di basso livello come hash:

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

Implementato in C come:

#include "caml/mlvalues.h" 

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

Si potrebbe quindi utilizzare:

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