Do Set implementations waste memory?

[Rémi Forax]

Le 18/03/2010 00:59, Paulo Levi a écrit :
> My understanding is that set implementations are implemented by using 
> Maps internally + a marker object, and that since Maps are implemented 
> using arrays of entries this is at least n*3 references more that what 
> is needed, since there are never multiple values.
>
> Any plans to change this? I suspect it would be a boon for programs 
> that use the correct data structure.
>

You have to test it.
My guess is that there will be no difference.
As far as I remember, an object needs to be aligned on a valid 64bits 
address even in 32bits mode,
Hotspot uses a 64bits header and the internal hash map entry contains 4 
ints,
if you remove the reference corresponding to the value, the empty place 
will be
considered as garbage and not used.

Else, you can try to remove the internal entry object but in that case
the hashcode of the element will be not stored anymore and you will
have a slowdown for all objects that doesn't cache their hashcode by itself.

Rémi