ISO recommendations for hash table lib

  • Permalink
  • submit to reddit
  • Email
  • Follow




Can someone recommend a decent hash table library?  I know about
the functions in search.h (hsearch, etc.), but I need to be able
to have multiple hash tables simultaneously, so this is out.

TIA!

kynn

P.S.  Yes, I know I can ask "The Google" for links to "hash tables
in C", but rather than links, what I'm looking for are recommendations
from satisfied (and knowledgeable) customers.
0
Reply no.email5 (314) 6/12/2009 4:23:30 PM

See related articles to this posting


In article <h0tve2$drs$1@reader1.panix.com>, kj  <no.email@please.post> wrote:
>
>
>
>Can someone recommend a decent hash table library?  I know about
>the functions in search.h (hsearch, etc.), but I need to be able
>to have multiple hash tables simultaneously, so this is out.
>
>TIA!
>
>kynn
>
>P.S.  Yes, I know I can ask "The Google" for links to "hash tables
>in C", but rather than links, what I'm looking for are recommendations
>from satisfied (and knowledgeable) customers.

Then this is not the place.  Nobody here uses hash tables, debuggers,
graphics, or anything else that is not mentioned in the C standards
documents.  If you don't believe me, just ask anyone here - they''l tell
you the same thing.

0
Reply gazelle3 (1726) 6/12/2009 4:42:11 PM

On Jun 12, 9:23=A0am, kj <no.em...@please.post> wrote:
> Can someone recommend a decent hash table library? =A0I know about
> the functions in search.h (hsearch, etc.), but I need to be able
> to have multiple hash tables simultaneously, so this is out.
>
> TIA!
>
> kynn
>
> P.S. =A0Yes, I know I can ask "The Google" for links to "hash tables
> in C", but rather than links, what I'm looking for are recommendations
> from satisfied (and knowledgeable) customers.

Have you tried sourceforge?
Plenty of hash table implementations there.
0
Reply dcorbit (2698) 6/12/2009 6:52:22 PM

kj wrote:
> Can someone recommend a decent hash table library?  I know about
> the functions in search.h (hsearch, etc.), but I need to be able
> to have multiple hash tables simultaneously, so this is out.
> 
> TIA!
> 
> kynn
> 
> P.S.  Yes, I know I can ask "The Google" for links to "hash tables
> in C", but rather than links, what I'm looking for are recommendations
> from satisfied (and knowledgeable) customers.

I wonder why Chuck Falconer hasn't sprung into this.

Anyway:

http://cbfalconer.home.att.net/download/
0
Reply jacob (2541) 6/12/2009 6:58:07 PM

"kj" <no.email@please.post> wrote in message 
news:h0tve2$drs$1@reader1.panix.com...
>
>
>
> Can someone recommend a decent hash table library?  I know about
> the functions in search.h (hsearch, etc.), but I need to be able
> to have multiple hash tables simultaneously, so this is out.
>
> TIA!
>
> kynn
>
> P.S.  Yes, I know I can ask "The Google" for links to "hash tables
> in C", but rather than links, what I'm looking for are recommendations
> from satisfied (and knowledgeable) customers.


can you not just write it yourself?...

for something THIS simple, if anything, you would need the learning 
experience...

and then, maybe 50-150 lines of code later (if that), one will have gained 
at least a small sliver of knowledge...

or until one is perplexed by such a task as, say, implementing a linked 
list, or calculating the sum of an array of numbers...


now, for a head start:
http://en.wikipedia.org/wiki/Hash_table



0
Reply cr88192355 (1928) 6/12/2009 7:21:57 PM

kj wrote:
> Can someone recommend a decent hash table library?  I know about
> the functions in search.h (hsearch, etc.), but I need to be able
> to have multiple hash tables simultaneously, so this is out.


There are no ISO recommendations for hash table lib in C, it's not part 
of the standard library, so I presume what you are refering to, is the 
library extensions found in the GNU C library.


> P.S.  Yes, I know I can ask "The Google" for links to "hash tables
> in C", but rather than links, what I'm looking for are recommendations
> from satisfied (and knowledgeable) customers.

A better place to ask this question is in e.g. comp.unix.programmer. I 
would have looked at libdict:

http://www.mirrorservice.org/sites/ftp.freebsd.org/pub/FreeBSD/distfiles/libdict.html


FUT: set.

-- 
Tor <echo bwzcab@wvtqvm.vw | tr i-za-h a-z>
0
Reply bwzcab (61) 6/12/2009 8:00:56 PM

"cr88192" <cr88192@hotmail.com> wrote in message 
news:h0u9so$cod$2@news.albasani.net...
>
> "kj" <no.email@please.post> wrote in message 
> news:h0tve2$drs$1@reader1.panix.com...
>>
>>
>>
>> Can someone recommend a decent hash table library?  I know about
>> the functions in search.h (hsearch, etc.), but I need to be able
>> to have multiple hash tables simultaneously, so this is out.
>>
>> TIA!
>>
>> kynn
>>
>> P.S.  Yes, I know I can ask "The Google" for links to "hash tables
>> in C", but rather than links, what I'm looking for are recommendations
>> from satisfied (and knowledgeable) customers.
>
>
> can you not just write it yourself?...
>
> for something THIS simple, if anything, you would need the learning 
> experience...
>
> and then, maybe 50-150 lines of code later (if that), one will have gained 
> at least a small sliver of knowledge...
>
> or until one is perplexed by such a task as, say, implementing a linked 
> list, or calculating the sum of an array of numbers...
>

(Aside: Use of complete sentences on USENET is a virtue).

Designing and implementing a hashing library is more difficult (say 5X to 
10X) than a linked list. There are many more choices to consider for 
implementation and more research and thought is therefor required (indeed, 
one may need linked list techniques to implement hashtables if chaining is 
chosen as the solution to collisions). The first hashtable one creates will 
surely not be the last nor will there be only one hashtable design to 
satisfy all needs. It will take a few (or a dozen) iterations and use over 
time to settle and be satisfied with some "final" designs. The OP may want 
to take a look at a C++ library for useful algorithms and design ideas if 
that language is not a deterent to him, as those are evolved and robust 
implementations. A container and algorithm library should have cohesiveness 
and developing one container in isolation is a "myopic" approach. Finally, a 
hashtable should not be the first container a noob should try to create. 


0
Reply tony422 (386) 6/12/2009 8:14:06 PM

Tor Rustad <bwzcab@wvtqvm.vw> writes:

> kj wrote:
>> Can someone recommend a decent hash table library?  I know about
>> the functions in search.h (hsearch, etc.), but I need to be able
>> to have multiple hash tables simultaneously, so this is out.
>
>
> There are no ISO recommendations for hash table lib in C, it's not
> part of the standard library, so I presume what you are refering to,
> is the library extensions found in the GNU C library.

hsearch and friends are specified by POSIX.

If you are in fact using GNU libc (probably the case if and only if you
are on Linux), they provide as an extension a set of reentrant
functions, hsearch_r etc, which will let you create multiple hash
tables.
0
Reply nate14 (514) 6/12/2009 8:27:00 PM

Tony wrote:

[...]

> It will take a few (or a dozen) iterations and use over 
> time to settle and be satisfied with some "final" designs. The OP may want 
> to take a look at a C++ library for useful algorithms and design ideas if 
> that language is not a deterent to him, as those are evolved and robust 
> implementations. 

Nonsense, OP is familiar with the GNU interface:


int hcreate(size_t nel);
ENTRY *hsearch(ENTRY item, ACTION action);
void hdestroy(void);


so adjusting this API to handle multiple hash tables, can easily be done 
in a couple of *seconds*:

struct hash_table *my_hcreate(size_t nel);
ENTRY *my_hsearch(struct hash_table *, ENTRY item, ACTION action);
void   my_hdestroy(struct hash_table *);


the point is not to hold the hash table internally.

> A container and algorithm library should have cohesiveness 
> and developing one container in isolation is a "myopic" approach. Finally, a 
> hashtable should not be the first container a noob should try to create. 

Every elementary book on algorithms, would most likely discuss this 
topic. Reading up on collisions, isn't exactly rocket science.

-- 
Tor <echo bwzcab@wvtqvm.vw | tr i-za-h a-z>
0
Reply bwzcab (61) 6/12/2009 9:09:17 PM

