|
|
 | | From: | CBFalconer | | Subject: | Re: Hash-table versus B-Tree | | Date: | Tue, 07 Dec 2004 20:33:02 GMT |
|
|
 | "kar1107@gmail.com" wrote:
>
> I looked in the webpage for hashlib. I am looking for description
> of the algorithm (I see mostly implementation/usage docs in the
> .zip file).
>
> Can you describe your algorithm?
>
> By O(1) you mean best/common case, right? AFAIK there isn't any
> datastructure that can do better than O(log n) search (ie
> theoretically you need atleast O(log n) comparisons to zero-in
> on the item being searched).
One copy of your article will suffice!
It is a completely ordinary rehash method, of which there are many
descriptions in the literature. The expected performance is O(1),
while worst case performance (with poor hash functions) can be as
bad as O(n). One of the test cases checks that the system survives
such mistreatment.
What makes my system unique, IMO, is that I have combined it with
self adjustment for table size, convenient ways to scan the
complete table content, and the ability to delete entries. In
addition the code is re-entrant so that many tables may be
maintained by the same code. It was an outgrowth of a test bed for
hash functions. It showed up the common fault in malloc packages
where free is O(n) in the number of extant blocks, which in turn
triggered my development of nmalloc for DJGPP, without this fault.
--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
USE worldnet address!
|
|
|
