OCaml List.assoc的复杂性

Question

在OCaml的List模块中,如何:val assoc : 'a -> ('a * 'b) list -> 'b实现和(因此)此操作的复杂性是什么？幕后隐藏着一个哈希？

Answer 1

该代码可在线获取:https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml#L180-L182

let rec assoc x = function
    [] -> raise Not_found
  | (a,b)::l -> if compare a x = 0 then b else assoc x l

正如您所看到的,它是作为列表上的线性搜索实现的.