Равенство в хеш-таблицах Ocaml - PullRequest
Новая
       19

Равенство в хеш-таблицах Ocaml

6 голосов
/ 23 января 2012

Есть ли в 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.Это возможно?

Ответы [ 2 ]

11 голосов
/ 23 января 2012

Вы можете использовать пользовательские хеш-таблицы: 

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

И затем использовать H вместо Hashtbl в своем коде.

4 голосов
/ 23 января 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);;
...