Nate Eldredge <nate@vulcan.lan> writes:

> Tor Rustad <bwzcab@wvtqvm.vw> writes:
>
>> kj wrote:
>>> Can someone recommend a decent hash table library?  I know about
>>> the functions in search.h (hsearch, etc.), but I need to be able
>>> to have multiple hash tables simultaneously, so this is out.
>>
>>
>> There are no ISO recommendations for hash table lib in C, it's not
>> part of the standard library, so I presume what you are refering to,
>> is the library extensions found in the GNU C library.
>
> hsearch and friends are specified by POSIX.
>
> If you are in fact using GNU libc (probably the case if and only if you
> are on Linux), they provide as an extension a set of reentrant
> functions, hsearch_r etc, which will let you create multiple hash
> tables.

Be careful with those.  I've seen at least one system (Tru64 IIRC)
that had almost the same extension: same function names, but arguments
swapped.

The GNU hash table isn't particularly good anyway, so my advice is to
find some other library with a suitable licence.

-- 
M�ns Rullg�rd
mans@mansr.com
0
Reply mans (444) 6/12/2009 9:28:55 PM

On 12 Jun 2009 at 21:09, Tor Rustad wrote:
> int hcreate(size_t nel);
> ENTRY *hsearch(ENTRY item, ACTION action);
> void hdestroy(void);

Unfortunately, this interface is unnecessarily rigid, since keys are
forced to be character strings compared for equality with strcmp().

While this standard interface can be a convenient shortcut if your
situation happens to be one it applies to, it's still no substitute for
rolling your own standard hash table, since it lacks the generality you
often need. It would be better if an ENTRY was an arbitary void *, and
the constructor hcreate() took a comparison function pointer as an
argument.

The memory management is also a pig's breakfast: there is no way to tell
hdestroy() whether or not it needs to free the key and/or value pointers
in the items in the hash table, so the only solution is for the
programmer to maintain a whole other data structure just to do
bookkeeping for his or her hash table! Again it would be easier just to
implement your own hash table to begin with.

I find it difficult to understand why a recent international standard
would choose not to facilitate the level of generality often needed in
applications, and to create a memory management mess for users of this
data structure.

0
Reply nospam59 (11087) 6/13/2009 12:03:19 AM

"Tony" <tony@my.net> wrote in message 
news:gGyYl.13106$im1.12622@nlpi061.nbdc.sbc.com...
>
> "cr88192" <cr88192@hotmail.com> wrote in message 
> news:h0u9so$cod$2@news.albasani.net...
>>
>> "kj" <no.email@please.post> wrote in message 
>> news:h0tve2$drs$1@reader1.panix.com...
>>>
>>>
>>>
>>> Can someone recommend a decent hash table library?  I know about
>>> the functions in search.h (hsearch, etc.), but I need to be able
>>> to have multiple hash tables simultaneously, so this is out.
>>>
>>> TIA!
>>>
>>> kynn
>>>
>>> P.S.  Yes, I know I can ask "The Google" for links to "hash tables
>>> in C", but rather than links, what I'm looking for are recommendations
>>> from satisfied (and knowledgeable) customers.
>>
>>
>> can you not just write it yourself?...
>>
>> for something THIS simple, if anything, you would need the learning 
>> experience...
>>
>> and then, maybe 50-150 lines of code later (if that), one will have 
>> gained at least a small sliver of knowledge...
>>
>> or until one is perplexed by such a task as, say, implementing a linked 
>> list, or calculating the sum of an array of numbers...
>>
>
> (Aside: Use of complete sentences on USENET is a virtue).
>
> Designing and implementing a hashing library is more difficult (say 5X to 
> 10X) than a linked list. There are many more choices to consider for 
> implementation and more research and thought is therefor required (indeed, 
> one may need linked list techniques to implement hashtables if chaining is 
> chosen as the solution to collisions). The first hashtable one creates 
> will surely not be the last nor will there be only one hashtable design to 
> satisfy all needs. It will take a few (or a dozen) iterations and use over 
> time to settle and be satisfied with some "final" designs. The OP may want 
> to take a look at a C++ library for useful algorithms and design ideas if 
> that language is not a deterent to him, as those are evolved and robust 
> implementations. A container and algorithm library should have 
> cohesiveness and developing one container in isolation is a "myopic" 
> approach. Finally, a hashtable should not be the first container a noob 
> should try to create.

IMO, it is nowhere near that difficult...
hash tables are (conceptually) intimidating, but in practice are damn near 
one of the simplest things to implement (well, ok, linked lists are maybe 
simpler, but this is not always the case...).


well, ok, there are 3 major varieties of hash (my own terms here):
single-index hashes;
multi-index/iterative hashes;
chained hashes.


a single-index hash is what I could also call a "cache hash", basically, one 
computes the index, and checks the item at the index. if it is a match, the 
lookup succeeded, so do whatever. if it is not a match, do whatever and put 
the result in this spot in the hash (so that it will be found next time).

IMO, this approach is very simple (maybe only a few lines of code in many 
cases), and does speedup many operations (primarily lookups), but is not 
good for "exact" lookups (since collisions will typically replace whatever 
key was there before...).


iterative hashing:

an iterative hash basically differs from the above in that:
usually the hash table is larger (since now the hash actually needs to store 
stuff);
usually, whenever there is a colision, some means is needed to calculate a 
new "subsequent" key.

however, it has a few added costs:
the hash table can fill up;
resizing the table typically requires an awkward "re-hash" process;
if this is done, any existing literal indices into the table will be 
invalidated.

this leads to 2 solutions:
make the hash larger than the maximum number of items it may reasonably 
contain (the hash-table filling up can then be regarded as a "fatal" error);
don't hold literal indices into the table, thus resizing/rehashing is safe.

as an advantage, this approach tends to be fastest IME, but is a little more 
effort to make work well (in one of my more complicated uses, I have a table 
of this sort that is around 500 loc).


chaining:

this can have the advantages of the first and second approaches:
the hash table can be smaller and need not be resized;
one can hold literal indices to items (just not in the hash table itself).

the alteration is to have a sideband array (or, typically, several 
associated arrays), which contain:
the keys; the values;
index chains (each item holds the array index of the next item, or a 
terminal value such as 0 or -1).

so, one calculates the hash, and jumps to the item in question, and steps 
along the list.
indices can be held into this array, and the array can be resized as needed 
without any other ill-effects.

the cost of chaining, however, is that if the hash table is too small chains 
may become long and performance is reduced.



hash functions:

some people like shifts and xors, but I dislike this approach, as I have 
found that in general it is difficult to get good behavior from this 
(typically, a combination which works well for one type of input works 
poorly for another).

so, my typical approach is to use primes:
either normal primes or mersenne primes (note that, numerically, they behave 
rather differently).

for example, to hash a string:
i=0; while(*s)i=(i*4093)+(*s++);

this uses a normal prime. IME, the most effective strategy here is to shift 
right and mask to the table size when getting the table index:
j=(i>>12)&16383;

my usual method for itteration then is to multiply the original value by the 
prime:
i=i*4093+1;    //the +1 is for the rare case i==0

which, when combined with the above, generates a psuedorandom sequence...

mersenne primes are similar, but different:
i=0; while(*s)i=(i*127)+(*s++);

and:
i=i*127+1;

but differ in that usually one wants the low bits:
j=i&16383;


why this is the case is subtle number magic IMO, but mixing these up (taking 
the low bits of a normal prime, or the high bits of a mersenne prime) leads 
to poor results.

also, typically with normal primes, one wants the right-shift to be near the 
same value as the prime, which should be within a few orders of magnitude of 
the hash size.

for mersenne primes, they should be around 2^((log2 n)/2) if possible (seems 
to give best results), but this is problematic as there are not so many 
usable mersenne primes (whereas normal primes are far more common...).

as such, I typically use normal primes, except for with small hashes (for 
example <=1024 spots) where mersenne primes seem to work better...


multiplying against a prime can also hash many other types of data as well 
(not just strings), for example, if done right they are similarly effective 
with pointers, ...


> 


0
Reply cr88192355 (1928) 6/13/2009 4:41:17 AM

