MOO-cows Mailing List Archive
[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]
Re: hash & balanced trees
>>>>> 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:
References:
Home |
Subject Index |
Thread Index