用哪种数据结构来存储大量的字符串？

Question

好的，要解释这个问题-问题...

我有：

一个填满了数百万条记录（每个记录可能具有“n”列）的大型数据库表。

概念：

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

排序和过滤是在数据库中进行的，然后全量数据（以块为单位）被加载回Java，然后每个条目都会被检查是否被选择，并将被添加到即将在Web界面中显示的列表中。

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

选定列表和可用列表只会包含少量条目（那些向用户显示的，大约一页最多100-200个条目），因此类型为“entry”的列表已足够，并且可以进行排序。

问题：
结构“selected”必须保存许多千个ID（有时可能达到百万级别）。

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

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

- Stef

---

我认为使用Set会是最好的选择。 - Achintya Jha

如果需要保存这么多条目，你应该将它们存储在一个数据库表中，并附加一个额外的ID（例如某种类型的会话ID）。 - Darius X.

经过大量测试，我意识到所有哈希结构（HashSet、LinkedHashMap等）的性能几乎相同。TreeSet是我测试中性能最差的结构，需要最长的时间来查找元素。当我超过200,000个元素时，开始遇到测试系统溢出的问题（当然这与硬件等有关）。我可能会采用使用DB表来保存所选ID并直接从DB中获取数据的解决方案，使用连接方式（无论哪种方式，我都将使用DB进行排序和过滤）。感谢您的帮助。 - Stef

Answer 1

经过大量测试，我意识到所有哈希结构（HashSet、LinkedHashMap等）的性能大致相同。当我超过200,000个元素时（当然这与硬件等有关），我开始遇到测试系统溢出的问题。

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

感谢@DariusX提供的“获胜”建议以及其他人的帮助。

- Stef

Answer 2

也许是像 HashSet 这样可以快速访问的东西。

- duffy356

Answer 3

你可以使用 TreeSet，它的 javadoc 表明它提供了基本操作（添加、删除和包含）的 log(n) 时间保证。如果你需要将某些内容与你的 id 关联起来，可以使用 HashMap。

- DeadlyJesus

Answer 4

1.由于您需要保存成千上万个ID，因此HashMap是一个不错的选择。如果已知键，则它具有非常快的访问速度和快速插入。

2.通常，treemap和hashmap都没有同步，但hashtable是同步的。同时，hashtable不允许空键或值。另一方面，hashMap允许一个空键。

3.您还可以选择TreeMap，因为TreeMap允许我们按用户定义的某些排序顺序检索元素。嗯，我认为TreeMap比HashMap慢。

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

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

所以，我会选择使用ConcurrentHashMap

- Vinayak Pahalwan

Answer 5

HashSet 应该提供快速访问，并且很可能是常数时间访问，尽管我认为如果可行的话，您可以运行样本测试以检查由于数百万条目和数据集的性质而导致的碰撞是否过高。

这肯定不会解决您的最佳内存需求，您期望在将数百万条目保存到Java内存中时需要多大的占用空间？ 如果其占用空间非常大（比如1000 MB以上），则您可能需要考虑分布式缓存甚至考虑索引方法。

- harsh