Wait, why does searching for K3 present a problem? It starts at K1 (not ==), moves to K2 (REMOVED, so skip), finds K3 next.
This would be a pretty basic bug, yeah, but I don't think I was that dumb. On Wed, Jan 27, 2010 at 12:17 PM, Dawid Weiss <dawid.we...@gmail.com> wrote: > Sean, > > This is actually a bit tricky, because when retrieving or putting > values in the open table (or map) you must not stop on removed keys > and continue until you either find an empty slot, or a key different > then the one you are looking for. > > The test case is like this here: imagine you have three keys, k1, k2 > and k3 and ALL of them have hash collision on the same slot. This > makes a chain of lookups, for instance: > > slot1 K1 > slot2 K2 > slot3 K3 > slot4 EMPTY > > if you remove K2, this becomes: > > slot1 K1 > slot2 REMOVED > slot3 K3 > slot4 EMPTY > > now, retrieving the value of K3 will return junk in the implementation > you suggest below... which is also a bug in the current implementation > of FastMap, I believe. I think (ehm) I implemented it properly in > HPPC, you can peek in there if you want to. > > As long as you don't mix removes with adds, your implementation runs fine. > > Dawid
