java - 如何从 Java 中的未排序数组中快速获取前 N 个出现项？

Question

我试过两种方法。

1. 使用 HashMap 计算每个项目的数量，然后导航 map

   HashMap<Integer, Integer> doc_counts = new HashMap<Integer, Integer>();
   for (int i = 0; i < p; ++i) {
       int doc = alld[i];
       Integer count = doc_counts.get(doc);
       if (null == count)
           count = 0;
       doc_counts.put(doc, count + 1);
   }
   // to now it cost 200ms already
   for (Entry<Integer, Integer> item : doc_counts.entrySet()) {
       heapCheck(h, hsize, item.getKey(), item.getValue());    // heap sort top hsize items
   }
   

2. 先对数组进行排序，然后使用堆排序得到top N。

   Arrays.sort(alld, 0, p); // the sort costs about 160ms
   int curr = alld[0];
   int count = 0;
   for(int i = 0; i < p; i++) {
       int doc = alld[i];
       if(doc == curr) {
           ++count;
       } else {
           ++nHits;
           //curr += base;
           heapCheck(h, hsize, curr, count);
           curr = doc;
           count = 1;
       }
   }
   //
   // Handle the last document that was collected.
   heapCheck(h, hsize, curr, count);
   

在一个包含 1,600,000 个项目的数组上测试表明，第二种方法耗时约 170 毫秒，大部分时间都花在排序上(约 160 毫秒)，而第一种方法耗时 200 毫秒，即使只是将所有项目添加到 HashMap。如何提高性能，找到更快的映射或排序函数或将其更改为并行函数以使用多线程？

Answer 1

堆排序的复杂度为 O(n log n)，而将所有内容添加到 Hashmap 的复杂度为 O(n)，因此很可能由于 Hashmap 的调整大小/重新散列而导致常数因子性能下降。尝试指定一个大的初始容量以避免太多的调整大小操作。