From: Paul Lutus <nospam@...>
Date: 2006-09-08T10:07:10+09:00
Subject: Re: Faster datastructure for lookups wanted

m94asr@gmail.com wrote:

> Hi all,
> 
>   maybe somebody can recommend me the right datastructure or
> any other advice would be a big help.
> 
> My code spends most of its execution time doing lookups from
> a hashtable with about 1M keys. The keys are strings and the values
> are arrays of integers. Most of the time only of length 1.
> 
> I do not care  how long the construction of the datastructure takes,
> but the lookup should be as fast as possible.

Any way to segment the data? IOW are 1*10^6 keys really needed in the same
hash? A multi-tiered hash might save a lot of lookup time if the data can
be broken into groups smaller than 1*10^6.

Example. If the strings are consistent about content, you could break the
search into 26 (or 52) sections by simply hashing the first letter of the
key strings, then hashing on the remainder of each string in the second
tier.

-- 
Paul Lutus
http://www.arachnoid.com