473,387 Members | 1,535 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,387 software developers and data experts.

Perfect hash tables

Everybody knows that hash tables are fast.

What is less known is that perfect hash tables are even faster.
A perfect hash table has a hash function and a table layout that
avoids collisions completely. You can lookup a key in the table
with a single hash function call.

What is even less known is that there is a perfect software
for generating perfect hash tables called "gperf" offered by
GNU INC.

This software will take a bunch of strings (the keys), and generate
a hash table layout and a hash function for it in C. You add
the generated file to your project and you gain a LOT of speed
with static table lookups. This is very useful for tables that
are known in advance of course, since you can't modify the
perfect hash table at run time by adding or deleting elements.

What is even less known, is that you can hack gperf to generate
code to call a function of you directly instead of returning the
character string...

I used that last twist in an assembler I wrote for the PowerPC
AIX system earlier this year. The hacked gperf output called
directly the function "add" when it saw the opcode "add",
making for an incredible fast lookup.

Gperf is easy to hack, it is just C (with some C++ crafted to it
but this happens even in the best families) ...

Gperf is a very good solution for static tables. It can mean a lot when
you have a performance bottleneck in a table lookup.

Recommended!

jacob
Aug 30 '07 #1
1 3393
"jacob navia" <ja***@jacob.remcomp.frwrote in message
news:46***********************@news.orange.fr...
Everybody knows that hash tables are fast.

What is less known is that perfect hash tables are even faster.
[...]
Gperf is a very good solution for static tables. It can mean a lot when
you have a performance bottleneck in a table lookup.

Recommended!
[...]

Indeed.

Aug 31 '07 #2

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: Pelo GANDO | last post by:
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
22
by: VK | last post by:
A while ago I proposed to update info in the group FAQ section, but I dropped the discussion using the approach "No matter what color the cat is as long as it still hounts the mice". Over the last...
12
by: wxs | last post by:
Many times we have a bunch of enums we have from either different enums or the same enum that will have various numeric values assigned. Rarely will there be collisions in numbering between the...
2
by: Ravi | last post by:
Hi, I am working on a winform app. I need to use an object which can store some information(key/value pairs) and also can be acessed by multiple threads(read/write). From what I heard Hash table...
21
by: Johan Tibell | last post by:
I would be grateful if someone had a minute or two to review my hash table implementation. It's not yet commented but hopefully it's short and idiomatic enough to be readable. Some of the code...
12
by: shaanxxx | last post by:
I wanted to write hash function float or double. Any suggestion would be appreciated.
6
by: fdmfdmfdm | last post by:
This might not be the best place to post this topic, but I assume most of the experts in C shall know this. This is an interview question. My answer is: hash table gives you O(1) searching but...
139
by: ravi | last post by:
Hi can anybody tell me that which ds will be best suited to implement a hash table in C/C++ thanx. in advanced
2
by: bearophileHUGS | last post by:
Following links from this thread: http://groups.google.com/group/comp.lang.python/browse_thread/thread/179e1a45485ab36a# I have found this perfect hash (minimal too) implementation:...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.