26

Can someone please shed some light on how popular languages like Python, Ruby implements hash tables internally for symbol lookup? Do they use the classic "array with linked-list" method, or use a balanced tree?

I need a simple (fewer LOC) and fast method for indexing the symbols in a DSL written in C. Was wondering what others have found most efficient and practical.

3
  • 4
    Perhaps you wish to ask "How are maps implemented..." as a hash table is not the only way to implement a map!
    – Artelius
    May 24, 2009 at 6:57
  • Good comment. But the problem is I have already build the ground work based on calculated hashes of the symbols. BTW, what other ways are maps implemented beside hashes, which I thought everyone uses?
    – CDR
    May 24, 2009 at 9:25
  • 1
    Maps are sometimes also built from binary trees. It's generally used when the key type is unhashable, or you want to preserve a certain ordering of the data in the map (so that you can iterate from A to Z).
    – Crashworks
    May 24, 2009 at 10:26

7 Answers 7

17

The classic "array of hash buckets" you mention is used in every implementation I've seen.

One of the most educative versions is the hash implementation in the Tcl language, in file tcl/generic/tclHash.c. More than half of the lines in the file are comments explaining everything in detail: allocation, search, different hash table types, strategies, etc. Sidenote: the code implementating the Tcl language is really readable.

1
  • Earlier versions of the code are even more readable due to the reduced amounts if ifdeffery, though later versions are more useful in critical ways (supporting key customization and other things like that). Oct 10, 2010 at 6:54
12

Perl uses an array with linked lists to hold collisions. It has a simple heuristic to automatically double the size of the array as necessary. There's also code to share keys between hashes to save a little memory. You can read about it in the dated but still relevant Perl Illustrated Guts under "HV". If you're truly adventurous you can dig into hv.c.

The hashing algorithm used to be pretty simple but its probably a lot more complicated now with Unicode. Because the algorithm was predictable there was a DoS attack whereby the attacker generated data which would cause hash collisions. For example, a huge list of keys sent to a web site as POST data. The Perl program would likely split it and dump it into a hash which then shoved it all into one bucket. The resulting hash was O(n) rather than O(1). Throw a whole lot of POST requests at a server and you might clog the CPU. As a result Perl now perturbs the hash function with a bit of random data.

You also might want to look at how Parrot implements basic hashes which is significantly less terrifying than the Perl 5 implementation.

As for "most efficient and practical", use someone else's hash library. For god's sake don't write one yourself for production use. There's a hojillion robust and efficient ones out there already.

8

Lua tables use an utterly ingenious implemenation which for arbitrary keys behaves like 'array of buckets', but if you use consecutive integers as keys, it has the same representation and space overhead as an array. In the implementation each table has a hash part and an array part.

I think this is way cool :-)

4

Attractive Chaos have a comparison of Hash Table Libraries and a update. The source code is available and it is in C and C++

4

Balanced trees sort of defeat the purpose of hash tables since a hash table can provide lookup in (amortized) constant time, whereas the average lookup on a balanced tree is O(log(n)).

Separate chaining (array with linked list) really works quite well if you have enough buckets, and your linked list implementation uses a pooling allocator rather than malloc()ing each node from the heap individually. I've found it to be just about as performant as any other technique when properly tuned, and it is very easy and quick to write. Try starting with 1/8 as many buckets as source data.

You can also use open addressing with quadratic or polynomial probing, as Python does.

2
  • logarithmic defeat constant time? May 24, 2009 at 7:01
  • 1
    @tydok - to "defeat the purpose" means to fail to meet whatever objective the other solution meets, so it means "worse than", not "better than". May 24, 2009 at 7:40
2

If you can read Java, you might want to check out the source code for its various map implementations, in particular HashMap, TreeMap and ConcurrentSkipListMap. The latter two keep the keys ordered.

Java's HashMap uses the standard technique you mention of chaining at each bucket position. It uses fairly weak 32-bit hash codes and stores the keys in the table. The Numerical Recipes authors also give an example (in C) of a hash table essentially structured like Java's but in which (a) you allocate the nodes of the bucket lists from an array, and (b) you use a stronger 64-bit hash code and dispense with storing keys in the table.

1
  • In Java, TreeMap is implemented based on Red-BlackTree, ConcurrentSkipListMap is implemented based on SkipList.
    – coderz
    Mar 25, 2015 at 14:03
1

What Crashworks mean to say was....

The purpose of Hash tables are constant time lookup, addition and deletion. In terms of Algorithm, the operation for all operation is O(1) amortized. Whereas in case you use tree ...the worst case operation time will be O(log n) for a balanced tree. N is the number of nodes. but, do we really have hash implemented as Tree?

2
  • Thanks for pointing out my inclarity -- I've fixed my answer.
    – Crashworks
    May 24, 2009 at 7:28
  • 3
    A hash implemented as a tree is a tree with a hash-like API on the front.
    – user82238
    May 24, 2009 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.