[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

# Re: hash & balanced trees

- Date: Mon, 7 Jul 1997 11:29:54 -0500
- From:
- CC: janus@cam.org, moo-cows@the-b.org
- In-reply-to: <Pine.SOL.3.91.970707060419.16222B-100000@piaf> (message fromMichael Brundage on Mon, 7 Jul 1997 06:12:16 -0700 (PDT))

    >>>>>  On Tue, 1 Jul 1997, Richard Godard wrote:

        >> Beside be carefull with the O() there are some constants that
        >> disapears and they can't always be neglected... beside in
        >> theory hash table have O(1) search/delete/add/etc., in
        >> practice... :) :) :)
        >>
        >> Welcome to the marvelous world of data structures and
        >> algorithms :)

    Actually, hashing takes time that depends on how full the has table
    is, as this determined the probablity of collision.  The timing is
    also affected by the collision resolution strategy.  For an open hash,
    where the initial probe is done by computing the index based on the
    key and subsequent probes are performed by some linear function, the
    table performs with an average of less than 2 probes until the table
    gets about 70% full.  (See knuth "sorting and searching" for full
    derivation.)  After that, performance degrades rapidly.  When the
    table is nearly full, the search is no better that a simple exhaustive
    list search.

    It is interesting to observe that the performance of ethernet networks
    follows the same saturation model, since the ethernet is essentially
    hashing over time instead of index space.

    --
    --------  "And there came a writing to him from Elijah"  [2Ch 21:12]  --------
    Robert Jay Brown III  rj@eli.wariat.org  http://eli.wariat.org  1 847 705-0424
    Elijah Laboratories Inc.;  37 South Greenwood Avenue;  Palatine, IL 60067-6328
    -----  M o d e l i n g   t h e   M e t h o d s   o f   t h e   M i n d  ------

Follow-Ups:

- Re: hash & balanced trees

- From: Charles Victor Bancroft <bancroft@america.net>

References:

- re:hash & balanced trees

- From: Michael Brundage <brundage@piaf.ipac.caltech.edu>

- Prev by Subject: re:hash & balanced trees
- Next by Subject: Re: hash & balanced trees
- Prev by thread: re:hash & balanced trees
- Next by thread: Re: hash & balanced trees
- Index(es):
  - Subject
  - Thread

Home | Subject Index | Thread Index