Antoninus Twink <nospam@nospam.invalid> writes:

> On 12 Jun 2009 at 21:09, Tor Rustad wrote:
>> int hcreate(size_t nel);
>> ENTRY *hsearch(ENTRY item, ACTION action);
>> void hdestroy(void);
>
> Unfortunately, this interface is unnecessarily rigid, since keys are
> forced to be character strings compared for equality with strcmp().
>
> While this standard interface can be a convenient shortcut if your
> situation happens to be one it applies to, it's still no substitute for
> rolling your own standard hash table, since it lacks the generality you
> often need. It would be better if an ENTRY was an arbitary void *, and
> the constructor hcreate() took a comparison function pointer as an
> argument.
>
> The memory management is also a pig's breakfast: there is no way to tell
> hdestroy() whether or not it needs to free the key and/or value pointers
> in the items in the hash table, so the only solution is for the
> programmer to maintain a whole other data structure just to do
> bookkeeping for his or her hash table! Again it would be easier just to
> implement your own hash table to begin with.
>
> I find it difficult to understand why a recent international standard
> would choose not to facilitate the level of generality often needed in
> applications, and to create a memory management mess for users of this
> data structure.

The interface wasn't invented by POSIX, it came from SYSV.  POSIX chose
to adopt the existing practice, presumably not so much to promote its
use in new software as to guarantee the continued functionality of old
SYSV software that used it.

I think POSIX wisely refrained from inventing a new and improved hash
table API; such things rarely turn out well when designed by committee.
0
Reply nate14 (514) 6/13/2009 6:09:59 AM

On Jun 12, 11:23=A0pm, kj <no.em...@please.post> wrote:
> Can someone recommend a decent hash table library? =A0I know about
> the functions in search.h (hsearch, etc.), but I need to be able
> to have multiple hash tables simultaneously, so this is out.

hsearch(), etc. from gnu have multiple-use versions
named, IIRC, hsearch_r(), etc.  In fact, gnu's hsearch()
just calls hsearch_r().

There may be *other* good reasons not to use hsearch_r().
Do you have special requirements?  Speed, space, etc.?

James
0
Reply jdallen2000 (495) 6/13/2009 8:10:49 AM

Antoninus Twink wrote:

> On 12 Jun 2009 at 21:09, Tor Rustad wrote:
>> int hcreate(size_t nel);
>> ENTRY *hsearch(ENTRY item, ACTION action);
>> void hdestroy(void);
> 
> Unfortunately, this interface is unnecessarily rigid, since keys are
> forced to be character strings compared for equality with strcmp().


The design of the POSIX and GNU extensions to the standard C libraries, 
are better discussed in comp.unix.programmer.

A more flexible API design is provided in the <libdict> library, but 
that has a cost of being more complicated to use, when compared to the 
POSIX/GNU alternative.

The most important characteristic of an API, is simplicity, if more 
flexibility and portability is needed by OP, he could just use e.g. the 
<libdict> library, which has a BSD licence.

-- 
Tor <echo bwzcab@wvtqvm.vw | tr i-za-h a-z>
0
Reply bwzcab (61) 6/13/2009 11:51:36 AM

Tor Rustad wrote:
> Tony wrote:
>
> [...]
>
>> It will take a few (or a dozen) iterations and use over
>> time to settle and be satisfied with some "final" designs. The OP
>> may want to take a look at a C++ library for useful algorithms and
>> design ideas if that language is not a deterent to him, as those are
>> evolved and robust implementations.
>
> Nonsense, OP is familiar with the GNU interface:
>
>
> int hcreate(size_t nel);
> ENTRY *hsearch(ENTRY item, ACTION action);
> void hdestroy(void);
>
>
> so adjusting this API to handle multiple hash tables, can easily be
> done in a couple of *seconds*:
>
> struct hash_table *my_hcreate(size_t nel);
> ENTRY *my_hsearch(struct hash_table *, ENTRY item, ACTION action);
> void   my_hdestroy(struct hash_table *);
>
>
> the point is not to hold the hash table internally.
>
>> A container and algorithm library should have cohesiveness
>> and developing one container in isolation is a "myopic" approach.
>> Finally, a hashtable should not be the first container a noob should
>> try to create.
>
> Every elementary book on algorithms, would most likely discuss this
> topic. Reading up on collisions, isn't exactly rocket science.

Using or just copying existing hash containers (whether from existing 
library or textbook) is hardly the same as doing the required research to 
become capable to create something "from scratch". No one is going to sit 
down and create their first hashtable and then use it for the rest of their 
programming days. The same could of course be said for any container, but 
hashtable is, like I have already noted, not trivial compared to say linked 
list, though certainly a fixed-size table is easier to do than a dynamic 
one. 


0
Reply tony422 (386) 6/14/2009 3:23:19 AM

cr88192 wrote:
> "Tony" <tony@my.net> wrote in message
> news:gGyYl.13106$im1.12622@nlpi061.nbdc.sbc.com...
>>
>> "cr88192" <cr88192@hotmail.com> wrote in message
>> news:h0u9so$cod$2@news.albasani.net...
>>>
>>> "kj" <no.email@please.post> wrote in message
>>> news:h0tve2$drs$1@reader1.panix.com...
>>>>
>>>>
>>>>
>>>> Can someone recommend a decent hash table library?  I know about
>>>> the functions in search.h (hsearch, etc.), but I need to be able
>>>> to have multiple hash tables simultaneously, so this is out.
>>>>
>>>> TIA!
>>>>
>>>> kynn
>>>>
>>>> P.S.  Yes, I know I can ask "The Google" for links to "hash tables
>>>> in C", but rather than links, what I'm looking for are
>>>> recommendations from satisfied (and knowledgeable) customers.
>>>
>>>
>>> can you not just write it yourself?...
>>>
>>> for something THIS simple, if anything, you would need the learning
>>> experience...
>>>
>>> and then, maybe 50-150 lines of code later (if that), one will have
>>> gained at least a small sliver of knowledge...
>>>
>>> or until one is perplexed by such a task as, say, implementing a
>>> linked list, or calculating the sum of an array of numbers...
>>>
>>
>> (Aside: Use of complete sentences on USENET is a virtue).
>>
>> Designing and implementing a hashing library is more difficult (say
>> 5X to 10X) than a linked list. There are many more choices to
>> consider for implementation and more research and thought is
>> therefor required (indeed, one may need linked list techniques to
>> implement hashtables if chaining is chosen as the solution to
>> collisions). The first hashtable one creates will surely not be the
>> last nor will there be only one hashtable design to satisfy all
>> needs. It will take a few (or a dozen) iterations and use over time
>> to settle and be satisfied with some "final" designs. The OP may
>> want to take a look at a C++ library for useful algorithms and
>> design ideas if that language is not a deterent to him, as those are
>> evolved and robust implementations. A container and algorithm
>> library should have cohesiveness and developing one container in
>> isolation is a "myopic" approach. Finally, a hashtable should not be
>> the first container a noob should try to create.
>
> IMO, it is nowhere near that difficult...
> hash tables are (conceptually) intimidating, but in practice are damn
> near one of the simplest things to implement (well, ok, linked lists
> are maybe simpler, but this is not always the case...).
>

Hash tables are not "damn near one of the simplest things to implement". 
Anyone who thinks so has surely never implemented one of any generality or 
applicability. I've evolved the ones I use over a long time period along 
with the framework within which they reside. Though I forget all the 
decision details, I do remember being enlightened more than once and 
reworking them a few times to have what I have now. There are many, many 
ways to implement hashtables and many of those are "domain"-specific. 
Textbook offerings need not apply.

To the other guy: If all you have is UNIX... all you have is UNIX! (Couldn't 
resist that).

[snipped excessively looooong response with way too many ellipses!] 


0
Reply tony422 (386) 6/14/2009 3:35:41 AM

Tor Rustad wrote:
> Tony wrote:
>
> [...]
>
>> It will take a few (or a dozen) iterations and use over
>> time to settle and be satisfied with some "final" designs. The OP
>> may want to take a look at a C++ library for useful algorithms and
>> design ideas if that language is not a deterent to him, as those are
>> evolved and robust implementations.
>
> Nonsense, OP is familiar with the GNU interface:

While the OP asked for a library, I, OTOH, was responding to another 
poster's post.

