Java HashMap that takes to much of the memory

Question

The problem is that my hashmap is taking too much space. I wanna know if the code can be done in a more efficient way for not taking that much memory. I have an huge array and the reason why im using HashMap is because I want a fast way to print out the first occurence of where key = 3 as shown in the code. But the problem is now the memory. I still want it to be relatively fast O(n log n)

ArrayList<String> str = new ArrayList<>();
Map<String, Long> counts2 = new LinkedHashMap<String, Long>();
for(String val : str){
    long count = counts2.getOrDefault(val, 0L);
    counts2.put(val, ++count);
}
for(String key: counts2.keySet()){
    if(counts2.get(key)==3){
        System.out.println(list.indexOf(key));
        break;
    }
}

Answer 1

Update: You should not use the following

I'm just going to leave it here for a bit as a learning of what not to do. Today I learned using a hashcode for sole comparison is not enough. I think the idea of short-circuiting is good, but doesn't seem to be a concern. HashMap already does a great job resolving collisions, and a implementation that replicates that might end up using as much memory as the initial version.

Related questions:

Java: Use hashCode() inside of equals() for convenience?
Two strings: same hashcode
What is a good 64bit hash function in Java for textual strings?

Original answer follows:

One way could be to store the hash instead of the whole string:

...
var count = new HashMap<Integer, Long>();
for(String val: list) {
   count.put(val.hashCode(), count.getOrDefault(val.hashCode(), 0L)+1);
}

Expanding on @Alexander's idea, I think you can save space and computation by saving the hash and the index instead of the plain string and recounting ( + short circuiting )

So:

1. Iterate the list
2. Search in the map, if seen for the first time save index and count = 1
3. If seen before increment count
4. If count is 3 finish.

import java.util.*;

class SpaceTime {

  public static void main(String ... args) {

    var input = Arrays.asList("one", "two", "three", "two", "three", "two");
    var map = new HashMap<Integer, CountAndIndex>();

    for (int i = 0 ; i < input.size(); i++ ) {
      var s = input.get(i);
      var hc = s.hashCode();
      var cai = map.getOrDefault(hc, startAt(i));
      cai.count++;
      if (cai.count == 3) {
        System.out.printf("We've got it!!. Item: '%s' appears for the first time at index: %d%n", s, cai.index);
        break;
      }
      map.put(hc, cai);
    }
  }
  static CountAndIndex startAt(int index) {
    var cai = new CountAndIndex();
    cai.count = 0;
    cai.index = index;
    return cai;
  }
}

class CountAndIndex {
  long count;
  long index;
}
// output: 

We've got it!!. Item: 'two' appears for the first time at index: 1

Answer 2

Since your primary concern is a space, you might consider the following performance trade off, which doesn't require allocation of additional memory.

for (int i = 1; i < strings.size(); i++) {
    String next = strings.get(i);
    if (Collections.frequency(strings,next) == 3) {
        System.out.println(i);
        break;
    }
}

Answer 3

There are a couple of optimizations you can try on your current implementation. These are low-cost, quick wins:

Use explicit initial capacity and load factor

By using the appropriate constructor you can specify both initial capacity and load factor for your LinkedHashMap.

Load factor

Higher values decrease the space overhead but increase the lookup cost, according to the docs. You would have to experiment with values between 0.75 (the default) and 0.99 in order to find a sweet spot.

Initial capacity

By using a high value, you can minimize re-hashing due to buckets getting full. Since you are using LinkedHashMap, the impact of a large initial capacity is less critical since iteration time is unaffected. If your use case allows it, you can even eliminate re-hashing by choosing a large enough value to cover all distinct entries (i.e. if you have historical data of how many distinct keys you count or your dataset has finite elements anyway). If you can minimize/eliminate re-hashing, you also minimize any drawbacks cause by larger load factor values.

Only keep interesting entries

It seems that you only need to find one key per frequency. If this is true, you can reduce the data retained in memory once you are done and keep only one key per frequency (count).

Sample code

        Map<String, Long> counts2 = new LinkedHashMap<String, Long>(10_000, 0.95f); //Using the appropriate constructor
        for (String val : str) {
            long count = counts2.getOrDefault(val, 0L);
            counts2.put(val, ++count);
        }

        // Clean up unneeded (?) entries
        final HashMap<Long, Integer> data = new HashMap<>();
        for (Iterator<Map.Entry<String, Long>> it = counts2.entrySet().iterator(); it.hasNext();) {
            Map.Entry<String, Long> entry = it.next();
            if (data.containsKey(entry.getValue())) {
                it.remove();//Already exists; this will save space
            } else {
                data.put(entry.getValue(), str.indexOf(entry.getKey()));
            }
        }

        //You can now remove original counts2 now
        Integer indexOf3 = data.get(Long.valueOf(3));
        System.out.println(str.get(indexOf3) + " @ " + data.get(Long.valueOf(3)));

        //Original code
        for (String key : counts2.keySet()) {
            if (counts2.get(key) == 3) {
                System.out.println(key + " @ " + str.indexOf(key));
                break;
            }
        }

Bonus note:

Your use case reminded me of how Redis optimizes memory usage for hashes. This is an interesting approach, should you consider adding Redis to your stack.

Answer 4

I could think of 2 things to reduce your memory usage:

1. Use Byte instead of Long
2. Drop elements that you know occur more than 3 times. This one probably won't save that much memory since I had to create a HashSet to implement that mechanism. Also, doesn't really improve worst-case scenario, but should help on average.

    public static void main(String[] args) {
        var str = List.of("blue", "green", "red", "red", "orange", "green",
                "turquoise", "red", "green", "green");
        var exceeds3Count = new HashSet<String>();
        var counts = new HashMap<String, Byte>();
        for (String val : str) {
            if (exceeds3Count.contains(val)) continue;
            Byte count = counts.compute(val, (k, v) -> v == null ? 1 : (byte) (v + 1));
            if (count > 3) {
                counts.remove(val);
                exceeds3Count.add(val);
            }
        }
        System.out.println(counts);
        var answer = str.stream().filter(s -> counts.getOrDefault(s, (byte) 0) == 3).findFirst().get();
        System.out.println(answer + " is the first occurrence of a string that occurs 3 times");
    }