Subject: Re: [boost] [Tokenmap] A (perfect) hash container library chcked-in to sandbox (RFC)
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-02-21 21:05:57
I think that there is a problem with the `find` and `pop` members of
`tokenmap`: in `find_free_slot`, which is used by the `insert` member,
you apply collision resolution to find an unused element of `store_` where
the new element can be inserted, but the `find` and `pop` members do not
employ a loop when looking up the given key (to account for the
possibility that they key resulted in a collision when it was inserted).
It could be, for example, that the element of the given key was placed at
`ix + 3` by `find_free_slot`, in which case `find` and `pop` would fail to
find the element. Also, there are some improvements that can be made:
supporting an allocator type and getting rid of the floating-point
arithmetic around where you check whether a doubling of the capacity can
succeed (lines 175-176; you can use the `max_size` member of `std::vector`
and halve the result, rather than double `store_.capacity()`).
By the way, you might be interested in taking a look at the JDK
implementation of Java's `java.util.HashMap` class because the bucketing
strategy, and the use of an underlying array for storage, is very similar.