Re: C Hashmap implementation

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

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