将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。严重鄙视我提交的烂代码。

评论

12 楼 mtnt2008 2011-04-20  

lenozhi 写道

kimmking 写道

直接用hashcode呗。

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

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

以前的一个思路：

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

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

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

11 楼 JE帐号 2011-04-20  

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

所以,我觉得这个事情,最后的比对最好还是放在内存里,第一步就是把大文件分割为很多分范围的小文件(可以理解为一个大粒度的排序),然后具体查找重复项时还是把文件读入内存即可.

毕竟千万个数据虽多,但是使劲的分一分,一个小文件也占不了多少内存..


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

10 楼 lenozhi 2011-04-20  

JE帐号 写道

lenozhi 写道

JE帐号 写道

千万行文本? 大概多大?
可以先考虑遍历一遍,然后把键值按范围先分割到几百个小文件中.然后再查找重复的.
虽然多读取一遍,但循环规模可以大大减小.

范围以什么划分？感觉基本上hashcode是我能想到且用到的最好的手段了。这个思路感觉上跟我上面写的类似，只不过我放到一个文件里了。划分到几百文件，其实就是hashmap内部实现的table

我觉得,其实怎么划分还是要看你那个30位的数字串的特点.尽量让结果平均点.

重点在于分割,这样你的比较规模能小很多.

这话对，有几组可以从业务角度分割。

9 楼 JE帐号 2011-04-20  

lenozhi 写道

JE帐号 写道

千万行文本? 大概多大?
可以先考虑遍历一遍,然后把键值按范围先分割到几百个小文件中.然后再查找重复的.
虽然多读取一遍,但循环规模可以大大减小.

范围以什么划分？感觉基本上hashcode是我能想到且用到的最好的手段了。这个思路感觉上跟我上面写的类似，只不过我放到一个文件里了。划分到几百文件，其实就是hashmap内部实现的table

我觉得,其实怎么划分还是要看你那个30位的数字串的特点.尽量让结果平均点.

重点在于分割,这样你的比较规模能小很多.

8 楼 lenozhi 2011-04-20  

JE帐号 写道

千万行文本? 大概多大?
可以先考虑遍历一遍,然后把键值按范围先分割到几百个小文件中.然后再查找重复的.
虽然多读取一遍,但循环规模可以大大减小.

范围以什么划分？感觉基本上hashcode是我能想到且用到的最好的手段了。这个思路感觉上跟我上面写的类似，只不过我放到一个文件里了。划分到几百文件，其实就是hashmap内部实现的table

7 楼 JE帐号 2011-04-20  

千万行文本? 大概多大?
可以先考虑遍历一遍,然后把键值按范围先分割到几百个小文件中.然后再查找重复的.
虽然多读取一遍,但循环规模可以大大减小.

或者直接利用数据来找,遍历一遍存到数据库中,然后一条sql...

6 楼 lenozhi 2011-04-20  

dennis_zane 写道

lenozhi 写道

dennis_zane 写道

感觉你需要的是布隆过滤器。

非100%准确排重

那么再加个md5计算比较，基本上可以达到接近100%的正确率，当然还是要看你项目要求了。

资金账号比较，还是不能用接近，呵呵。还有什么高见。我就是觉得数据库的唯一索引很行，不明白其实现原理，给讲讲不？

5 楼 dennis_zane 2011-04-20  

lenozhi 写道

dennis_zane 写道

感觉你需要的是布隆过滤器。

非100%准确排重

那么再加个md5计算比较，基本上可以达到接近100%的正确率，当然还是要看你项目要求了。

4 楼 lenozhi 2011-04-20  

dennis_zane 写道

感觉你需要的是布隆过滤器。

非100%准确排重

3 楼 dennis_zane 2011-04-20  

感觉你需要的是布隆过滤器。

2 楼 lenozhi 2011-04-20  

kimmking 写道

直接用hashcode呗。

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

1 楼 kimmking 2011-04-20  

直接用hashcode呗。