I've been content to just observe Martin and Peter's nice efforts
on this, but one note:
On 07/11/2014 03:00 PM, Martin Buchholz wrote:
On Wed, Jul 9, 2014 at 3:17 PM, Peter Levart <peter.lev...@gmail.com> wrote:
IMH resizing is arranged so that the table is always 33% ... 66% full (if
nothing is ever removed from it) except when capacity reaches 2**29, then
it can be filled up to the top.
avg. # of probes can be taken as a rough estimation of average slow-down,
max. # of probes can be taken as a rough estimation of worst-case-operation
slow-down.
So where to draw the line?
Linear probing has long been known to be prone to long worst-case probes,
but with recent computer architectures this is offset by its extreme cache
friendliness.
Bear in mind that the number of bits of identityHashCode is less
than 32 on all JVMs I know. It can be as low as 23, which means that
you are sure to see a lot of exact collisions on IHMs with only
tens of millions of elements, and there's nothing much you can
do that will help.
-Doug
