Java项目:提高HashMap (包括加载存储)的性能

Question

我试图为我们的服务器编码，在其中我必须找到用户访问类型的URL。

现在，在开始的时候，我们看到每天有1亿个不同的URL被访问。现在，随着时间的推移，它变成了每天近6亿个不同的URL。

对于1亿美元，我们所做的如下：

1)使用并行数组构建一个键是URL的一部分(表示为LONG)，值是URL的另一部分(表示为INT)的HashMap - key可以有多个值。

2)然后搜索HashMap，看看访问了多少次。

现在，随着HashTable变得越来越大，我们做了以下工作：

1)构建两个/三个独立的HashTable，加载并存储(在通用文件系统上)，查看访问了多少次URL。

现在的问题是

1)虽然HashTable的性能相当不错，但代码在加载/存储HashTable时需要更多时间(我们使用文件通道，需要16-19秒来加载/存储HashTable -2亿个条目-因为加载因子为0.5)

我们想问的是：

1)有什么建议如何解决这个问题？

2)如何减少加载/存储时间(我之前问过，但似乎文件通道是最好的方法)？

3)存储一个大的HashTable (比内存更多)并重复缓存它是一个很好的解决方案吗？如果是这样，如何做到这一点(至少一些指针)。我们使用以下命令进行了尝试

RandomAccessFile raf = new RandomAccessFile("array.dat", "rw");
IntBuffer map = raf.getChannel().map(FileChannel.MapMode.READ_WRITE, 0, 1 << 30).order(ByteOrder.nativeOrder()).asIntBuffer();

但是，提供的性能比以前更差。

谢谢。

注意：

1)根据之前堆栈溢出的建议，我们使用了一些NoSQL DB，比如TokyoCabinet，但根据我们的经验，自定义HashTable在1亿键值对上比它有更好的性能。

2)不能为磁盘缓存预读数据，因为当系统启动时，我们的应用程序将开始工作，并在系统启动的第二天开始工作。

我们忘记提到的是：

1)由于我们的应用是项目的一部分，并且是在小型校园中应用，所以我们假设URL的访问量不超过8亿。因此，您可以认为600/700数据值是固定的。

2)我们主要关心的是性能。

3)我们必须在本地运行应用程序。

Edit: code of our hashmap can be found here.

Answer 1

最好是将表作为memory-mapped缓冲区进行访问。这样，您就可以简单地实现对文件的随机访问，而不必担心加载和存储，并将缓存留给操作系统。我看到your current implementation已经使用内存映射访问来进行读写，但它仍然会在两者之间将内容加载到java堆中。避免这种数据复制和复制！将备份文件本身视为数据结构，仅在需要时才访问实际需要的部分。

在该文件中，如果您真的非常确定哈希冲突不是问题，则哈希映射将会起作用。否则我会去那里找一个B+ tree，它的节点大小和你的硬盘页面差不多。这样，每次磁盘访问将产生比单个键多得多的可用数据，从而导致更浅的树和更少的单个磁盘操作。

我猜其他人可能已经实现了类似的东西，但是如果您更喜欢自己的散列映射实现，那么您可能更喜欢编写自己的内存映射B+树。

Answer 2

对我来说，整个方法听起来很可笑。我猜您真正想实现的是每个不同URL的简单访问计数器。就其本质而言，这些数据经常被写入，但很少被读取。

为此，我只需要有一个数据库表，并为每个访问添加一个新条目(它也可以用作日志)。当您需要计算任何URL被访问的频率时，可以使用表中的SELECT计数轻松完成(取决于您将多少额外数据与URL条目一起存储，您甚至可以进行受约束的计数，如昨天访问的频率、上周访问的频率等)。

这就把所有的工作都推到了真正需要结果的地方。

顺便说一句，您也可以从web服务器日志文件中检索访问计数，因此您可能不需要自己编写任何数据。先看看这个。

Answer 3

您可以使用像JCS这样的缓存框架。10亿个键值对应该不是问题。

http://commons.apache.org/jcs/