IdentityHashMap in hppc?

37 views
Skip to first unread message

Wojciech Jaśkowski

unread,
Sep 5, 2014, 8:48:17 AM9/5/14
to java-high-performance...@googlegroups.com
Hi,

does hppc have a Java's IndentityHashMap equivalent? (Had not found any)

Best,
Wojciech

Dawid Weiss

unread,
Sep 5, 2014, 3:32:09 PM9/5/14
to java-high-performance-primitive-collections
Hi Wojtek!

There is no out-of-the-box solution for this... but a few hints:

1) if your keys don't override equals/ hashCode then the default
implementation in Object is effectively an identity comparison anyway
and you can just use Object*OpenHashMap(s).

2) you can obviously implement a wrapper implementing equals/ hashCode
as an identity of the provided delegate, but this defeats the purpose
I guess (conserving some memory).

3) you could copy/ paste the code of KTypeVTypeOpenHashMap.java and
generate an identity-key-map for generic types by replacing:

Intrinsics.equalsKType(a, b)

with a conditional that would generate (for object KType):

(a) == (b)

and probably it'd be also better to use System.identityHashCode in
place for rehash(..). Now that I think of it it may not be as trivial
as I initially thought and some fundamental knowledge of the
templating system would be probably needed. I will look into this.

4) Can you explain a bit what type of map do you need? Does it require
deletions? Is the maximum number of unique keys known in advance? I
ask because such a map is actually pretty trivial to write (assuming
linear probing); perhaps I can offer some assistance here.

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.

Vincent Sonnier

unread,
Sep 6, 2014, 3:38:40 AM9/6/14
to java-high-performance...@googlegroups.com
<shameless plug here>

Or you can also use my own fork HPPC-RT (https://github.com/vsonnier/hppc)
using KTypeVTypeOpenCustomHashMap using a pre-built strategy  KTypeIdentityHash which actually make it an IdentityMap.

</shameless plug here>

Othewise Dawid is perfectly right in its explaination. Yet another solution is to consider fastutil (http://fastutil.di.unimi.it/) which as also custom hash maps.

Vincent

Dawid Weiss

unread,
Sep 6, 2014, 4:07:19 AM9/6/14
to java-high-performance-primitive-collections
> Or you can also use my own fork HPPC-RT (https://github.com/vsonnier/hppc)
> using KTypeVTypeOpenCustomHashMap using a pre-built strategy
> KTypeIdentityHash which actually make it an IdentityMap.

+1. I will consider pulling this particular piece back into HPPC,
actually - this seems useful in more scenarios than identity maps
(e.g., objects with a poor hashCode distribution).

Dawid

Vincent Sonnier

unread,
Sep 6, 2014, 4:10:13 AM9/6/14
to java-high-performance...@googlegroups.com
Of course, for a pure performance perspective a really specialized IdentityMap would be the way to go. Hey, let's add it ! https://github.com/vsonnier/hppc/issues/28

Vincent Sonnier

unread,
Sep 6, 2014, 8:03:54 AM9/6/14
to java-high-performance...@googlegroups.com
Done, Identity containers are here ! Of course, Identity Hash containers are only meaningfull for key Objects.

Vincent

Dawid Weiss

unread,
Sep 6, 2014, 5:23:40 PM9/6/14
to java-high-performance-primitive-collections
Thanks Vincent!

I looked at your patch (and your fork) -- very well done -- many
interesting things to see and learn from. I didn't want to
revolutionize HPPC's code or templating system (just yet) so I
implemented those identity maps myself, but your patch is definitely
an alternative.

Dawid
Reply all
Reply to author
Forward
0 new messages