4

好吧，为了解释问题问题......

我有：
一个包含数百万个条目的 Big DB 表（每个条目可能有“n”个列）。

这个概念：

我想向 Web 界面显示两个列表（例如“可用”和“已选择”）。当用户将条目从一个列表移动到另一个列表时，我需要将条目的唯一 ID（字符串类型）临时存储到我的服务器中名为“selected”的“未知数据结构”中，并且当用户最终单击提交时我会将此列表进一步传递给其他应用程序。

排序和过滤在 DB 中完成，然后将全部数据（以块为单位）加载回 java，然后检查每个条目是否被选中，并将其添加到将显示在网页界面。

for each entry{
  if(selected.contains(currentEntry.ID)){
    selectedList.add(currentEntry)
  }else{
    availableList.add(currentEntry)
  }
}

列表 selectedList 和 availableList 将仅包含数百个条目（向用户显示的条目，大约是一个最多包含 100-200 个条目的页面），因此“条目”类型的列表足够好并且可以保存我的排序。

问题：
“选定”的结构必须包含数千个 id（有时可能达到数百万个）。

需求：
我需要快速访问以查找 id 是否存在（structure.contains(id)），所以我肯定会使用哈希结构。我需要使用最少内存资源的结构。

不需要：不需要
良好的删除性能。不需要排序。

4

5 回答 5

1

mybe 你可以快速访问的东西，比如 HashSet。

于 2013-04-26T12:24:42.530 回答
1

您可以使用 a TreeSet，javadoc 说它“为基本操作（添加、删除和包含）提供有保证的 log(n) 时间成本” ，如果您需要将某些内容链接到您的 id，请使用HashMap

于 2013-04-26T12:25:43.437 回答
1

经过大量测试后，我意识到所有 Hash 结构（HashSet、LinkedHashMap 等）的性能大致相同。

当我超过 200.000 个元素（当然这与硬件等有关）时，我开始面临测试系统溢出的问题。

我可能会使用数据库表来保存选定的 id 并使用连接直接从数据库中获取数据的解决方案（无论哪种方式我都会使用数据库进行排序和过滤）

感谢@DariusX。对于“获胜”的建议和其他所有人的帮助。

于 2013-05-03T12:26:35.557 回答
0

1.既然你需要持有数千个id，HashMap那么一个ans。如果密钥已知和快速插入，它的访问速度非常快。

2.一般情况下treemap&hashmap都不是同步的，而是hashtable同步的。同时，hashtable不允许空键或值。另一方面hashMap允许一个空键。

3.您也可以使用TreeMapasTreeMap允许我们以用户定义的某种排序顺序检索元素。好吧，我认为这 TreeMap比HashMap

编辑： 好吧，在阅读了几篇文章后，我也遇到了这篇文章..

不过说真的，你最好完全远离 Hashtable。对于单线程应用程序，您不需要同步的额外开销。对于高度并发的应用程序，偏执的同步可能会导致饥饿、死锁或不必要的垃圾收集暂停。就像 Tim Howland 指出的那样，您可以改用 ConcurrentHashMap

所以，我会去ConcurrentHashMap

于 2013-04-26T12:35:55.947 回答
0

HashSet应该提供快速访问，并且很可能是恒定时间访问，但我认为如果可行，您可以运行示例测试以检查是否由于数百万个条目和数据集的性质而存在过高的冲突。

这肯定不会满足您的最佳内存需求，您期望在 Java 内存中保存数百万个条目的大小是多少？如果它的占用空间非常大（比如 1000 MB），您可能需要考虑分布式缓存，甚至考虑索引方法。

于 2013-04-26T12:48:51.353 回答