Context matters people!


0
Reply tony422 (386) 6/14/2009 3:37:22 AM

"Tony" <tony@my.net> wrote in message 
news:0g_Yl.31920$yr3.31122@nlpi068.nbdc.sbc.com...
> cr88192 wrote:
>> "Tony" <tony@my.net> wrote in message
>> news:gGyYl.13106$im1.12622@nlpi061.nbdc.sbc.com...
>>>
>>> "cr88192" <cr88192@hotmail.com> wrote in message
>>> news:h0u9so$cod$2@news.albasani.net...
>>>>
>>>> "kj" <no.email@please.post> wrote in message
>>>> news:h0tve2$drs$1@reader1.panix.com...
>>>>>
>>>>>
>>>>>
>>>>> Can someone recommend a decent hash table library?  I know about
>>>>> the functions in search.h (hsearch, etc.), but I need to be able
>>>>> to have multiple hash tables simultaneously, so this is out.
>>>>>
>>>>> TIA!
>>>>>
>>>>> kynn
>>>>>
>>>>> P.S.  Yes, I know I can ask "The Google" for links to "hash tables
>>>>> in C", but rather than links, what I'm looking for are
>>>>> recommendations from satisfied (and knowledgeable) customers.
>>>>
>>>>
>>>> can you not just write it yourself?...
>>>>
>>>> for something THIS simple, if anything, you would need the learning
>>>> experience...
>>>>
>>>> and then, maybe 50-150 lines of code later (if that), one will have
>>>> gained at least a small sliver of knowledge...
>>>>
>>>> or until one is perplexed by such a task as, say, implementing a
>>>> linked list, or calculating the sum of an array of numbers...
>>>>
>>>
>>> (Aside: Use of complete sentences on USENET is a virtue).
>>>
>>> Designing and implementing a hashing library is more difficult (say
>>> 5X to 10X) than a linked list. There are many more choices to
>>> consider for implementation and more research and thought is
>>> therefor required (indeed, one may need linked list techniques to
>>> implement hashtables if chaining is chosen as the solution to
>>> collisions). The first hashtable one creates will surely not be the
>>> last nor will there be only one hashtable design to satisfy all
>>> needs. It will take a few (or a dozen) iterations and use over time
>>> to settle and be satisfied with some "final" designs. The OP may
>>> want to take a look at a C++ library for useful algorithms and
>>> design ideas if that language is not a deterent to him, as those are
>>> evolved and robust implementations. A container and algorithm
>>> library should have cohesiveness and developing one container in
>>> isolation is a "myopic" approach. Finally, a hashtable should not be
>>> the first container a noob should try to create.
>>
>> IMO, it is nowhere near that difficult...
>> hash tables are (conceptually) intimidating, but in practice are damn
>> near one of the simplest things to implement (well, ok, linked lists
>> are maybe simpler, but this is not always the case...).
>>
>
> Hash tables are not "damn near one of the simplest things to implement". 
> Anyone who thinks so has surely never implemented one of any generality or 
> applicability. I've evolved the ones I use over a long time period along 
> with the framework within which they reside. Though I forget all the 
> decision details, I do remember being enlightened more than once and 
> reworking them a few times to have what I have now. There are many, many 
> ways to implement hashtables and many of those are "domain"-specific. 
> Textbook offerings need not apply.
>
> To the other guy: If all you have is UNIX... all you have is UNIX! 
> (Couldn't resist that).
>
> [snipped excessively looooong response with way too many ellipses!]

I have implemented more than a few of the things, and I have nowhere along 
the lines encountered any sort of pandora's box of unforseen complexity...

I have also used them for all sorts of tasks, ranging from:
looking up keys;
merging strings;
looking for repeating patterns (LZ77, ...);
hashing object field and method lookups;
....


my experience is that, like linked lists, the task is sufficiently simple 
that one implements a hash for the task at hand, and then they are free to 
move on to the next task at hand.

(it is much like linked lists and sort functions, once one learns the basic 
algorithms one can write sort functions for all sorts of tasks...).


through experience, one refines the technique, but the core idea is simple, 
and easy to learn.
just people keep fudding it up by calling it difficult...

> 


0
Reply cr88192355 (1928) 6/14/2009 6:54:10 AM

"Tony" <tony@my.net> wrote in message 
news:0g_Yl.31919$yr3.1342@nlpi068.nbdc.sbc.com...
> Tor Rustad wrote:
>> Tony wrote:
>>

<snip>

>>
>> the point is not to hold the hash table internally.
>>
>>> A container and algorithm library should have cohesiveness
>>> and developing one container in isolation is a "myopic" approach.
>>> Finally, a hashtable should not be the first container a noob should
>>> try to create.
>>
>> Every elementary book on algorithms, would most likely discuss this
>> topic. Reading up on collisions, isn't exactly rocket science.
>
> Using or just copying existing hash containers (whether from existing 
> library or textbook) is hardly the same as doing the required research to 
> become capable to create something "from scratch". No one is going to sit 
> down and create their first hashtable and then use it for the rest of 
> their programming days. The same could of course be said for any 
> container, but hashtable is, like I have already noted, not trivial 
> compared to say linked list, though certainly a fixed-size table is easier 
> to do than a dynamic one.

I am confused by what is meant by this...

hash tables are trivial enough to write, yes...
but, errm, how will one expect a single hash table to fulfill all their 
tasks?
this makes little sense to me.

often some tasks may require several different hash tables for the same 
task.

unless you mean, they always type out exactly the same code, but I don't see 
why someone would do this, as inevitably they would see things that could be 
improved the next time they write out a hash table...


it is like, my "magic" with primes and pseudo-random permutations. I didn't 
start out with this, but both techniques popped up at various points, and 
were an improvement to prior techniques, and so they stuck.

in fact, I will note, hashes are typically so simple that one need not even 
bother with copying and pasting, as usually the entire implementation can be 
kept in ones' memory, ... (unlike, say, a typical parser, where 
copy/paste/edit is usually better...).


or such...

>


0
Reply cr88192355 (1928) 6/14/2009 7:03:47 AM

cr88192 said:

<snip>
 
> hash tables are trivial enough to write, yes...
> but, errm, how will one expect a single hash table to fulfill all
> their tasks?
> this makes little sense to me.

There is at least one hash table library in existence that can solve 
not only all /their/ tasks, but everyone else's tasks as well. I 
think we all know the one I mean.

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Forged article? See 
http://www.cpax.org.uk/prg/usenet/comp.lang.c/msgauth.php
"Usenet is a strange place" - dmr 29 July 1999
0
Reply rjh (10790) 6/14/2009 7:10:53 AM

Tony wrote:
> Tor Rustad wrote:
>> Tony wrote:
>>
>> [...]
>>
>>> It will take a few (or a dozen) iterations and use over
>>> time to settle and be satisfied with some "final" designs. The OP
>>> may want to take a look at a C++ library for useful algorithms and
>>> design ideas if that language is not a deterent to him, as those are
>>> evolved and robust implementations.
>> Nonsense, OP is familiar with the GNU interface:
> 
> While the OP asked for a library, I, OTOH, was responding to another 
> poster's post.
> 
> Context matters people!

Yes it do, and context here in my book -- was giving advice to OP. :)

Looking into a C++ library for design ideas and algorithms, would be 
very low on my list for useful things to do when designing a C library.

For algorithms, I would for starters look that up in Knuth and 
Sedgewick, and for API design ideas, existing C libraries are would be a 
far better place to start.

$ man hcreate
[...]
        #define _GNU_SOURCE
        #include <search.h>

        int hcreate_r(size_t nel, struct hsearch_data *tab);

        int hsearch_r(ENTRY item, ACTION action, ENTRY **ret,
                      struct hsearch_data *tab);

        void hdestroy_r(struct hsearch_data *tab);


so it appears at least GNU libc already has the extensions OP was 
looking for, and those API modifications to handle multiple hash tables, 
looked awfully close to the ones I suggested.

-- 
Tor <echo bwzcab@wvtqvm.vw | tr i-za-h a-z>
0
Reply bwzcab (61) 6/14/2009 10:01:01 AM

Tony wrote:
> Tor Rustad wrote:
>> Tony wrote:

[...]

