Re: C Hashmap implementation

Bernhard Roessmann <roessmann@gmx.net>
26 Apr 2007 09:42:44 -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: Bernhard Roessmann <roessmann@gmx.net>
Newsgroups: comp.compilers
Date: 26 Apr 2007 09:42:44 -0400
Organization: Compilers Central
References: 07-04-089
Keywords: symbols
Posted-Date: 26 Apr 2007 09:42:44 EDT

> Almost everyone I've talked to has said that Chained Hashmaps are much
> easier to implement than Open Addressed maps.


I dont think so, open addressed maps are very easy to implement. But
beware of the fill level (see below).


> 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.


If you have enough RAM and resizing occurs infrequently, why not. In an
embedded environment with limited RAM resources and/or without MMU, this
is not really a good idea.


> 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? I realize
> there are lots of different answers here, so a good starting point
> would really help out.


There's a lot of academic stuff about this, but if you want a practical
approach for an open addressed map:
"Nearly full" open addressed hash table maps performs VERY bad, so
estimate the maximum number of elements and use 125% as the hash table
size.




LG,
--
Bernhard Roessmann
Don't Fear The Penguins!


Post a followup to this message

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