Re: C Hashmap implementation

Christopher Diggins <cdiggins@gmail.com>
26 Apr 2007 09:39:01 -0400

          From comp.compilers

Related articles
C Hashmap implementation Sean.Gillespie@bisonofborg.com (bison) (2007-04-23)
Re: C Hashmap implementation vmakarov@redhat.com (Vladimir Makarov) (2007-04-25)
Re: C Hashmap implementation cr88192@hotmail.com (cr88192) (2007-04-26)
Re: C Hashmap implementation Sean.Gillespie@bisonofborg.com (bison) (2007-04-26)
Re: C Hashmap implementation cdiggins@gmail.com (Christopher Diggins) (2007-04-26)
Re: C Hashmap implementation gneuner2@comcast.net (George Neuner) (2007-04-26)
Re: C Hashmap implementation gene.ressler@gmail.com (Gene) (2007-04-26)
Re: C Hashmap implementation roessmann@gmx.net (Bernhard Roessmann) (2007-04-26)
Re: C Hashmap implementation DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-04-27)
Re: C Hashmap implementation DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-04-27)
| List of all articles for this month |

From: Christopher Diggins <cdiggins@gmail.com>
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 <Sean.Gilles...@bisonofborg.com> 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 (
http://en.wikipedia.org/wiki/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 http://www.ootl.org


> 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 full...by 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
O(1).


Christopher Diggins
http://www.cdiggins.com


Post a followup to this message

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