Java HashMap 占用大量内存

Question

问题是我的哈希图占用了太多空间。我想知道代码是否可以以更有效的方式完成，而不占用那么多内存。我有一个巨大的数组，我使用 HashMap 的原因是因为我想要一种快速的方法来打印代码中所示的 where key = 3 的第一次出现。但现在的问题是内存。 我还是希望它相对较快 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

由于您主要关心的是空间，因此您可能会考虑以下性能权衡，这不需要分配额外的内存。

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 2

更新：您不应该使用以下内容

我将把它留在这里一段时间，以了解什么是不该做的。 今天我了解到使用 hashcode

 进行单独比较是不够的。
我认为短路的想法很好，但似乎并不是一个问题。
HashMap 已经在解决冲突方面做得很好，并且复制的实现可能最终会使用与初始版本一样多的内存。

相关问题：

Java：为了方便，在 equals() 内部使用 hashCode()？
两个字符串：相同的哈希码
Java 中用于文本字符串的良好 64 位哈希函数是什么？

原答案如下：

一种方法可能是存储哈希值而不是整个字符串：

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

扩展@Alexander的想法，我认为您可以通过保存哈希和索引而不是普通字符串并重新计数（+短路）来节省空间和计算

所以：

迭代列表
在地图中搜索，如果第一次看到保存索引并计数=1
如果在增量计数之前看到
如果数到3就完成了。

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 3

您可以在当前的实施中尝试一些优化。这些都是低成本、快速的成果：

使用明确的初始容量和负载系数

通过使用

适当的构造函数，您可以为 LinkedHashMap 指定初始容量和负载因子。

负载率

根据

docs

，较高的值会减少空间开销，但会增加查找成本。您必须尝试使用 0.75（默认）和

0.99

之间的值才能找到最佳位置。初始容量

通过使用较高的值，您可以最大程度地减少由于存储桶已满而导致的重新散列。由于您使用的是 LinkedHashMap，因此较大初始容量的影响不太重要，因为迭代时间不受影响。如果您的用例允许，您甚至可以通过选择足够大的值来覆盖所有不同的条目来消除重新散列（即，如果您有计算了多少个不同键的历史数据，或者您的数据集无论如何都有有限元素）。如果您可以最小化/消除重新散列，您还可以最大程度地减少较大负载因子值引起的任何缺点。

只保留感兴趣的条目

看来你只需要为每个频率找到

一个

键。如果这是真的，您可以在完成后减少内存中保留的数据，并且每个频率（计数）仅保留一个密钥。 示例代码

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

附注：

您的用例让我想起了 Redis

如何优化哈希的内存使用

。这是一个有趣的方法，您是否应该考虑将 Redis 添加到您的堆栈中。

Answer 4

使用

Byte
1. 代替

   Long

   删除您知道出现次数超过 3 次的元素。这可能不会节省那么多内存，因为我必须创建一个 HashSet 来实现该机制。此外，并不能真正改善最坏的情况，但平均而言应该有所帮助。

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

Answer 5

O(n log n)

使用排序方法来简化搜索的复杂性：

    ArrayList<String> str = new ArrayList<>();
    // Add elements to the str list as needed
    
    // First, store the first occurrence index of each element
    Map<String, Integer> firstOccurrence = new HashMap<>();
    for (int i = 0; i < str.size(); i++) {
        if (!firstOccurrence.containsKey(str.get(i))) {
            firstOccurrence.put(str.get(i), i);
        }
    }

    // Count the occurrences of each element
    Map<String, Integer> counts = new HashMap<>();
    for (String val : str) {
        counts.put(val, counts.getOrDefault(val, 0) + 1);
    }

    // Find the first element with exactly 3 occurrences
    for (String key : firstOccurrence.keySet()) {
        if (counts.get(key) == 3) {
            System.out.println(firstOccurrence.get(key));
            break;
         }
    }

说明：

1.First Occurrence Map：一个Map

，用于存储每个元素的第一次出现索引。

2.Counts Map：用于统计每个元素出现次数的 Map

。

3.两次通过：

第一遍填充firstOccurrence 映射。

• 第二次计算出现次数。
• 第三遍（遍历键）查找第一个恰好出现 3 次的元素。

复杂性：

时间复杂度
• ：由于使用HashMap操作的开销，平均为 O(1)，但由于调整大小和散列，在最坏情况下可以被视为 O(log n)冲突。
空间复杂度
• ：O(k)，其中 k 是满足条件时唯一元素的数量。