How are hash tables implemented internally in popular languages?

c hashtable
CDR picture CDR · May 24, 2009 · Viewed 8.4k times · Source

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.

Answer

zvr picture zvr · May 24, 2009

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.

Related questions

hash function for string

I'm working on hash table in C language and I'm testing hash function for string. The first function I've tried is to add ascii code and use modulo (%100) but i've got poor results with the first test of data: 40 collisions …

Read More
Super high performance C/C++ hash map (table, dictionary)

I need to map primitive keys (int, maybe long) to struct values in a high-performance hash map data structure. My program will have a few hundred of these maps, and each map will generally have at most a few thousand …

Read More
Simple hash functions

I'm trying to write a C program that uses a hash table to store different words and I could use some help. Firstly, I create a hash table with the size of a prime number which is closest to the …

Read More