Re: C Hashmap implementation

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