HashCrack程序数据及索引设计

概述  前文已经讲述，字母全排列是个惊人的数字，即使只遍历小写字母和数字6个全排列也有36^6 = 2176782336，21亿多个，7个排列36^7 = 78364164096，783亿多，8个排列36^8 = 2821109907456，2.8万亿多个，数字非常惊人。Md5反查是个string-string的映射，16-N个字符的映射，如果考虑hex模式的md5那就是32-N的映射，考虑映射人们最

前文已经讲述，字母全排列是个惊人的数字，即使只遍历小写字母和数字6个全排列也有36^6 = 2176782336，21亿多个，7个排列36^7 = 78364164096，783亿多，8个排列36^8 = 2821109907456，2.8万亿多个，数字非常惊人。Md5反查是个string-string的映射，16-N个字符的映射，如果考虑hex模式的md5那就是32-N的映射，考虑映射人们最先想到的可能都是数据库存储方式，我也首先想到了用数据库存储，分别考察了一下sqlite和berkeleydb，但测试下来制造数据的速度很慢，sqlite加索引大概只能到5w条记录/s，不加索引为10w条/s，berkeleydb用单条模式大概只能到4.5w条/s，这个速度已经很慢了，更难于接受的是如果写1000w对sqlite加索引来说不是耗时200s，而是2000s了，也就是说耗时随单个数据文件记录的条数增多几乎成平方模式递增，而不是简单的线性递增，这是很要命的，就算制造1亿条数据耗时也是惊人，我的实测中没有测试过用sqlite制造1000w条以上的数据，在我心目中已经否定了那种模式。虽然我知道很多号称有多少亿条数据的网站其实都是用的数据库，我不知道他们花了多少时间制造数据，或者几天，或者几个月，或者更长时间，反正我对采用普通数据库模式制造数据完全持否定态度，嵌入式速度太慢，其他数据库则不光速度慢而且也不适合分布式应用，难道用户每装个点还要装个MysqL之类的数据库，几乎不可能啊。

下面说说我的方法，我本来第一版本是计划先不做文件式数据库的，第一版本来只规划了做内存数据，充分榨取每一个字节，关于内存数据库我实现了好几个版本，下面分别介绍一下：

版本1：hash模式

用char key[16];做键，char pass[n];做内容，由于hash桶占用了一些字节：

DWORD h,nKeyLen; //hash键值,字符串长度

DWORD tag; //私有值，默认为0提供给外部使用

bucket *pListNext; //hash表双链的下一个节点

bucket *pListPrev; //hash表双链的上一个节点

bucket *pNext; //拉链的下一个节点

VALUE second; //具体数据

_Elem first[0]; //first键

用这个hash模式大概存储一个6个字符的串的md5信息花了50个字节，花费太多，结果自然存不了多少数据，该方案作为第一验证方案，除了花费内存太多还是个能通过的方案。

版本2：hash简化方案

在上述版本基础上简化桶设计，抛弃作为标准桶的一些字段，精简之后如下:

DWORD h; //hash键值

bucket *pNext; //拉链的下一个节点

byte nKeyLen; //字符串长度

VALUE second; //具体数据

_Elem first[0]; //first键

该版本存储一个6个字符的串的md5信息需要31个字节，比版本1少了很多，进步一些了。

方案1和方案2速度都很快。

版本3：vector方案

考虑到hash占用内存较多，采用vector方案，直接存储

Char mm[16];

Char pass[n];

存储一个6个字符的串的md5信息需要22个字节，该方案排序速度太慢，查找速度肯定也比不上版本1和版本2，之后还测试过将vector里面存储指针，那种模式每个6个字符的串的md5信息占用内存26个，接近hash版本，排序速度比直接存储数据的好一点，但也还是很慢，总之这个方案作为一个过度方案最终也被放弃了。

方案4：全文件Hash紧缩方案

以上这些方案的特点是都存储了char mm[16]; 也就是说存储部分都有计算出来的md5，经过思考之后觉得可以放弃存储md5，不存储md5是个很妙的想法，继续发挥hash思想，也不保存根据md5计算出来的hash值本身，只将该md5和串的信息关联到hash值的模所在的索引节点，这样就将索引节点信息减少到极致：

size_t coffset; //content offset low

unsigned short a:12; //切分为12,4

unsigned short b:4; //4，为下一个冲突值的索引序数，如果没有就为0

size_t nextindex; //冲突条目的存储序号，为0表示没有冲突

使用该索引可让单文件最多支持内容16T，最多687亿记录，具体实现的时候由于全使用文件所以速度比较慢，速度退化到sqlite之类同一级别了，不过这个设计思想为方案5提供了借鉴，如果跟方案5一样用大块内存辅助，速度大概可以上升一个级别，不过由于没有具体实现，待研究之后再做评估。

方案5：hash紧缩内存方案

学习方案4的设计思想，考虑仅在内存里面实现一个紧凑型文件，由于只考虑内存可表示的32位范围，所以简化索引节点定义如下：

Size_t coffset; pass相对于内容区首的偏移

Size_t nindex; 冲突节点下一个序，如果为0则表示没有冲突

内容区存储更简单，每个字符串直接保存，最后的0也保存，这样每个字符串自然分开，对一个6个字符长的串来说，保存一个信息只需要15个字节，真的是省啊，1亿个字符串也只要大约1.5g左右硬盘就够了。此方案虽然很妙，但实现的时候却费了一些周折，具体做的时候也做过好几个版本，由于考虑该方案的内容和索引最后都可以直接保存到文件，所以该方案对位置的保存都用的是相对位置，也由于想让索引节点信息简单，最初是让冲突索引采用线性步长跳跃方法，测试之后发现这个方法速度奇慢，而且还有个非常讨厌的问题，随着数据量的增多冲突扩散越来越厉害，耗时非线性的陡峭增长。放弃这个实现之后还是回到了经典的拉链法，拉链法速度就是快，但拉链法处理索引节点虽然容易，但要让索引信息可直接保存却要花一些脑子，最后采用先用内存扩展拉链，待全部索引构造好之后再把拉链出来的部分重新填到原始索引区中的空区，并修正对应索引相对位置。这个方法的精妙之处在于既省空间又有速度，最令人兴奋的是采用该方法耗时随着数据量的增大是线性增长，最后的实现在我的笔记本上大概100w/s，1亿条记录从字母组合到最终生成索引文件也只要不到2分钟的时间，制造了一些数据之后统计了一下，冲突节点比例大概占26%-35%，也就是说有65%以上的数据只要一次hash就直接命中，平均拉链长度1.2左右，最长拉链10，总体还是很满意的。

原本第一版没有考虑这个可存储的方案，但花了几天就搞定了一个基本可用的存储方案还是很令人兴奋的，虽然该存储方案还有一些问题没有彻底解决，但已经有进一步处理的办法，待下一个相对空闲时间段再仔细研究一下，定会有更简洁的实现做出来，至于待解决的是什么问题以及如何解决那些问题还是等我代码写好了再写出来吧。

总结

以上是内存溢出为你收集整理的HashCrack程序数据及索引设计全部内容，希望文章能够帮你解决HashCrack程序数据及索引设计所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。