字符串hash的研究

字符串哈希的研究

关于hash函数，其存在的理由就是让存入的数据得到好的立足之地（就像给存入的数据一个唯一的门牌号，我们就可以很容易的找到它所在地点），而且不让数据扎堆也是很重要的（而不是让数据扎堆，毕竟在一间几十上百号人的屋子找个人相对比较困难的）。

由此，hash函数应该，也必须要让数据“散开”，数据不必争房子住，如此冲突就少了，社会也就和谐了。

以下为hash设计历程：（一步一步、做足苦力啊！先贴代码，然后是自己的一点分析，再后是测试的统计数据）

设计1：

private int FirstHash(String str){
        char[] chars = str.trim().toCharArray();
        int hash = 0;
        int count = 0;
        int length = chars.length;
        while (count < length) {
                   hash = (int) chars[count] + (hash << 8) + (hash << 16);
                   count++;
        }
        return hash & 0x7FFFFFFF;
}

 

设计2：

while (count < length) {
         hash = (int) chars[count] + (hash << 8) + (hash << 16) – hash;
         count++;
}

 

设计3：（只改动了一个数据哦！！！）

while (count < length) {
          hash = (int) chars[count] + (hash << 7) + (hash << 16) – hash;
          count++;
}

 

设计4：

while (count < length) {
      hash = (int) chars[count] + (hash << 7) + (hash << 16) + (hash << 24) – hash;
      count++;
}

附：hashSet、hashMap的哈希函数（以便比较）

private int SystemHash(String s) {
      int hash = s.hashCode();
      hash ^= (hash >>> 20) ^ (hash >>> 12);
      return (hash ^ (hash >>> 7) ^ (hash >>> 4));
}

 

 

必须说明：现在只测试“英文单词”为存入的数据对象。

分析：

    刚开始想到设计1是根据字符的二进制编码的。Java中char型数据是2 byte。但想到超过ASCLL值256的char型数据没法手工输入（我试了一下，char型数据超过256的都打印个“?”），最常用的英文单词实际上就是char数组，每个字母必不超过256。说了这么多，只想说明此时一个字母虽然是2 byte，但是变成二进制的话只有低8位存数据，高8位就都是 0 了。

OK，上面的前提是解释我的测试的铺垫。

     将上面的32位存储结构分为四份（即将一个int型数据8位8位的分为四份，并分别标号为1、2、3、4）。

假如现在有一个数组a，数组存有5个元素，假设为“12345”，设计1的哈希过程是这样的：

 

 

最终插入“12345”完成！！！

    这个设计在存储数据少的时候还是比较让人满意的，但是，一看这个表格，顿时就惊呆了，这个表格说明了什么——加入hash表的长度为1000，那么取余后得到的索引位置只与存入的字符串的最后2个字母有关！！！那肯定是不行的，加入有“abcde”和“cbade”存入，那肯定得撞车了。

    然后，稍微改进了一下，得到设计2：

    同样的有：

嗯，现在好多了，3、4两个低位都与整个数组元素扯上了关系，当再加入“abcde”和“cbade”后，再撞车已经几乎不可能发生了。

    现在想想，既然扯关系，那不如把关系扯得错综复杂一点，然后就得到设计3：把“hash<<8”改为“hash<<7”,即标号4的低位模块的数据没有全部移到标号3的模块，而是插一腿到原来自己呆的模块。此时，额，已经很难追寻踪迹了。。。

    那设计4怎么又加上“hash<<24”呢？很简单，就是让hash更复杂，但这个复杂是有道理的，目的就是让标号1和2的模块也与存入的整个字符串扯上关系（由表可见，标号1的模块只与少数字符数组关联），自此，便可大胆提出类似巴赫猜想的假设：如果字符数组的长度越长，那么设计4的散列效果肯定比较好。

下表为根据运行结果得到的统计数据：

 

现在只能看着数据发呆了，不管怎么说，还是能得到些信息的：

    1. 设计2和设计4的数据基本一样，也就是说“hash<<8”和“hash<<7”是差不多的，“hash<<7”并不能增加散列效果；

    2. 在哈希表容量少、插入数组短的时候，自己的设计还是可以的，但是容量大、插入数据长的时候，那就比较劣了。

    3. “hash<<24”这一句并没有给设计4带来长数组的散列效果。（唉，有时候，猜想没有得到 验证也是很痛苦的）。

    4. 最重要的一点：我输了，彻底的输了，平均下来，系统的hash函数就远远抛下了我写的hash，特别是容量更大、数组长度更长的时候，差距就更明显了。

    不过，没有绝对好的hash，只有相对合适的hash。

    探索路程，依然的，在路上……