>>> A container and algorithm library should have cohesiveness
>>> and developing one container in isolation is a "myopic" approach.
>>> Finally, a hashtable should not be the first container a noob should
>>> try to create.
>> Every elementary book on algorithms, would most likely discuss this
>> topic. Reading up on collisions, isn't exactly rocket science.
> 
> Using or just copying existing hash containers (whether from existing 
> library or textbook) is hardly the same as doing the required research to 
> become capable to create something "from scratch". No one is going to sit 
> down and create their first hashtable and then use it for the rest of their 
> programming days. The same could of course be said for any container, but 
> hashtable is, like I have already noted, not trivial compared to say linked 
> list, though certainly a fixed-size table is easier to do than a dynamic 
> one. 

Some 10+ years ago I tuned the most time consuming server on a major 
OLTP switch. The existing server for routing transactions worked 
correctly, but measurements showed it was THE bottleneck. After 
inspecting the COBOL source, it was easy to see that the search 
algorithm there was the sinner.

I wrote 4 new versions of the server in C, sporting different search 
algorithms (including hashing). The result was validated and 
benchmarked, and all the new servers showed a massive speed-up, with the 
hashing version being the fastest.

We never put the hashing version into production, but went for the most 
robust and less memory consuming search strategy. That was fast enough, 
and the new routing server has been running flawless ever since it was 
put into production.

Can't say I remember implementing dynamic hash table and handling 
collisions, to be such a challenge really, but I wasn't looking for 
implementing a Boost library in C either.

However, I don't disagree that implementing a linked-list is easier, 
wouldn't lookup Knuth and/or Sedgewick to do that.

-- 
Tor <echo bwzcab@wvtqvm.vw | tr i-za-h a-z>
0
Reply bwzcab (61) 6/14/2009 10:07:01 AM

Tor Rustad <bwzcab@wvtqvm.vw> writes:
> kj wrote:
>> Can someone recommend a decent hash table library?  I know about
>> the functions in search.h (hsearch, etc.), but I need to be able
>> to have multiple hash tables simultaneously, so this is out.
>
> There are no ISO recommendations for hash table lib in C, it's not
> part of the standard library, so I presume what you are refering to,
>
>
>> P.S.  Yes, I know I can ask "The Google" for links to "hash tables
>> in C", but rather than links, what I'm looking for are recommendations
>> from satisfied (and knowledgeable) customers.

Implementing a hash table is so dead simple that there is little to be
gained by using third party code for that, except the usual problems
coming with that, eg bugs which have to be fixed in code noone really
knows (yet).
0
Reply rweikusat (2830) 6/14/2009 2:33:08 PM

"Tony" <tony@my.net> wrote in message
>
> Hash tables are not "damn near one of the simplest things to implement". 
> Anyone who thinks so has surely never implemented one of any generality or 
> applicability.
>
The problem is getting a nice interface, efficiency, and generality. Often 
it is handy to have the keys as strings, for instance, but not always. 
Sometimes you want to store objects and sometimes pointers, and you don't 
want to store pointers as objects because that entails inefficient byte by 
byte copying.

However the actual hash table logic isn't too difficult.


0
Reply regniztar (3128) 6/14/2009 3:04:39 PM

"Malcolm McLean" <regniztar@btinternet.com> writes:

> "Tony" <tony@my.net> wrote in message
>>
>> Hash tables are not "damn near one of the simplest things to implement". 
>> Anyone who thinks so has surely never implemented one of any generality or 
>> applicability.
>>
> The problem is getting a nice interface, efficiency, and generality. Often 
> it is handy to have the keys as strings, for instance, but not always. 
> Sometimes you want to store objects and sometimes pointers, and you don't 
> want to store pointers as objects because that entails inefficient byte by 
> byte copying.
>
> However the actual hash table logic isn't too difficult.

But there are a lot of choices.  How do you handle collisions?
Do you put a linked list at each entry of the hash table?  Do you do
linear or quadratic probing?  What will you use for a hash function?
The best option in each case may depend on knowing something about your
data set, and a wrong choice may unexpectedly give pathological behavior.

I'm not sure that it's so trivial.  In a real application, I wouldn't
mind having a linked list implemented by a beginner, but I'd rather use
a hash table developed by someone that really knew what they were
doing.  So I'd probably prefer to use an established library.

Just my $0.02.
0
Reply nate14 (514) 6/14/2009 4:40:44 PM

On Jun 12, 5:03=A0pm, Antoninus Twink <nos...@nospam.invalid> wrote:
> On 12 Jun 2009 at 21:09, Tor Rustad wrote:
>
> > int hcreate(size_t nel);
> > ENTRY *hsearch(ENTRY item, ACTION action);
> > void hdestroy(void);
>
> Unfortunately, this interface is unnecessarily rigid, since keys are
> forced to be character strings compared for equality with strcmp().
>

Huh? How do get that the keys are forced to be character strings?
0
Reply cdalten (975) 6/14/2009 4:49:08 PM

"Malcolm McLean" <regniztar@btinternet.com> wrote in message 
news:1fmdnW-xw47qjKjXnZ2dnUVZ8h-dnZ2d@bt.com...
> "Tony" <tony@my.net> wrote in message
>>
>> Hash tables are not "damn near one of the simplest things to implement". 
>> Anyone who thinks so has surely never implemented one of any generality 
>> or applicability.
>>
> The problem is getting a nice interface, efficiency, and generality. Often 
> it is handy to have the keys as strings, for instance, but not always. 
> Sometimes you want to store objects and sometimes pointers, and you don't 
> want to store pointers as objects because that entails inefficient byte by 
> byte copying.
>
> However the actual hash table logic isn't too difficult.
>

yeah...

I hadn't much considered the "generic API" case, because IMO hashes were 
often too simple for me to feel there was much need for a generic API...

(it is much how like if one wants a "generic sort" they can use qsort, 
nevermind that there are many cases where qsort does not fit well, and so it 
is often better to implement a custom sorter for the specific task...).


so, if one needed an API, a solution I think would be to have several 
"varieties" of hash best suited to particular use patterns, but which have 
relatively "generic" behavior, and then wrap them with little interfaces to 
make them more applicable to specific cases (such as interning strings, 
looking up by key, ...).


nevermind that someone more like myself would likely just implement custom 
logic for the specific task-at-hand, and then maybe give the task a nice 
little API.

so, I don't think: hash table which does everyone's needs, rather:
intern strings;
lookup key and return value;
....

often, the hashtables are invisible behind-the-scenes components.


one doesn't know that, for example, when they invoke an interface method on 
an object, it jumps through a hash table (typically via pre-computed 
indices), rather than, say, looking up the interface method linearly, 
looking for the class containing the method and fetching the method info 
(starting at the object and walking the inheritence heirarchy), ...

likewise for "given a pointer to a function, go and find its name and 
relevant metadata", ...

the hash is just a way to solve this particular problem, and so need not be 
exposed in its own right.


so, "hash table" is a fairly vague and far reaching idea.

"here is a name so give me a value" is far more specific.
personally, I figure time is better served addressing these more specific 
issues, as they occur.


it is much like how, if given a simple file to parse, one does not go and 
try to address all the great issues of parsing, one just writes a parser...

(or at least, some do, and end up throwing lex and yacc at problems that, 
IMO, either have no need for, or are ill suited to, the usage of these 
tools...).

it is like how screwdrivers, wrenches, and drills are different tool.
in general it is not needed for someone to go and try to figure out how to 
unify them (say, for example, as a terribly overpowered electric drill which 
can accept impact sockets, and is small and light enough, and precise 
enough, that it doesn't tear things apart when one tries to use it like an 
electric screwdriver...).

similarly, it is also not likely to need an add-on for hammer-like 
functionality, ...


>


0
Reply cr88192355 (1928) 6/14/2009 5:09:21 PM

chad <cdalten@gmail.com> writes:

> On Jun 12, 5:03�pm, Antoninus Twink <nos...@nospam.invalid> wrote:
>> On 12 Jun 2009 at 21:09, Tor Rustad wrote:
>>
>> > int hcreate(size_t nel);
>> > ENTRY *hsearch(ENTRY item, ACTION action);
>> > void hdestroy(void);
>>
>> Unfortunately, this interface is unnecessarily rigid, since keys are
>> forced to be character strings compared for equality with strcmp().
>>
>
> Huh? How do get that the keys are forced to be character strings?

