> This is rather cache-friendly, so it seems like a Good Thing to me. Yes indeed. Linear reprobe is probably a winner overall.
> >o Keys are never deleted (a "resize" to the same size is necessary). > > Keys can actually be deleted, that's what the Tombstone key is for. That just means they don't have a valid value. The end user won't see the difference, but the key in the table is never deleted so that the slot can be reused. That's what I meant. This means that the worst use case is a table with short lived entries that is fed new keys all the time (deleting and readding the same key is not a problem). Something like that isn't entirely uncommon in real-world caches, but then the turnaround is on a scale of several minutes so the resize overhead is probably small overall. > The algorithm allows for shrinking the same way it allows for > growth, it's just that he hasn't implemented it. The reason why (as > he states it) is that you'd need to be careful that you don't get > one thread shrinking and another growing and another then shrinking > again, and so forth. Other than that, the method for growing and > shrinking basically is the same. Double when full, shrink when 3/4'ths empty is usually a reasonable policy to avoid that sort of thing.
