Re: fast dictionary search algorithm

From: CBFalconer (cbfalconer_at_yahoo.com)
Date: 02/10/04 

Date: Tue, 10 Feb 2004 08:16:34 GMT

Paul Hsieh wrote:
> prashanthellina@gmx.net (Prashanth Ellina) wrote:
> >
... snip ...
> >
> > I have considered hashing and multiple level hashing as an option
> > but am not sure about the hash function. People tell me it is
> > difficult to avoid collisions. Have tried binary search, however
> > need something faster.
>
> Collisions are not fatal. And they aren't necessarily slow if you
> don't go the route of rehashing. For example, for all the entries
> that land on a given hash index, simply place them all into a sorted
> binary, and use binary search on them from there. In this way you get
> the benefit of the massive narrowing of your search via hashing, and
> the O(log(n)) guarantee of the binary tree at the same time.

Nor are they slow if rehashed. A reasonable system will never
need more than two hashes total, and will be O(1) for all
searches. 

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

Relevant Pages

  • 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)
  • 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 ... hashing, because someone who wanted hashing would just use the Hashtable ... Hashing and sorting are so fundamentally different ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Choice of data structures
    ... > probably use some generic sequence data type, ... I'm wondering if you need the hashing. ... random-access operation, then sure, hashing is necessary. ... You could store the time in each piece of data, then use binary search ...
    (comp.lang.lisp)
  • Re: fast dictionary search algorithm
    ... > I have a text file with words and meanings. ... The algorithm ... > I have considered hashing and multiple level hashing as an option ... and use binary search on them from there. ...
    (comp.programming)