Re: Red-black trees?

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
times (amortized).

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.

-- [mdw]
.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... preimage resistant hash function accepting a graph as ... exchanging any vertices leaves the hash ... implying that computing and comparing two such ... width w, supposed collision and preimage resistant, ...
    (sci.crypt)
  • Re: code snippet
    ... Quite possibly, but it also has more overhead, and for some sizes of lists, ... computing the hash is more expensive than the entire search anyway. ...
    (comp.lang.c)
  • Re: Red-black trees?
    ... You've missed the memo about extending hash tables. ... Or Oinsertion times, which is worse than a balanced binary tree! ... case simply computing an index requires one to produce Obits, ...
    (comp.programming)
  • Re: [opensuse]
    ... Hash: SHA1 ... (on 64 bits machines). ... 64 bit computing wins significantly. ...
    (SuSE)
  • Re: [opensuse] Pango problem
    ... Hash: SHA1 ... my CCD camera and I keep getting this error message when I run it from the ... tables read any good computing book). ... Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org ...
    (SuSE)