Inconsistency in key search loops in HashSet / HashMap, maybe because of old code ?

37 views
Skip to first unread message

Vincent Sonnier

unread,
Apr 16, 2014, 9:49:27 AM4/16/14
to java-high-performance...@googlegroups.com
Hello,

While reviewing the code source changes fof integration on my side (a.k.a stealing the changes) I noticed
something in HashSets / HashMap which is probably there from a long long time.

When searching for a key presence in the Open hash map instances, we see the following pattern :

 slot = hash(key)

 while (allocated[slot])
        {
            if (identical key found)
            {
                //do stuff;
            }

            slot = (slot + 1) & mask;
        }

Sometimes however in OpenHashMap we have also :

slot = hash(key)

final int wrappedAround = slot;

 while (allocated[slot])
        {
            if (identical key found)
            {
                //do stuff;
            }

            slot = (slot + 1) & mask;
            if (slot == wrappedAround)
                break;
        }

Which is there obviously to have a stop iteration condition, but it is not needed as far as I see.

My anayse is that since resizeAt is built to be < real keys size, there is always a slot where allocated == false that stops iteration, In addition,
expandAndPut() looks entirely based around this precondition, as it first asserts emphases :)

Consequently I think the wrappedAround check may come from legacy code that can be entirely removed by now.


Dawid Weiss

unread,
Apr 29, 2014, 7:45:16 AM4/29/14
to java-high-performance-primitive-collections
Sorry for the delay, Vincent.

I think you're right. It used to be the case that all slots could fill
up, actually, but I think in the course of changes (resulting from
http://issues.carrot2.org/browse/HPPC-73, for example) the current
state is that at least one slot is always free, even at load factor of
1 (not recommended though).

Thanks for the heads up, I've committed a patch to the repo.

Dawid
> --
> You received this message because you are subscribed to the Google Groups
> "High Performance Primitive Collections for Java" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to
> java-high-performance-primi...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
Reply all
Reply to author
Forward
0 new messages