Version franēaise
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Map efficiency?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-11-04 (09:26)
From: Jean-Christophe Filliatre <Jean-Christophe.Filliatre@l...>
Subject: Re: [Caml-list] Map efficiency?

Dustin Sallings writes:
 > 	Should I expect Hashtbl to be more efficient than Map with the same 
 > key type?  I'm taking a small performance hit in a log processing app 
 > after turning a Hashtbl into a Map.

Hashtbl.add runs in  O(1) and Hashtbl.find can be  so (or almost) when
the hash function is good enough.

Map.add and Map.find are always in O(ln n) where n is the total number
of keys.

The main interest of maps wrt  hash tables is to be persistent (in the
sense of Okasaki's book, not of the PERSIL library).

 > 	Also, is there a particular reason Map is so, um, inaccessible to 
 > beginners?  Hashtbl's generic interface is much more inviting than 
 > Map's functorial-only interface, especially to those not terribly 
 > familiar with the module system.

Just   copy  the  body   of  Map.Make   and  replace  by  and you'll get  a polymorphic  version of  Map, as
easy to use as Hashtbl's generic interface.

But I agree: it's a shame ocaml does not provide it.

Jean-Christophe Filliātre (

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: