Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Looking for fast string hash searching

Reply
Thread Tools

Looking for fast string hash searching

 
 
Thomas Christmann
Guest
Posts: n/a
 
      05-13-2004
Hi!

First let me apologize for asking this question when there are so many answers
to it on Google, but most of them are really contradicting, and making what I
want to do very performant is crucial to my project. So, here's what I have:

My C programm connects to a database and gets ca. 50-100K domain name/file path
pairs. Those pairs have to be cached by my application. Building the cache may
take a second or two, but retrieving from it must be very fast. Since I get
the data from a database, I'd be able to order by domain name (which will be
my key, and is guaranteed to be unique), so I thought something like a btree
search for strings might be a good idea. I only have to look up by domain name
from the hash, searching by path is not permitted.
Since I'm far from being an expert on the subject of hashing and search
algorithms, your opinion on how to make this fast is humbly requested

TIA,

Thomas
 
Reply With Quote
 
 
 
 
Stephen L.
Guest
Posts: n/a
 
      05-13-2004
Thomas Christmann wrote:
>
> Hi!
>
> First let me apologize for asking this question when there are so many answers
> to it on Google, but most of them are really contradicting, and making what I
> want to do very performant is crucial to my project. So, here's what I have:
>
> My C programm connects to a database and gets ca. 50-100K domain name/file path
> pairs. Those pairs have to be cached by my application. Building the cache may
> take a second or two, but retrieving from it must be very fast. Since I get
> the data from a database, I'd be able to order by domain name (which will be
> my key, and is guaranteed to be unique), so I thought something like a btree
> search for strings might be a good idea. I only have to look up by domain name
> from the hash, searching by path is not permitted.
> Since I'm far from being an expert on the subject of hashing and search
> algorithms, your opinion on how to make this fast is humbly requested
>
> TIA,
>
> Thomas


This isn't _really_ a `C' question...

If the distribution of "domain" names
is pretty even across the alphabet,
then you could use the 1st letter of
the name as an index to an array of
"pointers" to name/path pairs that
you can `bsearch()'. 100,000 entries
isn't that much now-a-days, and
dividing by 26 (for about 4,000 entries)
should provide a very fast lookup.


Stephen
 
Reply With Quote
 
 
 
 
Thomas Christmann
Guest
Posts: n/a
 
      05-13-2004
> This isn't _really_ a `C' question...

I know, I know, and I'm sorry to post here, but you guys usually
help me very much (not knowingly, I suppose) with your posts. Also,
there isn't really an alt.hash.maps

> If the distribution of "domain" names
> is pretty even across the alphabet,
> then you could use the 1st letter of
> the name as an index to an array of
> "pointers" to name/path pairs that
> you can `bsearch()'. 100,000 entries
> isn't that much now-a-days, and
> dividing by 26 (for about 4,000 entries)
> should provide a very fast lookup.


Sounds good, I'll give that a try.

Thanks,

Thomas
 
Reply With Quote
 
August Derleth
Guest
Posts: n/a
 
      05-14-2004
On Thu, 13 May 2004 07:47:36 -0700, Thomas Christmann wrote:

>> This isn't _really_ a `C' question...

>
> I know, I know, and I'm sorry to post here, but you guys usually
> help me very much (not knowingly, I suppose) with your posts. Also,
> there isn't really an alt.hash.maps


comp.programming or something like that (I've forgotten the exact name)
handles language-agnostic algorithm questions. You should get the
algorithm ironed out first before trying a specific implementation anyway.

--
yvoregnevna gjragl-guerr gjb-gubhfnaq guerr ng lnubb qbg pbz
To email me, rot13 and convert spelled-out numbers to numeric form.
"Makes hackers smile" makes hackers smile.

 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      05-16-2004
"Stephen L." <(E-Mail Removed)> writes:

|> Thomas Christmann wrote:

|> > First let me apologize for asking this question when there are so
|> > many answers to it on Google, but most of them are really
|> > contradicting, and making what I want to do very performant is
|> > crucial to my project. So, here's what I have:

|> > My C programm connects to a database and gets ca. 50-100K domain
|> > name/file path pairs. Those pairs have to be cached by my
|> > application. Building the cache may take a second or two, but
|> > retrieving from it must be very fast. Since I get the data from a
|> > database, I'd be able to order by domain name (which will be my
|> > key, and is guaranteed to be unique), so I thought something like
|> > a btree search for strings might be a good idea. I only have to
|> > look up by domain name from the hash, searching by path is not
|> > permitted. Since I'm far from being an expert on the subject of
|> > hashing and search algorithms, your opinion on how to make this
|> > fast is humbly requested

|> If the distribution of "domain" names
|> is pretty even across the alphabet,
|> then you could use the 1st letter of
|> the name as an index to an array of
|> "pointers" to name/path pairs that
|> you can `bsearch()'.

They aren't. I'll bet that well over half of all domains start with
"www.". Also, the alphabet for domain names isn't limited to letters.

I think that for this application, nothing will beat a good hash code.
The trick is, of course, to avoid a bad one; for some reason, URL's
seem to be very sensitive to bad hash codes. A Google search for FNV
hashing should turn up what you need -- if performance of the hash
itself turns out to be an issue, and your hardware doesn't handle
arbitrary multiplies very rapidly, I've also used Mersenne prime based
hash codes in the past with good results. (The basic algorithm is the
same as for FNV hashing, but the multiplier is a Mersenne prime, which
can easily be calculated with a shift and a subtraction.)

--
James Kanze
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash of hash of hash of hash in c++ rp C++ 1 11-10-2011 04:45 PM
Hash#select returns an array but Hash#reject returns a hash... Srijayanth Sridhar Ruby 19 07-02-2008 12:49 PM
Google search result to be URL-limited when searching site, but notwhen searching Web stumblng.tumblr Javascript 1 02-04-2008 09:01 AM
Searching for a very fast string parser |MKSM| Ruby 5 03-09-2006 02:45 PM
Searching an example for a defined hash value of a nonexisting hash key Ralf Baerwaldt Perl Misc 1 07-20-2004 03:05 PM



Advertisments