26 Apr 2007 09:39:01 -0400

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

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.