Re: Grace and Maps (was Re: Development process in the Ada community)

[Simon Wright <simon@pushface.org>]

Darren New <dnew@san.rr.com> writes:

> I'm not sure why a hashtable wouldn't have a worst-case time of O(N)
> (if all the elements hash to the same value) or how you'd guarantee
> any particular limit on execution time of inserting a value (for
> example, in the same case). In contrast, a red-black tree is *never*
> going to see O(N) time in any operation.

I would have expected a hash table to have O(N) anyway, at least for
searching; it's just that the multiplier is reduced by the number of
hash buckets.

This is certainly the case for the BCs, now you all come to mention
it! Insertion is constant time, though.

Are red-black trees much better than AVL trees (which is what you get
in the BCs)?