文档章节

字符串hash函数的本质

tiankonguse
 tiankonguse
发布于 2017/03/18 21:02
字数 679
阅读 20
收藏 0

前言

以前在《memcached 源码阅读之 字符串 hash 与 搜集的一些 字符串 hash》中已经记录了一些hash函数.

现在看其本质算法.

本质

如果对算法不感兴趣的人, 只需要看看这个小节就行了, 下面小节的都是经典书籍与人物的算法,都是本质算法穿上了一个马甲.

hash函数的本质是扫描字符串过程中, 根据之前的结果, 当前位置,当前字符的值使用一个公式计算出当前结果.

当然稍微复杂的hash算法会考虑之前所有的的结果,位置以及字符, 甚至会迭代多次.

这篇文章提到了一些书籍, 系统和一些人, 如果想要任何书籍的人都可以加公众号要相关书籍.

核心代码如下:

BKDR Hash

Brian KernighanDennis Ritchie的《The C Programming Language》一书被展示而得名,是一种简单快捷的hash算法,也是Java目前采用的字符串的Hash算法。

有人说将乘法分解为位运算及加减法可以提高效率.

但其实在Intel平台上,CPU内部对二者的处理效率都是差不多的;

在ARM这类RISC系统上由于ARM内部使用Booth’s Algorithm来模拟32位整数乘法运算,它的效率与乘数有关.

SDBM Hash

在开源项目SDBM(一种简单的数据库引擎)中被应用而得名,它与BKDRHash思想一致,只是种子不同而已。

RS Hash

Robert Sedgwicks在其《Algorithms in C》一书中展示而得名。

AP Hash

Arash Partow发明的一种hash算法。

JS Hash

Justin Sobel编的一种hash算法。

DEK hash

本算法是由于Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。

FNV Hash

Unix system系统中使用的一种著名hash算法,后来微软也在其hash_map中实现。

DJB Hash

由Daniel J. Bernstein教授编的一种hash算法。

PJW Hash

本算法是基于AT&T贝尔实验室的Peter J. Weinberger的论文而发明的一种hash算法。

CRC32 hash

这个就不需要介绍了.

参考资料

General Purpose Hash Function Algorithms

其他文章

UNION架构篇 UNION优化篇 UNION诞生篇 union运营篇 谈谈cache 浪潮之巅 排名算法

关于作者

曾是一名ACMer, 现在是鹅长视频部门的后台开发

这里主要记录工作中的技术架构与经验,计算机相关的技术,数学、算法、生活上好玩的东西

长按二维码关注作者, 了解作者发布的最新好玩的东西

© 著作权归作者所有

tiankonguse
粉丝 0
博文 15
码字总数 26545
作品 0
深圳
程序员
私信 提问
PHP中HASH函数的优化技巧

Hash数据结构是一种非常常见的数据结构,作为一个程序员,你可能每天都在和它接触, 尽管很多时候你可能没有意识到。Hash在PHP内核中扮演了非常重要的角色,数组、变量作用域、函数参数列表等...

ChefXu
2015/12/04
1K
4
使用create_function()创建"匿名"函数

1.使用create_function()创建"匿名"函数 前面提到PHP5.3中才才开始正式支持匿名函数,说到这里可能会有细心读者有意见了,因为有个函数是可以生成匿名函数的: create_function函数, 在手册里...

金于虎
2016/12/23
37
0
Python 源码的考古(四) 1.0.1 版

1.0.1 版的 README 文件提到这是对正式发布的 Python 1.0 的补丁, 主要解决可移植性问题. 大致变化 我看和 0.9.1 版差别, 首先是目录结构整理了一下, 以前是所有源文件都混在一个 src 目录下...

刘军兴
2016/01/04
90
0
(一) 实现用字符串作为switch的case子句

1. 问题: 实现用字符串作为switch语句的case子句。形如: 2. 基本思路 1、用hash函数,设置字符串的hash值,将字符串转换为1个整数; 2、利用c++11自定义文字常量的语法,定义一个constexpr...

geoff1314
2017/04/25
0
0
Java源码解读扫盲【String篇】

一.String类的定义 String类被定义为final类,意味着它不能被继承,它是个不可变类,并发程序最喜欢不可变量了。 String类实现了Serializable, Comparable<String>, CharSequence接口。 Comp...

lemonLove
2018/03/02
461
2

没有更多内容

加载失败,请刷新页面

加载更多

架构师的十大学习步骤

架构师有十大步第一步: 学习两种抽象视角 (Abstraction View) 架构师的第二步: 关心下层的变动自由度 ( 没钱就改版,改版就有钱 ) 架构师的第三步: < 系统架构控制力 > 支撑 < 商业竞争话...

请叫我小可爱呀
2分钟前
1
0
node处理静态模板无法自动引入问题

本文是在参考张鑫旭大神的文章所写,对其进行了一些优化,在原文中只对入口文件 import/import-example.html做了监控,当footer.html发生改变时,最终文件并不会发生变化,此时需要对import/...

litCabbage
2分钟前
1
0
关于PHP的命名空间

这篇文章介绍的内容是关于PHP的命名空间 ,有着一定的参考价值,现在分享给大家,有需要的朋友可以参考一下 什么是PHP命名空间 PHP手册:从广义上来说,命名空间是一种封装事物的方法。在很多...

chenhongjiang
4分钟前
1
0
sync.Once 多次调用一次执行

demo package mainimport ("fmt""sync")func main() {var once sync.OnceonceFunc := func() {fmt.Println("this func do once")}done := make(chan bo......

李琼涛
4分钟前
1
0
AliOS Things 3.0应用笔记:http client简单应用

简介 AliOS Things 3.0版本于9月27日在云栖大会正式发布,在新版本中带来了全新的应用开发框架,帮助用户快速构建自己的应用。使用户可以更专注于自身应用的开发。 AliOS Things 3.0版本新增...

阿里云官方博客
12分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部