From FreeBSD's hcreate(3):

     The hsearch() function is a hash-table search routine.  It returns a
     pointer into a hash table indicating the location at which an entry can
     be found.  The item argument is a structure of type ENTRY (defined in the
     <search.h> header) containing two pointers: item.key points to the com-
     parison key (a char *), and item.data (a void *) points to any other data
     to be associated with that key.  The comparison function used by
     hsearch() is strcmp(3).          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     ^^^^^^^^^^^^^^^^^^^^^^^


0
Reply nate14 (514) 6/14/2009 5:37:21 PM

"Nate Eldredge" <nate@vulcan.lan> wrote in message
> "Malcolm McLean" <regniztar@btinternet.com> writes:
>
>>
>> However the actual hash table logic isn't too difficult.
>
> But there are a lot of choices.  How do you handle collisions?
> Do you put a linked list at each entry of the hash table?  Do you do
> linear or quadratic probing?  What will you use for a hash function?
> The best option in each case may depend on knowing something about your
> data set, and a wrong choice may unexpectedly give pathological behavior.
>
> I'm not sure that it's so trivial.  In a real application, I wouldn't
> mind having a linked list implemented by a beginner, but I'd rather use
> a hash table developed by someone that really knew what they were
> doing.  So I'd probably prefer to use an established library.
>
That's true.

However 90% of the time you just want linear access times.
The main problem for a generic table is the rehashing problem, when the 
table has to be resized. This can be OK or totally unacceptable, depending 
on whether the program can take a few millions of cycles out once in a blue 
moon.


0
Reply regniztar (3128) 6/14/2009 6:31:31 PM

"Nate Eldredge" <nate@vulcan.lan> wrote in message 
news:863aa2db03.fsf@vulcan.lan...
> "Malcolm McLean" <regniztar@btinternet.com> writes:
>
>> "Tony" <tony@my.net> wrote in message
>>>
>>> Hash tables are not "damn near one of the simplest things to implement".
>>> Anyone who thinks so has surely never implemented one of any generality 
>>> or
>>> applicability.
>>>
>> The problem is getting a nice interface, efficiency, and generality. 
>> Often
>> it is handy to have the keys as strings, for instance, but not always.
>> Sometimes you want to store objects and sometimes pointers, and you don't
>> want to store pointers as objects because that entails inefficient byte 
>> by
>> byte copying.
>>
>> However the actual hash table logic isn't too difficult.
>
> But there are a lot of choices.  How do you handle collisions?
> Do you put a linked list at each entry of the hash table?  Do you do
> linear or quadratic probing?  What will you use for a hash function?
> The best option in each case may depend on knowing something about your
> data set, and a wrong choice may unexpectedly give pathological behavior.
>

well, typically not worse than a linear search, unless the implementation is 
really bad...


as for linear and quadratic probing, IMO, both are lame, so personally I use 
neither...
usually, I use psuedo-random probing...

since each key ends up calculating a (generally) unique hash value, the 
psuedo-random sequence is typically different for each input key, and as 
such, the usual bad behavior of linear probing is often avoided.

of course, typically after some N probes, one either has to resize the 
table, or do a linear scan (but, of course, by the time one is doing a 
linear scan one can safely conclude that the table is either full or almost 
entirely full, and so by this point I normally fallback to whatever the 
"table is full" behavior is...).


as for hash functions, for most input data I have found primes-based 
polynomial hashing to be most effective, and in general, it is relatively 
flexible and forgiving (vs the more popular shifts&xors, which typically 
work well for one piece of data and suck for another...).

there are slight variations though related to the size and type of the prime 
(mostly related to approximate hash table size).

I usually have the tables themselves at either power-of-2 sizes, or may 
expand via a factor of 1.5^x.


> I'm not sure that it's so trivial.  In a real application, I wouldn't
> mind having a linked list implemented by a beginner, but I'd rather use
> a hash table developed by someone that really knew what they were
> doing.  So I'd probably prefer to use an established library.
>

in a "real application", we typically use a profile and optimize whatever is 
going slow...
if said hash table is poorly written and bogs down the app, it will 
typically show up on the profiler, and if it does not, it is either working 
well or is not being used enough to matter...


if it really matters that it works well, set up an external text case:
typically this will be an implementation of the algo in question, and it 
will be fed in a large amount of simulated (or actual, if available) data.

this way, one can see how well the algo is working, and one can try out new 
possibilities and twiddle the details and measure the results...

(this is actually how I originally noticed the somewhat different behavior 
between ordinary and mersenne primes: they showed up differently in the 
performance measurements and statistical analysis tests, ...).


> Just my $0.02. 


0
Reply cr88192355 (1928) 6/14/2009 9:17:21 PM

"cr88192" <cr88192@hotmail.com> wrote in message 
news:h13pd2$f6t$1@news.albasani.net...
>
> "Nate Eldredge" <nate@vulcan.lan> wrote in message 
> news:863aa2db03.fsf@vulcan.lan...
>> "Malcolm McLean" <regniztar@btinternet.com> writes:
>>
>>> "Tony" <tony@my.net> wrote in message
>>>>
>>>> Hash tables are not "damn near one of the simplest things to 
>>>> implement".
>>>> Anyone who thinks so has surely never implemented one of any generality 
>>>> or
>>>> applicability.
>>>>
>>> The problem is getting a nice interface, efficiency, and generality. 
>>> Often
>>> it is handy to have the keys as strings, for instance, but not always.
>>> Sometimes you want to store objects and sometimes pointers, and you 
>>> don't
>>> want to store pointers as objects because that entails inefficient byte 
>>> by
>>> byte copying.
>>>
>>> However the actual hash table logic isn't too difficult.
>>
>> But there are a lot of choices.  How do you handle collisions?
>> Do you put a linked list at each entry of the hash table?  Do you do
>> linear or quadratic probing?  What will you use for a hash function?
>> The best option in each case may depend on knowing something about your
>> data set, and a wrong choice may unexpectedly give pathological behavior.
>>
>
> well, typically not worse than a linear search, unless the implementation 
> is really bad...
>
>
> as for linear and quadratic probing, IMO, both are lame, so personally I 
> use neither...
> usually, I use psuedo-random probing...
>
> since each key ends up calculating a (generally) unique hash value, the 
> psuedo-random sequence is typically different for each input key, and as 
> such, the usual bad behavior of linear probing is often avoided.
>
> of course, typically after some N probes, one either has to resize the 
> table, or do a linear scan (but, of course, by the time one is doing a 
> linear scan one can safely conclude that the table is either full or 
> almost entirely full, and so by this point I normally fallback to whatever 
> the "table is full" behavior is...).
>
>
> as for hash functions, for most input data I have found primes-based 
> polynomial hashing to be most effective, and in general, it is relatively 
> flexible and forgiving (vs the more popular shifts&xors, which typically 
> work well for one piece of data and suck for another...).
>
> there are slight variations though related to the size and type of the 
> prime (mostly related to approximate hash table size).
>
> I usually have the tables themselves at either power-of-2 sizes, or may 
> expand via a factor of 1.5^x.
>
>
>> I'm not sure that it's so trivial.  In a real application, I wouldn't
>> mind having a linked list implemented by a beginner, but I'd rather use
>> a hash table developed by someone that really knew what they were
>> doing.  So I'd probably prefer to use an established library.
>>
>
> in a "real application", we typically use a profile and optimize whatever 
> is going slow...
> if said hash table is poorly written and bogs down the app, it will 
> typically show up on the profiler, and if it does not, it is either 
> working well or is not being used enough to matter...
>
>
> if it really matters that it works well, set up an external text case:
> typically this will be an implementation of the algo in question, and it 
> will be fed in a large amount of simulated (or actual, if available) data.
>
> this way, one can see how well the algo is working, and one can try out 
> new possibilities and twiddle the details and measure the results...
>
> (this is actually how I originally noticed the somewhat different behavior 
> between ordinary and mersenne primes: they showed up differently in the 
> performance measurements and statistical analysis tests, ...).
>
>

