ISO recommendations for hash table lib



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
no.email5 (314)
6/12/2009 4:23:30 PM
comp.lang.c 29955 articles. 1 followers. spinoza1111 (3247) is leader. Post Follow

33 Replies
169 Views

Similar Articles

[PageSpeed] 8
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
tony422 (386)
6/18/2009 10:37:52 PM
Reply:
Similar Artilces:

DiscretePlot and difference tables; trying to offset bars
I've finally got bars charted to show the differences, but I'd like to offset them from the original function values. Also, I'm getting a divide-by-zero error somehow. I think it came in with the second DiscretePlot. DynamicModule[ { f = x, a = 0, b = 6 }, Grid[ { {InputField[Dynamic[f]]}, {InputField[Dynamic[a], Number]}, {InputField[Dynamic[b], Number]}, {Grid[{ { (* A row with the graph on the left and the difference table on \ right *) Dynamic[ Show[{ DiscretePlot[ f, {x...

=?ISO-8859-1?Q?immobilienfinanzierung_schweiz=2Czins=FCbersicht_baufin?= =?ISO-8859-1?Q?anzierung=2Cbaufinanzierung_angebote=2Ceigenheimzulagengesetz=2Cha?= =?ISO-8859-1?Q?us_kaufen_darlehen=2Ch
immobilienfinanzierung schweiz,zins=FCbersicht baufinanzierung,baufinanzierung angebote,eigenheimzulagengesetz,haus kaufen darlehen,hypotheken diskount,kredit aufs haus,hausfinanzierung =FCber lebensversicherung,zur immobilienfinanzierung, + + + + +++ GUENSTIGE KREDITE ONLINE +++ KREDITE IM INTERNET OHNE SCHUFA +++ + + http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NE...

=?ISO-8859-1?Q?Error:_Couldn't_open_file_=9165280'_Failed_close_on_p?= =?ISO-8859-1?Q?ipe_to_pdfinfo_for_65280:_256_at_pdf2xml.pm_line_129?=
I have been attempting to use the pdf2xml program without any success. I am running SWISH-E on a Linux 7.3 OS and copied a program (first item immediatelly below) from www.linuxjournal.com/articles.php?sid=6652 which uses this program to index the PDF files. The SWISH-E program works properly from both a browser and the command line when indexing regular text files. (howto-pdf-prog.pl file) #!/usr/bin/perl -w use pdf2xml; my @files = system (�find /var/www/html/ccsp/docs/ -name *.pdf -print�); for (@files) { chomp(); my $xml_record_ref = pdf2xml($_); print $$xml_record_ref; } The following...

=?iso-8859-15?Q?Re:_[Uniface-L]_icomp_parameter_to_append_to_file_when?= =?iso-8859-15?Q?_exporting_data=3F?=
Hi, in $uuu, it is described as "supersede" ($96). Success, Uli > -----Urspr=FCngliche Nachricht----- > Von: Uniface User Group Discussion Forum <uniface-l@uug.org> > Gesendet: 05.06.06 21:34:35 > An: uniface-l-gate@lists.umanitoba.ca > Betreff: [Uniface-L] icomp parameter to append to file when exporting da= ta=3F > Hi All, >=20 > Does anyone know if there is an icomp parameter $9x for function 300 > exporting data that will append the data to a file. I have checked $UUU= but > no luck. >=20 > Thanks in advance. &...

equiv of border=1 in table
Hi All Wondered if you could let me know if I've missed something when setting up a table. If I use the following: <TABLE WIDTH=500 BORDER=1> <TR><TD>fred</TD></TR> <TR><TD>fred</TD></TR> <TR><TD>fred</TD></TR> <TR><TD>fred</TD></TR> </TABLE> All 4 sides of all of 4 table cells have a border 1 pixel in depth - perfect! If I change this to: <TABLE WIDTH=500 STYLE="border: 1px dashed black"> <TR><TD>fred</TD></TR> <...

FAQ 3.18 How can I free an array or hash so my program shrinks? #18
This is an excerpt from the latest version perlfaq3.pod, which comes with the standard Perl distribution. These postings aim to reduce the number of repeated questions as well as allow the community to review and update the answers. The latest version of the complete perlfaq is at http://faq.perl.org . -------------------------------------------------------------------- 3.18: How can I free an array or hash so my program shrinks? (contributed by Michael Carman) You usually can't. Memory allocated to lexicals (i.e. my() variables) cannot be reclaimed or reused even if they ...

