473,748 Members | 2,300 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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 3418
"jacob navia" <ja***@jacob.re mcomp.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
4254
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
4639
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 month I had enough of extra proof that the cat doesn't hount mice anymore in more and more situations. And the surrent sicretisme among array and hash is the base for it. I summarized all points in this article:...
12
3204
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 enums. These enums you might imagine would be like OrderPrice=27, OrderQuantity=50, OrderSide=62. There may be a lot of these. So normally what we would have to do is store these in hash table so hashtable=value could be set with the value....
2
2526
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 is best suited for it. My question is Why hash table. why can't we use an array. I thought hash table uses more memory than array. Correct me if am wrong.
21
3222
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 (i.e. the get_hash function) is borrowed from various snippets I found on the net. Thee free function could probably need some love. I have been thinking about having a second linked list of all entries so that the cost of freeing is in proportion to...
12
12454
by: shaanxxx | last post by:
I wanted to write hash function float or double. Any suggestion would be appreciated.
6
16877
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 according to your hash function you might take more memory than binary tree. On the contrary, binary tree gives you O(logN) searching but less memory. Am I right?
139
14209
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
3263
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: http://burtleburtle.net/bob/hash/perfect.html I have already translated part of it to D, and it seems to work well enough. As discussed in the PyConDue, I think this may be used in frozenset (and frozendict) to build a (minimal too?) perfect hash on the...
0
9376
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 tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9326
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8245
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6796
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
6076
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4607
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4877
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3315
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2787
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

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.