Even discounting hash collisions, we could have a quarrel about whether
it should have been O(key length) where the key length is not considered
constant.
Very true. I misread his question as "complexity of hash value lookup". If
you're including computing the hash itself then that dominates (both
asymptotically and as a constant).
A typical hash function must traverse the entire key even
when searching an empty table,
Hash functions (in my experience) typically terminate after a finite number
of atomic operations, so the complexity is not related to the size of the
key but, rather, just to the bounded length of this computation, i.e. O(m).
so the key length affects the lookup time
differently than for e.g. binary search. (I have no idea what the
equivalent formula is for binary search.)
If your binary search uses structural comparison between keys then it is
O(key_size log n).
Re: RosAsm jut got a 3X Speedup !!! ... > CheckSum64, PointerToFamilyList, ChainPointer ... It does *not* distribute the keys well throughout the hash table. ... suspect that you're using a linear search to resolve collisions.... but a simple little binary search would work great. ... (alt.lang.asm)
Re: fast dictionary search algorithm ... >> I have a text file with words and meanings.... >> option but am not sure about the hash function.... > If you had all the entries in a decently-balanced binary search... I would expect total storage to approximate 400,000 bytes for the ... (comp.programming)
Re: Need quick lookup like Hashtable, but dont need to store value ... The complexity to get an entry from a hashtable that doesn't have ... argument when I add the string keys to it. ... Using an ArrayList and binary search is slower than a Hashtable for ... lookups, and much, much slower for inserts. ... (microsoft.public.dotnet.framework)
Re: Adding a unique user name in a file ... > sam wrote: ... >>Is there any perl module I can use to read in a list of user names ... >>from a file and do a binary search on the list base on the user name, ... If you read the user names into a hash then ... (comp.lang.perl.misc)
Re: How to best extract a list of identical keys in a sorted ArrayList with BinarySearch ? ... where that entry contains all of the items that match that key. ... If the indexer on key has to do a binary search then ... I presume that SortedList doesn't do hashing, because someone who wanted hashing would just use the Hashtable class instead, or possibly would use the two class together to achieve hashing with sorting. ... Even if you assume that the binary search is slower than a lookup by hash value, it's not going to be *much* slower. ... (microsoft.public.dotnet.languages.csharp)
