Существуют ли в Ocaml хеш-таблицы, которые используют == вместо = при проверке на равенство ключей? Например:
# 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
Мне нужна хеш-таблица, которая может различать a и b. Это возможно?
Вы можете использовать пользовательские хэш-таблицы:
module H = Hashtbl.Make(struct
type t = foo
let equal = (==)
let hash = Hashtbl.hash
end)
А затем используйте H вместо Hashtbl в своем коде.
end ключевого слова stuct.
- person nlucaroni; 23.01.2012
Решение в ответах Томаса и Каго функционально правильное. Одна проблема, которая может беспокоить вас, если вы используете их решение как есть, заключается в том, что вы получите больше коллизий, чем ожидалось, если вы хэшируете много ключей, одинаковых для (=) и разных для (==). Действительно, все ключи, которые равны для (=), имеют одинаковый хэш для Hashtbl.hash и попадают в одно и то же ведро, где они распознаются как разные (поскольку вы просили использовать (==) в качестве функции равенства) и создают разные привязки. В худшем случае хэш-таблица будет вести себя так же сложно, как и список ассоциаций (который, кстати, является еще одной структурой данных, которую вы могли бы использовать, и тогда вам не пришлось бы беспокоиться о предоставлении хеш-функции). ).
Если вы можете допустить, что ключ значения время от времени меняется (и, следовательно, значение невозможно получить из хеш-таблицы, поскольку тогда привязка находится в неправильном сегменте), вы можете использовать следующую низкоуровневую функцию в качестве хэша:
external address_of_value: 'a -> int = "address_of_value"
Реализовано на C как:
#include "caml/mlvalues.h"
value address_of_value(value v)
{
return (Val_long(((unsigned long)v)/sizeof(long)));
}
Затем вы должны использовать:
module H = Hashtbl.Make(struct
type t = foo
let equal = (==)
let hash = address_of_value
end);;
let test x = let t = Array.make 1 x in x == t.(0) ;; test 1.0 ;;вычисляетfalse. Многопоточный сборщик мусора для Caml, который существует только на бумаге, также может дублировать неизменяемые значения. - person Pascal Cuoq schedule 23.01.2012