在Java中的“Big dictionary”实现
在Java中的“Big dictionary”实现
我正在进行一个Java项目，将使用一个“大字典”来存储单词。所谓的“字典”是指将某些数字（int）分配给字符串。而所谓的“大”是指一个大约100MB的文件。我想到的第一个解决方案可能是最简单的。在初始化时，我会读取整个文件，并创建一个大型HashMap，以便后续可以用来查找字符串。\n是否有一种高效的方法在初始化时不需要读取整个文件呢？也许没有，但如果文件确实很大，比如接近可用RAM的大小，那该怎么办呢？所以基本上我正在寻找一种在内存中高效地查找大型字典的方法。\n感谢迄今为止的回答，由此我意识到我可以在问题上更具体一些。你们可能已经猜到这个应用与文本挖掘有关，特别是将文本表示为稀疏向量的形式（尽管有些人有其他创新的想法 :))。因此，对于使用而言，关键是能够在字典中快速查找字符串并获取它们的键。最初“读取”字典文件或将其索引到数据库中的开销并不像优化字符串查找时间那样重要。再次，让我们假设字典的大小很大，与可用RAM的大小相当。
在Java中实现“大字典”存在以下问题。解决方法如下：
问题1: 在字典中查找字符串并尽快获取它们的键是至关重要的，使用数据库相对较慢，使用HashMap更快。
解决方法: 避免使用数据库，而是使用HashMap实现快速查找。
问题2: 当字典的大小超过内存限制时，需要更多的内存来存储字典。
解决方法: 获取更多的内存来存储字典，如果无法获取更多内存，可以只加载最常见的单词，对于其他单词可以使用较慢的方法（例如内存映射文件）。
问题3: 缺乏一个良好的实现字典的Trie数据结构。
解决方法: 在Java中没有一个特别好的Trie数据结构的实现，特别是在堆外内存中。但可以尝试使用ByteBuffer将整个字典打包，假设大部分字符为ASCII字符，可以使用位操作，每个箭头标签字符需要1个字节，每个子节点指针需要1-5个字节。子节点指针使用相对值（即当前节点和子节点之间的差异）存储，可以使用base 128编码将大多数子节点指针压缩到单个字节中。具体的内存消耗需要估算，但每个单词约为4个字节。上述压缩会降低查找速度，但仍然远远快于单个磁盘访问。
为了实现“大字典”功能，需要考虑使用HashMap进行快速查找，并根据需要获取足够的内存来存储字典。如果需要使用Trie数据结构，可以尝试使用ByteBuffer将字典打包，并使用位操作和压缩算法来降低内存消耗。
在数据结构占用几百MB到几个GB的情况下，最好不要在运行时初始化数据结构，而是使用支持索引的数据库（大多数数据库都支持索引）。索引是唯一能确保在文件变得如此庞大并且接近JVM的-Xmx设置时能够实现最快检索文本的方法之一。这是因为如果文件的大小与或远远大于最大大小设置，那么不可避免地会导致JVM崩溃。
至于必须在初始化时读取整个文件。您最终将不得不这样做，以便能够有效地搜索和分析代码中的文本。如果您知道您一次只会搜索文件的某个部分，那么可以实现延迟加载。如果不是这样，那么最好一次性将整个文件加载到数据库中。在此过程中，如果有其他不依赖于此的代码执行部分，可以实现并行处理。
无论如何，与HashMap相比，任何数据库都非常慢。考虑到OP提到的100MB，这根本没有意义。更糟糕的是：如果字符串不适合内存，那么您就取决于操作系统和硬盘...速度会减少5个数量级（100 ns HashMap vs. 10 ms硬盘）。使用trie压缩字符串听起来会快得多。
根据我的经验，数据库实际上并不那么慢（在MongoDB中，我甚至无法分辨出差异）。事实上，如果能够充分利用数据库内部提供的工具，它们可以非常快速。我从未见过一个大小为100MB的数据结构，并且他还提到了"orders of RAM"，在这种情况下，我个人会使用数据库，正如其他人所建议的那样。我同意，将更多的东西放在内存中会使事情变得更快，但我并不假设这篇文章的作者会为这个问题购买更多的内存。
你所说的"那么慢"是什么意思？我找到了这个基准测试...当没有涉及硬盘时，访问时间为50微秒，这意味着慢了3个数量级。带有SSD的时间为10毫秒。数据库中没有任何东西可以比HashMap更快，而且存在相当多的开销。光IPC的成本就比查找本身要高得多。
我从未反驳过HashMap会更快的事实。我只是说，对于它来说，100MB实在太多了。根据我的直觉和最佳实践，我永远不会为那么多的内存使用HashMap。根据我在垃圾回收、数据库内部等方面的经验，我无法推荐在堆中为单个HashMap实例分配100MB以上的内存。不过，请不要误解，我非常尊重您的观点，事实上，如果他不想使用数据库，我认为leventov的ChronicalMap是最好的解决方案。
那么我们确实达成了一致意见。我不会担心垃圾回收，因为数据似乎从不改变。我必须尝试一下会发生什么。实际上，标准的HashMap是一个内存占用工具，Guava的ImmutableHashMap也是如此，但是有很多CompactHashMap可以使用。
哈哈，是的，我们达成了一致意见：0）CompactHashMap、ChronicleMap将是解决这个问题的好方法。感谢您提供的精彩讨论，我学到了很多：）希望您有一个美好的一天！
在这段内容中，介绍了一个名为ChronicleMap的Java字典实现。它是一个非复制模式的堆外Java Map实现，或者从另一个角度来看，它是一个超轻量级的NoSQL键值存储。它的一些优点包括：通过内存映射文件将数据持久化到磁盘、延迟加载、操作系统可以自动解除映射不常用的页面等。
然而，ChronicleMap没有成为一个真正的万金油的原因是每次查询都需要对键值进行序列化和反序列化操作。对于String类型的键值来说，由于UTF-8与String之间的转换比较复杂，因此这种开销比较大。但是，如果字符串数据可以存储为byte[]，开销就会降低很多，对于原始类型的键值，几乎没有开销。如果键值是由几个原始类型字段（或其他数据对象）组成的简单数据对象，可以通过实现Byteable接口来避免序列化和反序列化的开销。
对于这个问题的解决方法，某些情况下可以使用trie数据结构，因为对于每个单词的查询，操作系统会将许多其他单词一起加载，而这些其他单词很少被使用。另外，有人建议实现一个名为ChronicleTrie的trie数据结构。
总结起来，ChronicleMap是一个高效的Java字典实现，可以在非复制模式下持久化数据到磁盘，具有延迟加载和共享内存等优点。然而，由于每次查询都需要进行序列化和反序列化操作，对于String类型的键值开销比较大。对于这个问题，可以考虑使用trie数据结构或者实现一个适用于字典的trie数据结构。