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

直接用hashcode呗。

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

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

非100%准确排重

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

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

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

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

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

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

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