Yaron Minsky wrote:
> For just this reason, the hashtables in Core have been reimplemented to use an
> AVL tree in the buckets.  That way, even when you have pathological 
> collisions,
> you degrade gracefully to O(log n) per operation, instead of O(n), where n is
> the number of keys in the hashtable.

I'm resisting the temptation to hack-it-and-see: does your implementation do 
anything clever to maintain Hashtbl's O(1) insertion time (e.g. Hashtbl.add 
updates a list and then the first call to Hashtbl.find or Hashtbl.mem "moves" 
any items from the list to the AVL). Or does doing that impact "general" 
performance too much?

In the POST web scenario (or processing HTTP request headers), for example, 
"degrading" Hashtbl.add from O(1) to O(log n) is only acceptable if you know 
that you'll query all the fields in the POST (which isn't necessarily true).


Caml-list mailing list.  Subscription management and archives:
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

Reply via email to