Re: C Hashmap implementation

Christopher Diggins <>
26 Apr 2007 09:39:01 -0400

          From comp.compilers

Related articles
C Hashmap implementation (bison) (2007-04-23)
Re: C Hashmap implementation (Vladimir Makarov) (2007-04-25)
Re: C Hashmap implementation (cr88192) (2007-04-26)
Re: C Hashmap implementation (bison) (2007-04-26)
Re: C Hashmap implementation (Christopher Diggins) (2007-04-26)
Re: C Hashmap implementation (George Neuner) (2007-04-26)
Re: C Hashmap implementation (Gene) (2007-04-26)
Re: C Hashmap implementation (Bernhard Roessmann) (2007-04-26)
Re: C Hashmap implementation (Hans-Peter Diettrich) (2007-04-27)
Re: C Hashmap implementation (Hans-Peter Diettrich) (2007-04-27)
| List of all articles for this month |

From: Christopher Diggins <>
Newsgroups: comp.compilers
Date: 26 Apr 2007 09:39:01 -0400
Organization: Compilers Central
References: 07-04-089
Keywords: symbols
Posted-Date: 26 Apr 2007 09:39:01 EDT

On Apr 23, 4:52 am, bison <> wrote:
> Hello. I'm looking into hashmap implementations for a VM based
> dynamically typed language. Since the implementation must allow me to
> resize on demand, I am a bit confused about the various approaches.
> Here is what I have found out so far:
> Almost everyone I've talked to has said that Chained Hashmaps are much
> easier to implement than Open Addressed maps.
> Wikipedia suggests that an approach to resizing hashmaps is to
> allocate space for a newer hashmap and copy elements from to the new
> table, and in some cases do it incrementally.

Another approach is to implement a Hash using a VList ( ).

It allows you to avoid moving elements, and has an average case of
O(1) time when hashing, with a worst case upper-bound of O(log(N)).

A public domain implementation of a Hash list in C++ (called ootl_map)
using a VList is available at

> Quick question about the last point: I'm curious about a starting
> point. How much space should a hashmap allocate initially, and when
> it's how much would I typically increase it?

The VList approach is to start with whatever value but simply keep
increasing by a factor of two, and linking to the previous hash-list
once you create a new one. This gives you constant time complexity for
indexing, if you don't find the item in the first list, you look in
the next list, then the next list, and so-on. If you don't find the
item it takes O(logN) time, but for items present the average time

Christopher Diggins

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.