文章出处:http://hunteagle.javaeye.com
注:最近因为在做和hash有关的题目,感到很纠结。虽然上学期数据结构学过,但是当时觉得hash没什么用,所以没有认真学~后悔啊~~~现在恶补一下~
计算理论中,没有Hash函数的说法,只有单向函数的说法。所谓的单向函数,是一个复杂的定义,大家可以去看计算理论或者密码学方面的数据。用“人 类”的语言描述单向函数就是:如果某个函数在给定输入的时候,很容易计算出其结果来;而当给定结果的时候,很难计算出输入来,这就是单项函数。各种加密函 数都可以被认为是单向函数的逼近。Hash函数(或者成为散列函数)也可以看成是单向函数的一个逼近。即它接近于满足单向函数的定义。
Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。除此以外,Hash函数往往应用于查找上。所以,在考虑使用Hash函数之前,需要明白它的几个限制:
1. Hash的主要原理就是把大范围映射到小范围;所以,你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
2. 由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。
3. 不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。
应用于加密的Hash函数已经探讨过太多了,在作者的博客里面有更详细的介绍。所以,本文只探讨用于查找的Hash函数。
Hash函数应用的主要对象是数组(比如,字符串),而其目标一般是一个int类型。以下我们都按照这种方式来说明。
一般的说,Hash函数可以简单的划分为如下几类:
1. 加法Hash;
2. 位运算Hash;
3. 乘法Hash;
4. 除法Hash;
5. 查表Hash;
6. 混合Hash;
下面详细的介绍以上各种方式在实际中的运用。
一 加法Hash
所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造如下:
static int additiveHash(String key, int prime)
{
int hash, i;
for (hash = key.length(), i = 0; i < key.length(); i++)
hash += key.charAt(i);
return (hash % prime);
}
这里的prime是任意的质数,看得出,结果的值域为[0,prime-1]。
二 位运算Hash
这类型Hash函数通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素。比如,标准的旋转Hash的构造如下:
static int rotatingHash(String key, int prime)
{
int hash, i;
for (hash=key.length(), i=0; i<key.length(); ++i)
hash = (hash<<4)^(hash>>28)^key.charAt(i);
return (hash % prime);
}
先移位,然后再进行各种位运算是这种类型Hash函数的主要特点。比如,以上的那段计算hash的代码还可以有如下几种变形:
1. hash = (hash<<5)^(hash>>27)^key.charAt(i);
2. hash += key.charAt(i);
hash += (hash << 10);
hash ^= (hash >> 6);
3. if((i&1) == 0)
{
hash ^= (hash<<7) ^ key.charAt(i) ^ (hash>>3);
}
else
{
hash ^= ~((hash<<11) ^ key.charAt(i) ^ (hash >>5));
}
4. hash += (hash<<5) + key.charAt(i);
5. hash = key.charAt(i) + (hash<<6) + (hash>>16) – hash;
6. hash ^= ((hash<<5) + key.charAt(i) + (hash>>2));
三 乘法Hash
这种类型的Hash函数利用了乘法的不相关性(乘法的这种性质,最有名的莫过于平方取头尾的随机数生成算法,虽然这种算法效果并不好)。比如,
static int bernstein(String key)
{
int hash = 0;
int i;
for (i=0; i<key.length(); ++i) hash = 33*hash + key.charAt(i);
return hash;
}
jdk5.0里面的String类的hashCode()方法也使用乘法Hash。不过,它使用的乘数是31。推荐的乘数还有:131, 1313, 13131, 131313等等。
使用这种方式的著名Hash函数还有:
// 32位FNV算法
int M_SHIFT = 0;
public int FNVHash(byte[] data)
{
int hash = (int)2166136261L;
for(byte b : data)
hash = (hash * 16777619) ^ b;
if (M_SHIFT == 0)
return hash;
return (hash ^ (hash >> M_SHIFT)) & M_MASK;
}
以及改进的FNV算法:
public static int FNVHash1(String data)
{
final int p = 16777619;
int hash = (int)2166136261L;
for(int i=0;i<data.length();i++)
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
除了乘以一个固定的数,常见的还有乘以一个不断改变的数,比如:
static int RSHash(String str)
{
int b = 378551;
int a = 63689;
int hash = 0;
for(int i = 0; i < str.length(); i++)
{
hash = hash * a + str.charAt(i);
a = a * b;
}
return (hash & 0x7FFFFFFF);
}
虽然Adler32算法的应用没有CRC32广泛,不过,它可能是乘法Hash里面最有名的一个了。关于它的介绍,大家可以去看RFC 1950规范。
四 除法Hash
除法和乘法一样,同样具有表面上看起来的不相关性。不过,因为除法太慢,这种方式几乎找不到真正的应用。需要注意的是,我们在前面看到的hash的 结果除以一个prime的目的只是为了保证结果的范围。如果你不需要它限制一个范围的话,可以使用如下的代码替代”hash%prime”: hash = hash ^ (hash>>10) ^ (hash>>20)。
五 查表Hash
查表Hash最有名的例子莫过于CRC系列算法。虽然CRC系列算法本身并不是查表,但是,查表是它的一种最快的实现方式。查表Hash中有名的例子有:Universal Hashing和Zobrist Hashing。他们的表格都是随机生成的。
六 混合Hash
混合Hash算法利用了以上各种方式。各种常见的Hash算法,比如MD5、Tiger都属于这个范围。它们一般很少在面向查找的Hash函数里面使用。
七 对Hash算法的评价
http://www.burtleburtle.net/bob/hash/doobs.html 这个页面提供了对几种流行Hash算法的评价。我们对Hash函数的建议如下:
1. 字符串的Hash。最简单可以使用基本的乘法Hash,当乘数为33时,对于英文单词有很好的散列效果(小于6个的小写形式可以保证没有冲突)。复杂一点可以使用FNV算法(及其改进形式),它对于比较长的字符串,在速度和效果上都不错。
2. 长数组的Hash。可以使用http://burtleburtle.net/bob/c/lookup3.c这种算法,它一次运算多个字节,速度还算不错。
八 后记
本文简略的介绍了一番实际应用中的用于查找的Hash算法。Hash算法除了应用于这个方面以外,另外一个著名的应用是巨型字符串匹配(这时的 Hash算法叫做:rolling hash,因为它必须可以滚动的计算)。设计一个真正好的Hash算法并不是一件容易的事情。做为应用来说,选择一个适合的算法是最重要的。
九 数组hash
inline int hashcode(const int *v)
{
int s = 0;
for(int i=0; i<k; i++)
s=((s<<2)+(v[i]>>4))^(v[i]<<10);
s = s % M;
s = s < 0 ? s + M : s;
return s;
}
注:虽说以上的hash能极大程度地避免冲突,但是冲突是在所难免的。所以无论用哪种hash函数,都要加上处理冲突的方法。
相关推荐
顶刊复现,基于Lyapunov的模型预测控制MPC方法,用于控制水下机器人AUV的路径跟踪问题trajectory tracking 具体的方法和建模过程可以参考文献 本代码包括水下机器人的fossen动力学模型,matlab的优化算法求解器,还包括非线性反步法backstepping 的对比代码非常划算,两种对比都有 ,顶刊复现; Lyapunov模型预测控制MPC; 水下机器人AUV路径跟踪; Fossen动力学模型; Matlab优化算法求解器; 非线性反步法backstepping对比,基于Lyapunov模型预测控制的水下机器人AUV路径跟踪方法对比研究
内容概要:本文由Seungri Song等人发表于期刊《光科学与应用》,主要介绍了新型计算三维极化敏感强度衍射断层扫描(PS-IDT),一种无需基准参考和惯性的基于矢量多切片束传播方法(MSBP)的3D成像新技术。这种方法利用明场显微镜附加LED环形阵列以及偏振组件即可完成多角度测量,实现3D琼斯矩阵重建并获得弱散射和多重散射样本的空间分布和光学各向异性的信息。文章不仅描述了实验装置、数据获取流程、重建步骤以及自我校准程序,还展示了对多种样品的成功测试,如马铃薯淀粉粒、小球藻和水熊虫,进一步验证了这一成像方式的应用前景和技术优势。 适用人群:光学工程研究人员、材料科学家及相关领域的学者与专业人士。 使用场景及目标:PS-IDT特别适合透明的微观结构,特别是那些存在复杂的光学特性并且可能引发多次散射现象的情况;旨在为生物医学研究提供高分辨率无损成像工具。此外它也可以扩展应用于需要精确表征物质内部结构特征的研究任务。 其他说明:目前该平台存在采集时间长的问题。未来发展方向可以考虑提高光源利用率来减少曝光时长以加快成像速度。与此同时,还可以探索将深度学习算法整合进重建过程中从而提升效率而不降
实验环境安装及其它介绍.html.zip
档位档位多
鸡骨白汤W-5001检验表格(食品添加剂食用香精质量验收记录表).docx
【机器人项目】飞行器与机器人通用控制体系项目集合-chy5.zip,整合了飞行器与机器人共用的控制体系,涵盖核心算法、硬件接口及通信协议。项目旨在实现跨平台的高效控制,适用于多种应用场景,提升系统兼容性与开发效率。
基于STM32的直流电机加减速正反转控制串口输出控制系统(P 1100009-基于STM32的直流电机加减速正反转控制串口输出控制系统(PCB 原理图 报告 源代码 proteus lcd1602) 功能描述:基于STM32平台 1、实现了电机控制正转、反转的功能 2、实现了电机控制加速、减速的功能 3、实现了串口输出控制信息的功能 4、串口可以模拟WIFI 蓝牙 RS232 等带有串口的功能。 资料包含: 1、源代码工程文件 2、仿真工程文件 3、lunwen报告1W字以上 4、原理图工程文件 5、PCB工程文件 ,核心关键词:STM32、直流电机、加减速、正反转控制、串口输出、控制信息、WIFI、蓝牙、RS232、源代码工程文件、仿真工程文件、原理图工程文件、PCB工程文件。,基于STM32的电机串口控制综合系统(含正反转、加减速及多种串口通信功能)
内容概要:本文探讨了高吞吐量网络链路异常检测中流量采样技术的应用及其效果。面对现代分布式信息系统频繁遭受的网络安全威胁,特别是互联网服务提供商(ISP)面临的威胁,作者提出一种通过减少数据采样频率以降低异常检测计算复杂度的方法。文中介绍了实验环境、系统架构、采用的数据聚合与采样方法以及用于检测异常的人工智能模型(基于自编码器神经网络)。通过对一个真实中型ISP生产环境中实际网络流量数据进行研究,该研究展示了即使在较低采样频率情况下仍能保持较高的异常检测准确性,尤其是针对持续时间较长的DDoS攻击更为显著。此外,论文还验证了所提系统的有效性和应用潜力,为构建高效的网络安全监控机制提供了新思路。 适用人群:对于计算机网络安全、数据分析或机器学习有兴趣的研究人员和从业人员,特别是那些专注于提高异常检测性能和应对高流量数据流的技术人员。 使用场景及目标:适用于希望在不影响业务操作的前提下引入额外层次防护措施的企业级网络管理员;研究者可参考本文中提出的流量预处理方式来探索不同的统计分布和采样间隔设置;企业可以通过部署该类系统快速响应潜在的安全事件并降低成本。
该项目是个人实践项目,答辩评审分达到90分,代码都经过调试测试,确保可以运行!,可用于小白学习、进阶。 该资源主要针对计算机、通信、人工智能、自动化等相关专业的学生、老师或从业者下载使用,亦可作为期末课程设计、课程大作业、毕业设计等。 项目整体具有较高的学习借鉴价值!基础能力强的可以在此基础上修改调整,以实现不同的功能。 欢迎下载,欢迎沟通,互相学习,共同进步!提供答疑!
在电子设计领域,尤其是模拟电路设计中,电子管起着至关重要的作用。这些古老的设备,尽管在现代数字电路中已不常见,但在某些特定的应用,如音频放大器、复古音响设备以及某些高功率射频系统中,电子管仍然占据主导地位。Altium Designer是一款广泛使用的电路设计软件,它提供了丰富的元器件库来支持各种设计需求,包括电子管。 标题"常用电子管原理图封装库(AD库)"指的是这个压缩包中包含了一系列常用电子管的原理图封装,适用于Altium Designer平台。这些封装是设计师在绘制电路原理图时需要用到的图形符号,它们精确地表示了电子管的引脚布局和电气特性,使得设计者能够直观地理解并连接各个元器件。 描述中的"6L,6S,12AU,5879,7199"列举了一些具体的电子管类型。这些型号分别代表了不同种类和用途的电子管。例如: - 6L和6S:这可能是对6系列电子管的泛称,6系列通常包含多种小型玻璃外壳的双三极管,用于音频放大和振荡电路。 - 12AU:这是一个常见的五脚功率放大管,常用于音频功放电路中,其内部结构可能包括一个控制栅极、两个屏极和两个阴极。 - 5879:这是一种九脚的电子管,常被用作音频功率放大器,具有较高的输出功率。 - 7199:这是一种特殊的高压大功率电子管,多用于雷达、工业设备或实验设备中。 ".SchLib"格式是Altium Designer的原理图库文件格式,这些封装库文件可以方便地导入到项目中,为设计者提供了一站式的电子管元器件选择,无需自己创建每个电子管的封装。 压缩包中的"4.5 - 电子管.SchLib"文件,很可能包含了上述所有电子管的封装,设计者可以通过Altium Designer打开并使用这些封装,直接拖放到原理图中,大大提高了设计效率和准确性。在使用时,设计师需要确保选择的封装与实际将要使用的电子管型号相符,以保证设计的电路能够正确地工作。 总结起来,这个"常用电子管原理图封装库(AD库)"是Altium Designer用户进行电子管相关电路设计的重要资源,它提供了多种常见电子管的封装,方便设计师快速绘制原理图,提高设计流程的效率。对于那些热衷于模拟电路和复古电子设备的人来说,这样的库是不可或缺的工具。。内容来源于网络分享,如有侵权请联系我删除。
《电力电子技术(第5版)》_王兆安_逆变电路
Matlab代码模拟枝晶生长可视化界面 ,Matlab; 枝晶生长; 代码模拟; 可视化界面; 生长过程模拟,Matlab模拟枝晶生长可视化界面
PFC5.02D煤层开挖案例代码,分步开挖,采用分步开挖 ,PFC5.02D;煤层开挖;分步开挖;案例代码,PFC5.0煤层分步开挖案例代码
系统采用B/S架构,集成Spring Boot(后端)、Vue.js(前端)和MySQL(数据库),通过RESTful API实现前后端分离。采用MyBatis-Plus优化数据访问,模块化设计与自动配置提升开发效率,结合数据库索引和读写分离确保性能,Element UI提供友好交互,整体具备高扩展性和可维护性。
花椒油检验表格(食品企业原辅料质量验收记录表).docx
系统采用B/S架构,集成Spring Boot(后端)、Vue.js(前端)和MySQL(数据库),通过RESTful API实现前后端分离。采用MyBatis-Plus优化数据访问,模块化设计与自动配置提升开发效率,结合数据库索引和读写分离确保性能,Element UI提供友好交互,整体具备高扩展性和可维护性。
基于adaline神经网络永磁同步电机多参数辨识 基于adaline神经网络永磁同步电机多参数辨识 1、利用adaline神经网络在线对电阻、电感和磁链进行辨识 ; 2、Adaline 算法本身具有自适应滤波的能力,保证输出辨识结果具有光滑理想的收敛曲线; 3、将Adaline与RLS对比,更能凸显神经网络的辨识优点; ,基于Adaline神经网络;永磁同步电机;多参数辨识;在线辨识;自适应滤波;输出收敛;Adaline算法与RLS对比,基于Adaline神经网络的永磁同步电机多参数辨识研究
基于STM32的水质 浊度检测仪设计与实现(详细设计说明书+ 10008-基于STM32的水质 浊度检测仪设计与实现(详细设计说明书+原理图PCB工程+源码工程+实物照片) 本次设计是设计一款水质检测设备,实现温度检查、水质检测的功能,将检测到的数据显示到显示器中,并实时记录系统的参数 本次系统需要对温度检测,使用的传感器为DS18B20,通过单总线的方式来完成系统温度检测 使用水质检测模块检查水的质量 通过传感器检测到的数据计算后的值实时刷新到显示器中,主要的功能包括以下几点: ①可以对温度实时检测; ②可以对水质实际值实时检测; ③水质浑浊预警 主要特点: 1.以STM32单片机为核心,配合水质模块; 2.主要完成系统的 功能控制、状态显示、信息检测以及报警硬件组建所单片机和传感器等元器件的选择; 3.完成系统控制的软件设计编程; 4.实现对水质检测、温度检查、预警的功能 内容包含: 1、原理图工程 2、PCB工程 3、源码工程 4、实物照片 5、详细介绍说明书-22531字 6、实物照片 7、浊度传感器资料 ,关键
8239_20161223025625.zip
伦理审查制度、物实验安全及伦理审查管理制度.docx