You proved my point quite well: creating hashtables is an order of magnitude 
more difficult than creating a linked list and one is hardly likely to get 
it right the first time or even to produce something not laughable by the 
initiated in a week's time (a month? evolved over years?). 


0
Reply tony422 (386) 6/18/2009 10:29:32 PM

"cr88192" <cr88192@hotmail.com> wrote in message 
news:h127ck$bro$1@news.albasani.net...
>
> "Tony" <tony@my.net> wrote in message 
> news:0g_Yl.31919$yr3.1342@nlpi068.nbdc.sbc.com...
>> Tor Rustad wrote:
>>> Tony wrote:
>>>
>
> <snip>
>
>>>
>>> the point is not to hold the hash table internally.
>>>
>>>> A container and algorithm library should have cohesiveness
>>>> and developing one container in isolation is a "myopic" approach.
>>>> Finally, a hashtable should not be the first container a noob should
>>>> try to create.
>>>
>>> Every elementary book on algorithms, would most likely discuss this
>>> topic. Reading up on collisions, isn't exactly rocket science.
>>
>> Using or just copying existing hash containers (whether from existing 
>> library or textbook) is hardly the same as doing the required research to 
>> become capable to create something "from scratch". No one is going to sit 
>> down and create their first hashtable and then use it for the rest of 
>> their programming days. The same could of course be said for any 
>> container, but hashtable is, like I have already noted, not trivial 
>> compared to say linked list, though certainly a fixed-size table is 
>> easier to do than a dynamic one.
>
> I am confused by what is meant by this...
>
> hash tables are trivial enough to write, yes...

No, they are not. You and others who have posted in this thread have already 
proven that with your discourse about hashtable parameters and choices.

> but, errm, how will one expect a single hash table to fulfill all their 
> tasks?

No one suggested that. Note that I particularly avoided making that 
impression when I used the words "hashing library" in an earlier post.


0
Reply tony422 (386) 6/18/2009 10:33:43 PM

"Tor Rustad" <bwzcab@wvtqvm.vw> wrote in message 
news:WdudncDB2pj9V6nX4p2dnAA@telenor.com...
> Tony wrote:
>> Tor Rustad wrote:
>>> Tony wrote:
>>>
>>> [...]
>>>
>>>> It will take a few (or a dozen) iterations and use over
>>>> time to settle and be satisfied with some "final" designs. The OP
>>>> may want to take a look at a C++ library for useful algorithms and
>>>> design ideas if that language is not a deterent to him, as those are
>>>> evolved and robust implementations.
>>> Nonsense, OP is familiar with the GNU interface:
>>
>> While the OP asked for a library, I, OTOH, was responding to another 
>> poster's post.
>>
>> Context matters people!
>
> Yes it do, and context here in my book -- was giving advice to OP. :)

Note that newsgroups are threaded discussion groups where the hiearchy and 
quoting shows what is being responded to. Stop playing childish mindgames 
and thereby lowering the S/N.


0
Reply tony422 (386) 6/18/2009 10:37:52 PM
comp.lang.c 29371 articles. 31 followers. Post

33 Replies
100 Views

Similar Articles

[PageSpeed] 52


  • Permalink
  • submit to reddit
  • Email
  • Follow


Reply:

Similar Artilces:

print hash table to disk and reread in hash table
if i have a hash table in elisp, is there a way to save it to disk and reread in when starting emacs? Thanks. Xah =E2=88=91 http://xahlee.org/ =E2=98=84 "xahlee@gmail.com" <xahlee@gmail.com> writes: > if i have a hash table in elisp, is there a way to save it to disk and > reread in when starting emacs? Yes. ...

equal test hash-tables vs nested hash tables
Does anyone have any insight into which is more efficient when the number of elements in the sequence keys is constant? E.g. (gethash '(foo bar) hash) vs (gethash 'bar (gethash 'foo hash)). I have a function I want to memoize on a certain number of arguments, but I don't to cons up a list (or vector) every time I check the table. Thanks, Matt akopa <akopa.gmane.poster@gmail.com> writes: > Does anyone have any insight into which is more efficient when the > number of elements in the sequence keys is constant? E.g. (gethash > '(foo bar) hash) vs (gethash &...

Regular table and hash table
Regular tables in C, such as assays of structs, can hold up to a max. number of elements, which are exactly similar to hash tables. For hash tables, a max. number, like table size needs to be specified before building a hash table. Could someone elaborate on what are major differences between regular and hash tables? Thanks for your comments! alexhong2001 wrote: ) Regular tables in C, such as assays of structs, can hold up to a max. number ) of elements, which are exactly similar to hash tables. For hash tables, a ) max. number, like table size needs to be specified before building a ha...

standard library for hash table storage and hash algorithm
Is there any reasonable standard hash table storage in C on Linux? AFAICT the one in glibc has a data struct where the key and value pairs both have to be null terminated pointers. In my case, that is fine for the key, but I need to store a complex struct as the value and short of doing dangerous things like printing the memory location of the value struct and then recasting it when I want to get to the struct (which I think is dangerous), I don't want to use non-standard libraries. Also, what is a good way to generate a hash from a very large 96bit identifier? the linux/hash.h only does...

User-defined equality/hashing functions in hash tables?
What implementations support user-defined equality/hashing functions for built-in hash tables? Here are the ones I know of: Allegro - :hash-function argument to MAKE-HASH-TABLE CMUCL - DEFINE-HASH-TABLE-TEST function in EXT package SBCL - DEFINE-HASH-TABLE-TEST function in SB-INT package CLISP - DEFINE-HASH-TABLE-TEST macro in EXT package any others? -Peter -- Peter Seibel peter@javamonkey.com Lisp is the red pill. -- John Fraser, comp.lang.lisp Peter Seibel <peter@javamonkey.com> writes: > > any others? LispWork...

Hash tables
Knuth (AoCP 6.4) more or less waves away the `open hashing' strategy, where you resolve conflicts by allocating a linked list outside the hash table. He devotes almost all of that section to `closed hashing', investigating linear probing and chaining as ways of storing the conflicting items elsewhere in the table. Personally, I don't see the problem with open hashing. So, was closed hashing born of necessity in the days when memory was at a premium and you needed to keep track of every last byte yourself? What's used these days? V. Victor Eijkhout <victor@eijkhout.net&g...

