Premier doublon

let premier_doublon l =
  let vus = Hashtbl.create 16 in
  let rec parcours l =
    match l with
    | [] -> None
    | x :: reste ->
        if Hashtbl.mem vus x then Some x
        else begin
          Hashtbl.add vus x true;
          parcours reste
        end
  in
  parcours l

La table vus joue le rôle d'un ensemble : on y note chaque élément déjà vu (la valeur true importe peu, seule compte la présence de la clé). Dès qu'un élément est déjà présent, c'est le premier doublon. Coût $\Theta (n)$ en moyenne, contre $\Theta (n^2)$ avec une recherche par liste.