List.assoc 的 OCaml 复杂性

Question

在 OCaml 的 List 模块中，val assoc : 'a -> ('a * 'b) list -> 'b 是如何实现的，(因此)它的复杂度是多少手术 ？幕后是否隐藏了 hashtbl？

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

如您所见，它是作为对列表的线性搜索实现的。