Hash Table
Hi everybody ! I am a beginner in C++. I am looking for a (simple if it's possible) source code in C++ about hash table... Thank you ! Pelo "Pelo GANDO" <o0593m@hotmail.com> wrote in message news:c1uuc4$bnn$2@news-reader1.wanadoo.fr... > Hi everybody ! > > I am a beginner in C++. I am looking for a (simple if it's possible) source > code in C++ about hash table... > > Thank you ! > > Pelo > > [quote - Josuttis' STL Reference Book] 6.7.3 Hash Tables One important data structure for collections is not part of the C++ standard lib...

Hash table
hi,I want to know how can i retrive a key from the given value from ahash table?suppose my table conatins:KEY VALUE1 32 103 124 15if i have value 10 how do i get its corresponding key?? ruds wrote:> hi,> I want to know how can i retrive a key from the given value from a> hash table?> suppose my table conatins:> KEY VALUE> 1 3> 2 10> 3 12> 4 15> if i have value 10 how do i get its corresponding key??The same way you knew where to insert the other values into your hash?...

Hash tables
Hi, I made a hash table that usually holds less than 1000 entries, and the keys are text strings of 5-10 characters. Would a decent hash function be to just generate a 10 bit remainder by feeding the text into a 10 bit shift register which does a crc long division on it, then using that to index a 1024 entry array? (i'll use a maximal length generator polynomial) Russell Shaw <rjshawN_o@s_pam.netspace.net.au> writes: > Hi, > > I made a hash table that usually holds less than 1000 entries, and the > keys are text strings of 5-10 characters. > > Would a decent has...

hash table...again
first of, i'd like to excuse myself for writing in this group, even though i know this is not a standard C++ question. i've written to microsoft.public.dotnet.lang.vc but no one seems to be answering me, and it's pretty urgent. any way, i have something like this: hash_map<double, int> mapa; double md = 0; for(int j=0;j<1000000;++j) { mapa[md] = 3; md++; } as you can see, i'm simply trying to hash a lot of data. my problem is that this uses up 70 MB of memory,which seems to me a bit too much. any ideas what went wrong? again, sorry for being offtopic -- ...

hash table
Here's what I am trying to write a simple hash table: struct Employee { char name[30]; int id; char department[10]; float salary; }; struct Employee *hash_array[MAX_SIZE]; hash_array[n] = (struct Employee*)malloc(sizeof(Employee)); strcpy(*hash_array[n].name, "John Smith"); *hash_array[n].id = 1234; *hash_array[n].department = "Marketing"; *hash_array[n].salary = 4000; .... hash_array will contain all the pointers pointing to each object of Employee type. My questions are: How to determine MAX_SIZE above? How to calculate index, n, to locate an appropriate arr...

about hash table
I want to use hash table in C. Have any build-in library in C so that I can use it without implement hash table myself? Thx Yat wrote: > > I want to use hash table in C. > Have any build-in library in C so that I can use it without > implement hash table myself? <http://cbfalconer.home.att.net/download/hashlib.zip> -- Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net) Available for consulting/temporary embedded and systems. <http://cbfalconer.home.att.net> USE worldnet address! On Wed, 18 Feb 2004 23:39:04 +0800, in comp.lang.c , "Yat&q...

hash table
Hi everyone, I tried to create a hashtable in VxWorks by using hashTblCreate(). I am unable to do so. when i run the application in simulator it returns fatal exception. please help me how to write an application for it. if anyone can write a simple application for me to tell the flow of the application. thanx. On Dec 10, 3:07 pm, ais...@gmail.com wrote: > Hi everyone, > I tried to create a hashtable in VxWorks by using hashTblCreate(). I > am unable to do so. when i run the application in simulator it returns > fatal exception. > please help me how to write an application for ...

Hash table
I'm looking for a Free Software Ada95 container library, or in particular, a hash table (or associative list). I noticed that Ada 2005 may include a standard Ada.Containers library, but is there a working prototype of this available now? A bit of searching found the ASL (Ada Structured Library -- http://sourceforge.net/projects/adasl), which hasn't had a new release since 2001 (which means it must be perfect ;-)). Should I use ASL, and if I do, will it be completely different from the proposed Ada.Containers standard? I'm using Gnat (3.15p) on Debian Linux. Thanks. David --...

Hash Table
Hello: My question is regarding Hash tables. How would one model a hash table in verilog? Use memory and what about the hashing function? Any Ideas... I'm just curious to what people think. Thank You, Prasun What kind of values would be the input to your hashing function? For synthesizable code you would have to constrain the maximum size of the memory/hash. The hash function would just convert a string (or whatever you are hashing) into a memory address (i.e. your unique key) where your value is stored. For synthesisable RTL code it's likely best to keep thing...

Hash tables
I dont know how can I store and recover data to/from a hash table which values are arrays. Is it OK? my %data = (); my @attributes = (); for($counter=1;$counter<@field;$counter++){ $attr = <DB>; push(@attributes, $attr); } $data{$node} = @attributes; $node = <DB>; } I cant recover the values stored in the hash table Guillermo wrote: > I dont know how can I store and recover data to/from a hash table > which values are arrays. perldoc perlreftut perldoc perlref I don't understand what the code you posted is supposed to do, but I noticed that you tr...

Hash Tables
This message is in MIME format. Since your mail reader does not understand this format, some or all of this message may not be legible. ------_=_NextPart_001_01C3E5F7.95E57D11 Content-Type: text/plain Hi, Could anyone explain to me exactly what happens when you perform a hash join between multiple tables. The Informix doc I have read only references a two table join. It says that a hash table is built of the driving table and matched against hash values of the second table. What happens if there is a third and fourth table? Would more than one hash table be bui...

hash table
i'm using the hash below to accomplish a merge. there is no merge statement, hence no alias names to indicate what's in what. i'd like to modify the code below to do the following (separately, of course): say i have two tables, A and B. 1) keep everything in A but drop anything in A and B or in B only 2) keep everything in A and A and B but exclude anything in B only i suspect setting up some kind of flag is the solution but i'm not exactly sure how to do it in a hash. thanks data sasdata.&repeat (keep=pos_card_cust_name pos_trans_key ...

Who uses SRFI 69 or R6RS hash tables with arbitrary hash functions?
I'd like to hear from Schemers who make use of hash tables, either the SRFI= 69 or the R6RS flavor, that need to go beyond the classic five equivalence= predicates, namely `eq?`, `eqv?`, `equal?`, `string=3D?`, and `string-ci= =3D?`. When do you use them? What equivalence predicates do you use? Wha= t hash functions accompany them? Note that in SRFI 69, you can use the `hash` hash procedure for `eqv?` as w= ell as `equal?` hash tables, and in R6RS, you can use the `equal-hash` hash= procedure for `string=3D?` as well as `equal?`. John Cowan writes: > I'd like to ...

Recommended Way to Produce =?ISO-8859-1?Q?=A3_=28Pounds_Ster?= =?ISO-8859-1?Q?ling=29?=
I was wondering what the ``right'' way to produce this symbol is. If I am in a serif font, $\pounds$ seems to work, but produces a very old-fashioned-looking symbol (italicised). In a sans-serif font, I just get an italicised dollar sign. (I'm using cmrm and cmss.) Is there a CTAN package to produce the right symbol, so that it matches the current font (serif or sans-serif)? Thanks in advance for any advice you can give, -- M. Tylee Atkinson <M.T.Atkinson@lboro.ac.uk> On 08-08-2007 15:19, M. Tylee Atkinson wrote: > I was wondering what the ``right'' w...

recommend a B size, A3 size, =?ISO-8859-1?Q?=2C13=D719_inch_?= =?ISO-8859-1?Q?printer=3F?=
Does anyone here recommend a B size, A3 size, 13�19 inch printer? I would prefer to have a color laser but those are prohibitively expensive. So I have been looking at an inkjet, the Canon Pro 100. Even the paper is expensive! http://www.amazon.com/Canon-PRO-100-Professional-Inkjet-Printer/dp/B0095F5BCS/ Thanks, Lynn From: "Lynn McGuire" <lmc@winsim.com> > Does anyone here recommend a B size, A3 size, > 13�19 inch printer? I would prefer to have a > color laser but those are prohibitively > expensive. So I have been looking at an inkjet, > t...

=?ISO-8859-1?Q?R=E9p.=20:=20RE:=20wxbase26d=5Fodbc.lib=20not=20g?= =?ISO-8859-1?Q?enerated=20on=20compilation=3F?=
Thank you. wxUSE_ODBC = 1 solved the problem. >>> gtasker@allenbrook.com 05/02 12:08 pm >>> Have you edited your setup.h file to set wxUSE_ODBC = 1 ? Be sure you edit all appropriate setup.h files in your entire wxWidgets directory structure g > -----Original Message----- > From: Hubert Talbot [mailto:Hubert.Talbot@criq.qc.ca] > Sent: Monday, May 02, 2005 11:37 AM > To: wx-users@lists.wxwidgets.org > Subject: wxbase26d_odbc.lib not generated on compilation? > > Hello, > > Maybe the title of my first message (compiling err...

post into hash table
I'm trying to put values (from form) posted by post method into hash table, but all entries after code execution are empty (i.e. $FORM_DATA{$forename} equals ""). Why? read(STDIN,$query,$ENV{'CONTENT_LENGTH'}); @kv_pairs = split(/\&/, $query); foreach $key_value (@kv_pairs) { ($key, $value) = split ( /\=/, $key_value); $value =~ tr/+/ /; $value =~ s/%([\dA-Fa-f][\dA-Fa-f])/chr(hex($1))/eg; $FORM_DATA{$key} = $value; } What's wrong? -- Bremse Bremse wrote: > I'm trying to put values (from form) posted by post method into hash > table, but...

Array as hash tables
Hello, It is common knowledge that arrays can be used as hashtables: var color = []; color["red"] = 0xFF0000; color["blue"] = 0x0000FF; With this, I can check whether a string identifies a color, or not: function isColor(string) { return color[string] == undefined; } My only concern is that isColor("pop") == true and that will hold true for quite a few annoying, parasitic, "keywords" ("constructor", "length", etc...) I finally came to use the following as a naked object, to use as a hashtable: ...