Solved

How to use this hash table

Posted on 2008-06-23
7
358 Views
Last Modified: 2010-04-15
Hi experts,

I am researching hash functions on http://www.burtleburtle.net/bob/c/lookup3.c. Assume that I use hash function hashlittle() and I have some key words like "this", "is", "yahoo",  can somebody give me an example how to put these keywords into hash and then retrieve them from hash?

Thanks a lot!
0
Comment
Question by:davidw88
  • 3
  • 3
7 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 21850813
That source code just offers several ways of generating a hash value. It doesn't actually implement a hash table.

If what you're looking for is simply how to generate a hash for a keyword, then that could be :

const char *keyword = "Yahoo";
uint32_t hash = hashlittle(keyword, strlen(keyword), 0x12345678);

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 21850817
>> and then retrieve them from hash?

A hash is one-way - ie. you can't get the "Yahoo" keyword out of the hash.
0
 

Author Comment

by:davidw88
ID: 21851098
hi I8,

Thanks so much for your clarification. Yes, they are just hash functions creating hash values. hashlittle(...) may generate either positive or nagative values.

When I said "hash", I actually meant "hash table". I should be more accurate in future.

Now I need to save this information "this", "is", "yahoo" so that later I can check. With these hash function values, I would like to implement a hash table. Do you have any suggestions on how to do this? especially how to handle the nagative hash function values?

Thanks again.
0
Comprehensive Backup Solutions for Microsoft

Acronis protects the complete Microsoft technology stack: Windows Server, Windows PC, laptop and Surface data; Microsoft business applications; Microsoft Hyper-V; Azure VMs; Microsoft Windows Server 2016; Microsoft Exchange 2016 and SQL Server 2016.

 

Author Comment

by:davidw88
ID: 21851226
Just a general guess: If I implement a hash table, can the overhead of this hash table beat the overhead of the hash table from Gnome Library?

This is what I conern. If it can not, then it is meaningless to implement a hash table. From my experience, I found the hash table from GLib really has a very heavy overhead.

Any ideas?
0
 

Author Comment

by:davidw88
ID: 21851254
Now that I know how to implement a hash table, I just wonder if it is worth to do so. At this time I use GLib hash tables.

I appreciate all replies and comments.

Thanks so much.
0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 125 total points
ID: 21852449
I haven't used glibc hash tables, I use custom implementation. You can begin by simply replacing the hash function being used ... If that does not help, you can probably try replacing the hash tables. Ideally hash tables should not be the pain point.

It would be a very good idea to profile your program and the hashing (if possible). That would give a very clear idea as to where you should be spending your energies .... no point in rewriting the hash tables when your bottleneck is say your search collation function
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 125 total points
ID: 21852785
These hash functions you posted return 32bit hash values. For use in a hash table, that might not be very handy (unless you take into account only a part of the hash value to fit the size of your hash table).


>> If I implement a hash table, can the overhead of this hash table beat the overhead of the hash table from Gnome Library?

Yes, because you can make a specifically tailored hash table that is optimized for your situation. Any common hash table implementation is done for general purposes, thus likely less efficient in the specific case.
0

Featured Post

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

831 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question