Re: Red-black trees?
- From: Mark Wooding <mdw@xxxxxxxxxxxxxxxx>
- Date: Wed, 12 Nov 2008 17:24:42 +0000 (UTC)
robin <robin_v@xxxxxxxxxxx> wrote:
A hash table is a table, and therefore is of fixed size, and would be
unsuitable for such a task.
You've missed the memo about extending hash tables. If you get it
right, the work done to grow the table leaves you with O(1) insertion
Well, you would, if hash tables were O(1) in the first place.
Unfortunately, they aren't: remember that the relationship has to hold
as n (the number of items in the table) gets arbitrarily large, in which
case simply computing an index requires one to produce O(log n) bits,
even if you don't worry too much about how the computation happens. All
of which really does more to show the value of asymptotic complexity
statements than it does to explain the performance of hash tables, but
there you go.
- Prev by Date: Re: Beginning Learning Computer Programming
- Next by Date: Re: "Foreign" programmers' thoughts on American politics?
- Previous by thread: Re: Beginning Learning Computer Programming
- Next by thread: Re: Red-black trees?