List.assoc 的 OCaml 复杂度
OCaml complexity of List.assoc
在 OCaml 的 List 模块中，如何实现：val assoc : 'a -> ('a * 'b) list -> 'b 以及（因此）这个操作的复杂度是多少？幕后是否隐藏了hashtbl？
可在此处在线获取代码：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
如您所见，它是作为对列表的线性搜索实现的。
在 OCaml 的 List 模块中，如何实现：val assoc : 'a -> ('a * 'b) list -> 'b 以及（因此）这个操作的复杂度是多少？幕后是否隐藏了hashtbl？
可在此处在线获取代码：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
如您所见，它是作为对列表的线性搜索实现的。