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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk