Time33算法

Hash-链地址法

一、哈希(Hash)简介

Hash,一般翻译做“散列”,也有直接音译为”哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。

这种转换是一种压缩映射,也就是散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。用数学语言来讲就是空间变换,从一个自变量空间映射到另一个值空间。也可以认为是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

使用哈希查找有两个步骤:
  1. 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下,不同的键会被转换为不同的索引值,但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况,所以哈希查找的第二个步骤就是处理冲突。

  2. 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法

哈希表是一个在时间和空间上做出权衡的经典例子。

如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);
如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。

哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

目前常用的hash方法有:开放地址法、再哈希法、链地址法(拉链法)

二、Time33方法

目前普遍采用的哈希算法是time33,又称DJBX33A (Daniel J. Bernstein, Times 33 with Addition)。这个算法被广泛运用于多个软件项目,Apache、Perl和Berkeley DB等。对于字符串而言这是目前所知道的最好的哈希算法,原因在于该算法的速度非常快,而且分类非常好(冲突小,分布均匀)。

对于一个Hash函数,评价其优劣的标准应为随机性,即对任意一组标本,进入Hash表每一个单元(cell)之概率的平均程度,因为这个概率越平均,数据在表中的分布就越平均,表的空间利用率就越高。

Time33算法:

对字符串的每个字符,迭代的乘以33
hash(i) = hash(i-1) * 33 + str[i]

三、PHP中Time33实现方式

static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
     register ulong hash = 5381;
 
     /* variant with the hash unrolled eight times */
     for (; nKeyLength >= 8; nKeyLength -= 8) {
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
          hash = ((hash << 5) + hash) + *arKey++;
     }
     switch (nKeyLength) {
          case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
          case 1: hash = ((hash << 5) + hash) + *arKey++; break;
          case 0: break;
     }
     return hash;
}

为什么初始值是5381

5381(001 010 100 000 101),据说hash后的分布更好一些。

四、参考

1、PHP内核中的神器之HashTable
2、详解time33 hash函数
3、解决Hash碰撞冲突方法总结
4、Hash算法和Hash冲突碰撞
5、位与&,位或|,位异或^运算,以及运用场景
6、常见算法及问题场景——散列(哈希)

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 转载自:https://halfrost.com/go_map_chapter_one/ https://half...
    HuJay阅读 6,209评论 1 5
  • 散列表,它是基于高速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构能够理解为一个线性表...
    江江JJ阅读 1,930评论 0 6
  • 散列表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表...
    yeying12321阅读 3,712评论 0 6
  • 一.概念 哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可...
    lfp901020阅读 3,032评论 0 2
  • 为什么要对自己好一点? 这句话我问了很多人,有人说是因为这个世界上只有这样一个自己,不对自己好一点又怎么对别人好一...
    没什么特别就是喜欢阅读 1,318评论 1 2