=?iso-2022-jp?B?GyRCIiEbKEJ3aXRoIGdyZWE=?= =?iso-2022-jp?B?dCBzZXJ2aWNlIA==?= =?iso-2022-jp?B?LCB3ZSBncm93IA==?= =?iso-2022-jp?B?LCB3ZSBhY2hpZQ==?= =?iso-2022-jp?B?dmUhGyRCIiEbKEJqZXN1cxskQiF6GyhC?=
--_596c8893-e5fe-42e2-8030-47c14da69650_ Content-Type: text/plain; charset="iso-2022-jp" Content-Transfer-Encoding: 7bit Dear! what's going on? I'd like to share a good online shopping experience with you. [[[[ www.li-xiao4$B!#(Binfo ]]]] is a top online store. It sells brand new phones, TV ,camera and so on. the quality is very good. I can't believe my eyes when I receive the apple phone, it is really original, the product has high quality and good after-sales service. Hope you will not miss this valuable chance! We solicit a continuance o...

=?ISO-8859-1?Q?=BFcomo_dividir_varios_objetp?= =?ISO-8859-1?Q?os_a_la_vez_en_autocad_2002=3F?=
Hola!! Tengo un plano con cotas cada 5 metros y estoy haciendo las cotas cada metro haciendo perpendiculares entre las cotas y dividiendolas en 5 para luego unir esos puntos y conseguir las demas lineas de cota. El problema es que no se dividir varias lineas a la vez y me est� costando mucho hacer un trabajo que es sencillo. Doy al comando dividir y luego me pone seleccione objeto pero no me da opci�n a seleccionar varios. Alguien sabe como hacerlo??? o si hay otra manera de hacer lo mismo?? Gracias Si fesais la traducci�n del espa�ol hacia el ingl�s seguramente que alg�n uno del g...

homebuild NAS recommendations
Hi, I'm in need for (budget) storage at home. After doing a little research i decided to build my own NAS server. I've got an "old" AMD Athlon XP 2400+ with one GB of ram, so that will be more than sufficient i guess. I've been thinking of doing the following, but i wonder if it's the best way to do it: - I can use the onboard IDE or SATA port to setup a mirrored OS (two small drives). - I'll add an 8 port SATA Raid controller, for example the FastTrak SX8300 from Promise Technology to store all data in RAID5. I can attach 8x 250GB discs ...

=?ISO-8859-1?Q?baufinanzierung_2=2Cbaufinanzierung_=F6sterreich=2Cimmobi?= =?ISO-8859-1?Q?lienkredit_von=2Chypothekenkredit_zinssatz=2Cimmobilienfinanzier?= =?ISO-8859-1?Q?ung_schweiz=2C?=
baufinanzierung 2,baufinanzierung =F6sterreich,immobilienkredit von,hypothekenkredit zinssatz,immobilienfinanzierung schweiz, + + + + +++ GUENSTIGE KREDITE ONLINE +++ KREDITE IM INTERNET OHNE SCHUFA +++ + + http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONLINE.NET http://WWW.IMMOBILIEN-KREDIT-ONL...

ISO 8061 suggestions
Lucho: Following a mention by Klaus Meinhard in alt.msdos.batch, I spent a few hours testing your new ISO 8061 functions. They work correctly as intended, but I have a couple of suggestions. First off, you have functions @ISODOWI and @ISOWEEK to return the day- of-week number and week number for an arbitrary date, but there's no corresponding @ISOWYEAR (or whatever) to return the year value, which can differ from the actual year. Second, there really ought to be an @ISOWDATE function corresponding to _ISOWDATE for an arbitrary input year. Doing the date calculations once ...

Recommend/survey graph, chart module space?
While looking for a chart module, I see a very large number to choose from. Is there a pointer to a guide, or do folks have recommendations, on how to evaluate and select the most appropriate from the *::Graph* and *::Chart* modules? My application is fairly simple: line graphs with multiple data series and multiple axes. I have external requirements to make it look like it came out of a pretty graphics workbench. I'm generating graphs automatically on the fly each time the data changes. Our data are time series, so we want to control the X axis range (the graph always shows the entire...

=?ISO-8859-1?Q?Eine_Fu=DFnote_aus_BibDesk_erscheint_pl=F6tzlich_nicht?= =?ISO-8859-1?Q?_mehr=2E?=
Hallo, ich habe beim letzen =DCberarbeiten meiner Diss jetzt pl=F6tzlich das Probl= em, dass ich keine neuen Literaturangaben aus BibDesk mehr in meine Arbeit = bekomme. Wenn ich einen neuen Eintrag in BibDesk anlege, speichere, alle au= x-Dateien l=F6sche und das Dokument in TeXShop neu "setze", erscheint von d= em neuen Eintrag nur der citekey, nicht der eigentliche Eintrag. Ich bekomm= e diese Fehlermeldung: Output written on "Dissertation Dittmers .pdf" (219 pages, 15371939 bytes). SyncTeX written on "Dissertation Dittmers .synctex.gz" Transcript ...

TechnoMarine Butterfly Diamond Ladies Watch DLRFD01 Recommendation Discount Watches
TechnoMarine Butterfly Diamond Ladies Watch DLRFD01 Recommendation Discount Watches TechnoMarine Butterfly Diamond Ladies Watch DLRFD01 Site: http://technomarine-watches.pxhelp.com/Technomarine-wristwatch-7299.html Thank you for choosing http://www.pxhelp.com/ Quality Technomarine Watches: http://technomarine-watches.pxhelp.com/ TechnoMarine Butterfly Diamond Ladies Watch DLRFD01 AdditionalInfo : Watches Brand : Technomarine Watches ( http://technomarine-watches.pxhelp.com/ ) Gender : Ladies Model : technomarine-diamond-ladies-dlrfd01 Also Called : Case Material : ...

=?ISO-8859-1?Q?7_Segredos_para_Criar_uma_Renda_Autom=E1tica_na_Inter?= =?ISO-8859-1?Q?net?=
Mini-curso gratuito por tempo limitado, n=E3o perca esta chance de estudar gratuitamente como criar um neg=F3cio on-line a partir da sua pr=F3pria casa sem investir um =FAnico centavo. Inscreva-se gratuitamente e receba o curso agora mesmo muitas informa=E7=F5es poderosas para seu crescimento pessoal e profissional !. http://dobrandominharenda.webng.com/cursorendaautomatica.html ...

Can someone recommend an editor for 'Windows .ico files?
I need to create 16x16 and 32x32 .ico files for a Tcl/Tk application (I'll load the icons with [wm iconbitmap]). I've used the editor in Visual Studio before and it's fine but I don't have access to it now and I need something else. I've Googled for "icon editor" and such and found nothing promising. I'm hoping someone here will have a recommendation. TIA. Chris Chris Nelson wrote: > I need to create 16x16 and 32x32 .ico files for a Tcl/Tk application > (I'll load the icons with [wm iconbitmap]). I&#...

=?ISO-8859-1?Q?Economics_of_Macro_Issues=2C_7=2FE=2C_Miller_=26_Benjamin_=A9?= =?ISO-8859-1?Q?2016_Prentice_Hall_Estimated_Availability=3A_07=2F15=2F2015_ISBN=2D1?= =?ISO-8859-1?Q?0=3A_0134018958_ISBN
! ! ! TEST BANKS, SOLUTION MANUALS, INSTRUCTOR MANUALS, CASE SOLUTIONS, POW= ER POINT SLIDES ! ! ! Hello Everybody, To get the Solution manuals and Test banks just email me with your book det= ails. My e-mail address is: testbankandsm@xxxxxxxxx, testbankandsm(at)gmail(dot)c= om. Please replace (at) by @ and (dot) by .=20 If you need Test banks and Solution manuals, email to me.=20 http://testbankandsm.blogspot.in/ Reply time: Within 6 hours, If online, immediately!!!! Delivery time: Within 12- 24 hours. If online, immediately after payment ve= rification!!!!!!!!! Having...

Advice on converting hashed packages to pseudo-hashed packages
Does a document exist with the outline below? If so please point me to it... If not, any help would be appreciated: "So, you wrote some object-oriented perl packages and you used hashes for all your objects because your boss wanted results and you stopped reading at page 125 of Conway. Now you found that your code runs horribly slowly and you should have used pseudo-hashes and the 'fields' pragma, but it looks like there's a lot to learn, and you're nervous about trying to convert this code. Here's what to do, and the things you need to watch out for:" Thanks in...

=?ISO-2022-JP?B?TmV3ZXN0IHNwb3J0cyBzaG9lcxskQiEkGyhCZ29sZiwgQWNjZXB0IHBheXBhbCBvciB3ZXN0ZW4g?= =?ISO-2022-JP?B?dW5pb24sQUFBIHF1YWxpdHkbJEIhJBsoQkxvdyBwcmljZS4gd3d3LmFsaWJhYmF1bmlvbi5jb20=?=
Dear fridend Pacific Ocean Trade Co.,LTD greets and desires of success and wishes you happy times. We greated in 2003 year ,and now we become the one of best supplier here because of we keep our credit standing . Pls visit our site For Wholesaler : www.alibabaunion.com MSN alibabaline@hotmail.com MSN pttpymy@hotmail.com Our main products : Fashion shoes: Air Jordan , Air force , Air max , Shox , Dunk , Adidas , Puma , Prada , Chanel , Gucci , Lacoste , LouisVuiton and more . Fashion Hoodies&T-Shirt&Jeans&Jacket: Gino Green Globa , Bape , BBC , Evsiu , Juicy cout...

GSM to ISO / UCS2 to ISO
HI all, In an effort to avoid re-inventing the wheel so to speak I was wondering if anyone's come across libraries/tools, etc that achieve the same kind of functionality as the tools library in this java app. http://code.google.com/p/ipddump/source/browse/trunk/src/ipddump/tools/Gsm2Iso.java Thanks, cheers James -- -- James Mills -- -- "Problems are solved by method" ...

Installation Problems
Hi My machine is having Windows 98 OS with two partitioned drives C and D. I would like to install RedHat Linux 7.1 using Partionless Installation method. There are close to 2.5 GB free space in both drives C and D. I have the installation files of RedHat 7.1 in Hard Disk D:\Linux1 (Installation Set 1 of 2) and Hard Disk D:\Linux2 (Installation set 2 of 2 )copied from 2 installation CDs. During the course of the installation, there comes a stage like Select Partition What partition and directory on that partition hold the CD (iso9660) images for RedHat Li...

How to process DBF table with multiple order (one within another)
Hello All, I am using DBFCDX. How can I process a table with multiple orders like SQL ORDER BY ... statement with a DBF table, where all sorting keys will be INDEXES of the table (CDX). Thanks. :) With best regards. Sudip Dear Sudip Bhattacharyya: On Apr 2, 6:49=A0am, Sudip Bhattacharyya <sudipb...@gmail.com> wrote: > Hello All, > > I am using DBFCDX. How can I process a table with multiple > orders like SQL ORDER BY ... statement with a DBF table, > where all sorting keys will be INDEXES of the table (CDX). You can create an index in the usual way. You can add orde...

Employer looking 4 online C++ aptitude tests; recommendations?
Hello, I'm a hiring C++ developer employer looking for existing, online C++ aptitude tests. I have not yet extensively researched this yet, but as an example, I thought this test looked pretty good: http://expertrating.com/c++test.asp I'm curious if anyone can offer any other recommendations? If so, could you please offer your experience with your recommended resource and why you recommend them...or might recommend others? Fyi, My philosophy falls in line with this post: http://groups-beta.google.com/group/comp.lang.c++.moderated/msg/f840d9074af466c1 -Matt -- Remove the "d...

Need MySQL management tool recommendation
Can someone please recommended a good Windows based MySQL DB management app? Julia Briggs wrote: > Can someone please recommended a good Windows based MySQL DB > management app? If you're running a PHP enabled webserver on the Windows box you can use phpMyAdmin. Also go to http://dev.mysql.com/downloads/ and look under the "Graphical clients" section. -- Chris Hope - The Electric Toolbox - http://www.electrictoolbox.com/ Have a look at MySQL-Front. http://www.mysqlfront.de/ Brent Palmer. "Julia Briggs" <julia4_me@yahoo.com> wrote in message n...

Use other value from table
Hi I want a user to select a name (from a table) from a dropdown box but then use the corresponding email address for that person also stored in the users table in a colmn called email and store in a variable. I'm using a drop down box which gets its values from a table called users. Using SELECT [Users].[Name] FROM Users; I have got my form to email people when i click a button and fill out text boxes but i want the user to only see peoples names and not email addresses. Hope that makes sense. Thanks in advance. <simonmarkjones@gmail.com> wrote in message news:1127909123.681...