|
锁定老帖子 主题：将HashMap文件化
精华帖 (0) :: 良好帖 (1) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-04-20
JE帐号 写道 lenozhi 写道 JE帐号 写道 千万行文本? 大概多大?
可以先考虑遍历一遍,然后把键值按范围先分割到几百个小文件中.然后再查找重复的. 虽然多读取一遍,但循环规模可以大大减小. 范围以什么划分？感觉基本上hashcode是我能想到且用到的最好的手段了。这个思路感觉上跟我上面写的类似，只不过我放到一个文件里了。划分到几百文件，其实就是hashmap内部实现的table 我觉得,其实怎么划分还是要看你那个30位的数字串的特点.尽量让结果平均点. 重点在于分割,这样你的比较规模能小很多. 这话对，有几组可以从业务角度分割。 |
| 返回顶楼 | |
|
发表时间：2011-04-20
最后修改：2011-04-20
我的印象里java的io操作是比较弱的,文件操作性能很差.
所以说,新拿到一个值,虽然你可以算出来应该在什么位置,并用skip直接定位过去,可是在io内部还是给read中间哪些值. 再说,你向文件里插入一个值,我印象是不可能向链表似的前后改下索引就行了,好像给整个复制.... 所以,我觉得这个事情,最后的比对最好还是放在内存里,第一步就是把大文件分割为很多分范围的小文件(可以理解为一个大粒度的排序),然后具体查找重复项时还是把文件读入内存即可. 毕竟千万个数据虽多,但是使劲的分一分,一个小文件也占不了多少内存.. 反正,我以前用io的时候就是这个印象. 所以我一直觉得数据库应该对于文件系统的操作进行了底层的控制,比如从10000跳到20000,他是直接跳过去找到,而不是顺序读过去的. |
| 返回顶楼 | |
|
发表时间：2011-04-20
最后修改：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冲突的方法 |
| 返回顶楼 | |
|
发表时间：2011-04-20
准备实现自己的想法，写一个。到时欢迎大家拍砖 @-@ |
| 返回顶楼 | |
|
发表时间：2011-04-20
JE帐号 写道 我的印象里java的io操作是比较弱的,文件操作性能很差.
所以说,新拿到一个值,虽然你可以算出来应该在什么位置,并用skip直接定位过去,可是在io内部还是给read中间哪些值. 再说,你向文件里插入一个值,我印象是不可能向链表似的前后改下索引就行了,好像给整个复制.... 用RandomAccessFile可以实现我描述的（已经实现了）。 JE帐号 写道 反正,我以前用io的时候就是这个印象. 所以我一直觉得数据库应该对于文件系统的操作进行了底层的控制,比如从10000跳到20000,他是直接跳过去找到,而不是顺序读过去的. 数据库底层很可能是跳过文件系统，直接玩的。 |
| 返回顶楼 | |
|
发表时间：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，不知道能搞成啥样。 |
| 返回顶楼 | |
|
发表时间：2011-04-20
索引大多都是B+树，可以保证分布平均，树深度不深，hash最坏的情况全落一个桶，唯一肯定是需要排序的，千万这个量不用纠结，与其考虑算法，应该优先考虑记录减肥降低磁盘io
|
| 返回顶楼 | |
|
发表时间：2011-04-20
ppgunjack 写道 索引大多都是B+树，可以保证分布平均，树深度不深，hash最坏的情况全落一个桶，唯一肯定是需要排序的，千万这个量不用纠结，与其考虑算法，应该优先考虑记录减肥降低磁盘io
原来是这样子，学习了。 |
| 返回顶楼 | |
|
发表时间：2011-04-20
首先看你的KEY是什么特点，设定一个规则，将HASHMAP分散到多个文件。不过我觉得这么搞还不如就放在数据库里好了
|
| 返回顶楼 | |
|
发表时间：2011-04-20
数据库是可以越过系统调用直接操纵磁盘，不过很多应用还是会架在OS的文件系统上访问数据
其实考虑类似bdb这样的嵌入式数据库比自己写类似应用要更容易，适用范围保护也更好，结合OS的内存虚拟磁盘使用可以很灵活构建方案 |
| 返回顶楼 | |
