search

vigna / fastutil

fastutil extends the Java™ Collections Framework by providing type-specific maps, sets, lists and queues.
Apache License 2.0
1.81k stars 199 forks source link

trim() limited to powers of two #334

Closed jvandort closed 2 weeks ago

jvandort commented 2 weeks ago

I am using Long2ObjectOpenHashMap due to it being more memory compact than a HashMap with Long keys.

However, as it stands (as far as I can tell), it is not possible to trim a map to a size != a power of two.

Say I have a map of size 65, if I trim it, this.n will be 128. To me this is a huge waste of space. I would expect the trim to set this.n to capacity / f, not nextPowerOfTwo(capacity / f).

Going further, I would like to size this map exactly to my dataset. The idea is that I build up a map, then afterwards trim it to size and do not mutate it further. Ideally, I would like to set f equal to 1.0f, but at the moment have resorted to setting the load factor to Math.nextDown(1.0f). Why can the load factor not be set to 1.0f?

vigna commented 2 weeks ago

I suggest you have a look at any basic tutorial about hash tables. Knuth is a good start. Or Wikipedia.

incaseoftrouble commented 2 weeks ago

Why can the load factor not be set to 1.0f?

this will give you O(n) lookup due to basically guaranteed hash collisions. If you have a fixed data set you may want to look into perfect hashing.