将HashMap文件化

   （ 只是个想法加雏形，实现的很丑陋且效率很低下）

    有这样一种场景，校验千万行文本中某一列键值（长度30以上）的唯一性(要求100%准确）。按我的水平，自然就想到用HashMap，可这样就会将所有的键值都放入内存，对内存资源需求较大。然后我就想，数据库也有一样的需求呀，人家怎么搞的呢？思前想后，能力太有限，没思路。最后只能想到，如果把HashMap的存储介质由内存转移到外存（文件中），貌似会节省相当部分的内存（此假设未经证实）。于是着手改造，HashMap实现的主要算法基本了解只是对于寻址那块要从内存转入文件，这是关键。由此做了如下设计：

 

HashMap的put方法中：

由hashcode算出在table中的位置i，然后以table[i]为链首存储元素。

 

我的思路：

建一个索引文件，每个索引的结构:数据项+后继索引位置。索引长度：数据项长度+long型的长度(8字节)

table[i]即链首的位置 = i * 数据项长度+8

当首次写入链首时，索引位置埴0，因为下一个元素未知嘛。

当table[i]第n个元素写入时，从链首开始遍历（取后继索引位置，跳转至该位置），直到遍历索引位置为0的链表元素，将要写入第n个元素的文件位置记到此后继索引位置，并将第n个元素写入文件。如果遍历时发现，当前元素数据项与要写入元素的数据项值相同，则发现重复元素。

 

 

 

目前的问题：

1. io操作过多，考虑是不是可以通过内存映像文件来提高提高效率。当然加加cache也行，就是没考虑好怎么加。

2. 还木有想到。。。

 

 

上传了我丑陋的代码，运行FileMap就好。 

 

试用了一下jdbm-2.0.jar这个包，100万行数据插入，就是从1到100万，10行一提交。共用了38秒。使用内存14M左右，太NB。严重鄙视我提交的烂代码。

评论

32 楼 lenozhi 2011-04-25  

iamlotus 写道

lenozhi 写道

iamlotus 写道

你这行事先知道吗？
知道的话遍历一遍，把hash相同的在内存里比较不就完了？

遍历一遍得把所有的hash值都存下来是吧，不然咋知道有hash相同的？这值到是可以把value设成空，可以节省内存空间。嗯。。等下，遍历一遍貌似得两个循环吧，不然咋找？

iamlotus 写道

不知道就学数据库建B+树，用file based hash空间太大，肯定不合算。其实不用那么麻烦，建张表，建个UK，然后全部insert进去不就完了？千万而已，又不是千亿，数据库吃得消。

用数据库整到是没试过，千万的话，字符串长度32，得多长时间？比如是个8核，64G的机器。

比如你有一组值A[]={A1 A2 A1 A3}, hash后分别是 {H1,H1,H1,H2} （假设A1,A2hash相等）
你的需求究竟是 “已知A1,问A中是否有和A1相同的值” 还是 “已知A，问其中有哪些值出现了一次以上”？
前者就是事先知道这行，后者就是不知道这行。
对前者，事先由A1算出 H1，然后遍历一遍A即可，连HashSet都不用，怎么会要两个循环？
后者你自己试试就知道时间了，配置不同不一样的。我估计不出插入时间，不过select应该能在20秒搞定。

是知道A，A存在于文件中。找出A中重复的。jdbm那个还不错，我试过。

31 楼 iamlotus 2011-04-25  

lenozhi 写道

iamlotus 写道

你这行事先知道吗？
知道的话遍历一遍，把hash相同的在内存里比较不就完了？

遍历一遍得把所有的hash值都存下来是吧，不然咋知道有hash相同的？这值到是可以把value设成空，可以节省内存空间。嗯。。等下，遍历一遍貌似得两个循环吧，不然咋找？

iamlotus 写道

不知道就学数据库建B+树，用file based hash空间太大，肯定不合算。其实不用那么麻烦，建张表，建个UK，然后全部insert进去不就完了？千万而已，又不是千亿，数据库吃得消。

用数据库整到是没试过，千万的话，字符串长度32，得多长时间？比如是个8核，64G的机器。

比如你有一组值A[]={A1 A2 A1 A3}, hash后分别是 {H1,H1,H1,H2} （假设A1,A2hash相等）
你的需求究竟是 “已知A1,问A中是否有和A1相同的值” 还是 “已知A，问其中有哪些值出现了一次以上”？
前者就是事先知道这行，后者就是不知道这行。
对前者，事先由A1算出 H1，然后遍历一遍A即可，连HashSet都不用，怎么会要两个循环？
后者你自己试试就知道时间了，配置不同不一样的。我估计不出插入时间，不过select应该能在20秒搞定。

30 楼 lenozhi 2011-04-23  

iamlotus 写道

你这行事先知道吗？
知道的话遍历一遍，把hash相同的在内存里比较不就完了？

遍历一遍得把所有的hash值都存下来是吧，不然咋知道有hash相同的？这值到是可以把value设成空，可以节省内存空间。嗯。。等下，遍历一遍貌似得两个循环吧，不然咋找？

iamlotus 写道

不知道就学数据库建B+树，用file based hash空间太大，肯定不合算。其实不用那么麻烦，建张表，建个UK，然后全部insert进去不就完了？千万而已，又不是千亿，数据库吃得消。

用数据库整到是没试过，千万的话，字符串长度32，得多长时间？比如是个8核，64G的机器。

29 楼 iamlotus 2011-04-22  

你这行事先知道吗？
知道的话遍历一遍，把hash相同的在内存里比较不就完了？
不知道就学数据库建B+树，用file based hash空间太大，肯定不合算。其实不用那么麻烦，建张表，建个UK，然后全部insert进去不就完了？千万而已，又不是千亿，数据库吃得消。

28 楼 sx011966 2011-04-21  

把那个文本作为oracle 外部表，然后用sql来排除

27 楼 ray_linn 2011-04-21  

bloom过滤器

26 楼 lenozhi 2011-04-21  

试用了一下jdbm-2.0.jar这个包，100万行数据插入，就是从1到100万，10行一提交。共用了38秒。使用内存14M左右，太NB。严重鄙视我提交的烂代码。

25 楼 lenozhi 2011-04-21  

renwolang521 写道

看你这个HashMap文件化，我想是否可以遍历一遍，存到sqlite中然后利用数据库寻找重复的。
java使用sqlite 就一个jar包(http://www.zentus.com/sqlitejdbc/)就行了,最后形成的也就一个文件。用完文件直接删了就行了。

不错，我去试试。看看对大数据量的支持如何

24 楼 renwolang521 2011-04-21  

看你这个HashMap文件化，我想是否可以遍历一遍，存到sqlite中然后利用数据库寻找重复的。
java使用sqlite 就一个jar包(http://www.zentus.com/sqlitejdbc/)就行了,最后形成的也就一个文件。用完文件直接删了就行了。

23 楼 uin57 2011-04-21  

lenozhi 写道

shguan2010 写道

考虑一下 jdbm2
http://code.google.com/p/jdbm2/

不错的东东

为什么不试一下derby呢？

22 楼 lenozhi 2011-04-20  

shguan2010 写道

考虑一下 jdbm2
http://code.google.com/p/jdbm2/

不错的东东

21 楼 shguan2010 2011-04-20  

考虑一下 jdbm2
http://code.google.com/p/jdbm2/

20 楼 real_aaron 2011-04-20  

<p>如果不想重造轮子的话可以考虑使用oracle的 bdb je,其collections框架提供了map的持久化实现。 其中的 com.sleepycat.collections.StoredMap 应该能满足你的需要,要注意的是je是dual licence.</p>
<p> </p>

19 楼 ppgunjack 2011-04-20  

数据库是可以越过系统调用直接操纵磁盘，不过很多应用还是会架在OS的文件系统上访问数据
其实考虑类似bdb这样的嵌入式数据库比自己写类似应用要更容易，适用范围保护也更好，结合OS的内存虚拟磁盘使用可以很灵活构建方案

18 楼 咖啡豆子 2011-04-20  

首先看你的KEY是什么特点，设定一个规则，将HASHMAP分散到多个文件。不过我觉得这么搞还不如就放在数据库里好了

17 楼 lenozhi 2011-04-20  

ppgunjack 写道

索引大多都是B+树，可以保证分布平均，树深度不深，hash最坏的情况全落一个桶，唯一肯定是需要排序的，千万这个量不用纠结，与其考虑算法，应该优先考虑记录减肥降低磁盘io

原来是这样子，学习了。

16 楼 ppgunjack 2011-04-20  

索引大多都是B+树，可以保证分布平均，树深度不深，hash最坏的情况全落一个桶，唯一肯定是需要排序的，千万这个量不用纠结，与其考虑算法，应该优先考虑记录减肥降低磁盘io

15 楼 lenozhi 2011-04-20  

mtnt2008 写道

lenozhi 写道

kimmking 写道

直接用hashcode呗。

咋叫直接用hashcode,两个键值的hashcode相同咋办

hash冲突的处理方法：1.开放地址法 2.地址链法 3.再hash发

以前的一个思路：

1.把value通过MappedByteBuffer(java的内存文件映射)存入硬盘得到文件偏移量d；

2.对key做hash,以这个值为index,进行操作：桶数组[index] = d

3.如果发生hash冲突，选用一个处理hash冲突的方法

目前我用用RandomAccessFile整的，正要试试MappedByteBuffer。再配合加些cache，不知道能搞成啥样。

14 楼 lenozhi 2011-04-20  

JE帐号 写道

我的印象里java的io操作是比较弱的,文件操作性能很差.
所以说,新拿到一个值,虽然你可以算出来应该在什么位置,并用skip直接定位过去,可是在io内部还是给read中间哪些值. 再说,你向文件里插入一个值,我印象是不可能向链表似的前后改下索引就行了,好像给整个复制....

用RandomAccessFile可以实现我描述的（已经实现了）。

JE帐号 写道

反正,我以前用io的时候就是这个印象.
所以我一直觉得数据库应该对于文件系统的操作进行了底层的控制,比如从10000跳到20000,他是直接跳过去找到,而不是顺序读过去的.

数据库底层很可能是跳过文件系统，直接玩的。

13 楼 mtnt2008 2011-04-20  

准备实现自己的想法，写一个。到时欢迎大家拍砖 @-@