djb2 hash算法

hash function

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

这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

djb2 hash function

算法实现:

// generates a hash value for a sting
// same as djb2 hash function
//构造哈希函数 f(hash)= hash * 33 + c
unsigned int CountMinSketch::hashstr(const char *str) {
  unsigned long hash = 5381;
  int c;
  while (c = *str++) {
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
  }
  return hash;
}

数学实现: X = (a * X) + c; // "mod M", M = 2^32 或 2^64

this algorithm (k=33) was first reported by dan bernstein many years ago in comp.lang.c. another version of this algorithm (now favored by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.

参考

djb2:一个产生简单的随机分布的哈希函数 常见的hash算法及其原理

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python pygame安装

    SDL(Simple DirectMedia Layer)是一套开放源代码的跨平台多媒体开发库,使用C语言写成。SDL提供了数种控制图像、声音、输出入的函数,让...

    李小白是一只喵
  • ROS之Ubuntu 18.04下安装ROS[二]

    第一篇:ROS之初识机器人操作系统[一] 第二篇:ROS之Ubuntu 18.04下安装ROS[二]

    李小白是一只喵
  • 深度学习之初识深度学习[上]

    总而言之,机器学习是让机器可以得到新的规则.不仅仅是依靠程序员的设定获取固定的答案.

    李小白是一只喵
  • hash散列 introduction

    hash散列是在记录的存储位置与他的关键字之间建立的对应关系f, 使得每个key都对应一个存储位置, 查找时根据key的hash去查找.

    CoffeeLand
  • 纸上谈兵: 哈希表 (hash table)

    HASH 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系,而且集合A的某个元素只能对应集合B中的一个元素...

    Vamei
  • 面试题,如何在千万级的数据中判断一个值是否存在?

    当你看到这个标题的时候,你也许会想我可以使用hashmap之类的来存储值,然后get就是了。又或者把数据存在数据库里然后去判断就可以了。

    ImportSource
  • 如果世界上只有一种数据结构,那么我选择哈希!

    来源:blog.csdn.net/liweisnake/article/details/104779497

    芋道源码
  • Hash冲突和一致性

    在数据量很大的时候,就会出现hash之后的数值,指向相同的位置,也就是所谓的hash冲突。这个取决于hash算法的好坏,以及数据量的大小,hash算法越差,数据...

    灰子学技术
  • php hash算法类

    它可以将一个长度不固定的数据,通过算法,获取其特征值生成一个固定的,较短的数据,压缩其文件标识.

    仙士可
  • 【专业技术】STL hash_map使用(一)

    今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。 hash_map类在头文件hash_map中,和所有其...

    程序员互动联盟

扫码关注云+社区

领取腾讯云代金券