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;
    }
}

CodePudding user response：

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;
    }
}

CodePudding user response：

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

CodePudding user response：

Since your primary concern is a space, you can sort list by N log N using any sort algorithm, then do one loop by comparing each value with previous one and increment counter if they equal, otherwise reset counter to 1 and continue loop.

    private static List<Map.Entry<String, Integer>> zipWithIndex(List<String> list){
        List<Map.Entry<String, Integer>> res = new ArrayList<>(list.size());
        int idx = 0;
        for (String s : list) {
            res.add(Map.entry(s, idx  ));
        }
        return res;
    }


    public static void main(String[] args) {
        List<String> list = List.of("a", "b", "a", "b", "c", "b", "a");

        List<Map.Entry<String, Integer>> sorted = zipWithIndex(list)
                .stream()
                .sorted(Map.Entry.comparingByKey())
                .collect(Collectors.toList());

        int count = 1;
        int minElementIndexWithFreq3 = -1;
        for (int i = 1; i < sorted.size(); i  ) {
            String prev = sorted.get(i - 1).getKey();
            String current = sorted.get(i).getKey();
            int currentElemOriginalIndex = sorted.get(i).getValue();
            if (current.equals(prev)){
                count  ;
            } else {
                if (count == 3){
                    if (minElementIndexWithFreq3 == -1 || currentElemOriginalIndex < minElementIndexWithFreq3){
                        minElementIndexWithFreq3 = currentElemOriginalIndex;
                    }
                }
                // reset count
                count = 1;
            }
        }
        System.out.println(minElementIndexWithFreq3);
    }