SML中哈希表的查找函数

Question

我被指派在SML中为这个哈希表数据类型编写一个查找函数；

datatype 'a ht = table of (int * ('a list)) list;

如果表为空和/或表中不存在键，则返回nil。功能应该是这个

val lookup = fn : int -> 'a ht -> 'a list

但我不知道如何在哈希表的每个bucket中查找，也不知道如何显示键的bucket的值。我希望能在使用哪种算法方面得到一些帮助。

例如，函数应该这样工作；

-lookup 3 (table [(1, [2,3]), (2, [3,4,5]), (3, [4])]);
  val it = [4] : int list
-lookup 4 (table [(1, [2,3]), (2, [3,4,5]), (3, [4])]);
  val it = [] : int list

Answer 1

您的哈希表是一个对列表。

有趣的查找n表=。。。首先，您需要一个函数来沿着配对列表向下移动到第n个位置。你可以用之类的东西

case table of
table [] => nil
|table ls => lookup n-1 table (tl ls)

第二步，当您的查找函数的第二个参数在递归中减少到1时，获取值（对的#2）或通过模式匹配，假设您的键按照示例中的顺序排列。然后返回。