TL;DR: in this post I present Bikey, a Java library to create Maps and Sets whose elements have two keys, consuming from 70%-85% to 99% less memory than usual data structures. It is Open Source, published in https://github.com/jerolba/bikey and available in Maven Central.
In my last post I talked about the problems of using an incorrect hash function when you put an object with a composite key in a Java
HashMap, but I was stuck with the question: Which data structure is better to index those objects?
Continuing with the same example I will talk about products and stores, and I will use their identifiers to form the map key. The proposed data structures are:
- A single map with a key containing its indexes:
HashMap<Tuple<Integer, Integer>, MyObject>, which I will call TupleMap.
- A nested map:
HashMap<Integer, HashMap<Integer, MyObject>>, which I will call DoubleMap.
In this post, I will describe you a real case in Nextail, where the change of a single line of code related to a hash function changed the performance of an application, both for CPU consumption and memory.