Re: [boost] [Tokenmap] A (perfect) hash container library chcked-in to sandbox (RFC)

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.