您的位置: 首页  >  IT文章  >  一些相干哈希函数的随记

一些相干哈希函数的随记

分类: IT文章 • 2024-11-30 12:11:49
一些有关哈希函数的随记

哈希函数

 

 

 

<!--[if supportFields]><span lang=EN-US><span style='mso-element:field-end'></span></span><![endif]-->

 

 

哈希函数

 

一个最简单最常见的哈希函数

 

 

int hash(int n, int m) {

    return n % m; // n & (m-1);

}

 

 

一个复杂的哈希函数

 

uint32_t hashint( uint32_t a)

{

a += ~(a<<15);

a ^=  (a>>10);

a +=  (a<<3);

a ^=  (a>>6);

a += ~(a<<11);

a ^=  (a>>16);

}

 

 

 

Java中用到的几个hash函数

 

 

 

static int hash(int h) {

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor).

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

 

 

 

 

 

 

 

private static int hash(int h) {

// Spread bits to regularize both segment and index locations,

// using variant of single-word Wang/Jenkins hash.

h += (h <<  15) ^ 0xffffcd7d;

h ^= (h >>> 10);

h += (h <<   3);

h ^= (h >>>  6);

h += (h <<   2) + (h << 14);

return h ^ (h >>> 16);

}

 

 

 

 

 

 

 

 

加密hash函数和非加密hash函数(cryptographic hash function &non-cryptographic hash function)

 

 

哈希函数设计的目的以及可能的问题

 

碰撞

 

冲突（Collision）， 也就是产生碰撞

 

 

碰撞是怎么回事，是怎么产生的？

 

 

int hash(int n, int m) {

    return n % m; // n & (m-1);

}

假设m＝4，输入n＝0，1，2，3计算出来的哈希值（0，1，2，3）能散列到不同的bucket中，但输入n＝4，5，6，7计算出来的哈希值（0，1，2，3）又散列到这些bucket，规律是输入的n＝n + 4 x i（i＝0…k）的这些输入计算出来的哈希值都相同，这就是所说的冲突（Collision）， 或碰撞

 

 

冲突（Collision）有什么问题

 

 

 

 

成功构造出大量使hash表发生碰撞的元素，导致系统被DoS

 

 

 

 

 

历史上就出现过利用Linux内核hash函数的漏洞，成功构造出大量使hash表发生碰撞的元素，导致系统被DoS，所以目前内核的大部分hash函数都有一个随机数作为参数进行掺杂，以使其最后的值不能或者是不易被预测。

 

 

 

 

这个问题放在现在是很难碰到了，基本上不可能Dos到系统被攻击的程度。

 

冲突（Collision）解决办法

 

 

雪崩效应

 

什么是雪崩效应

 

Full avalanche says that differences in any input bit can cause differences in any output bit.

 

 

 

 

哈希函数设计的考虑

 

 

性能

哈希函数需要设计得更好的性能， 效率高

 

单向

 

用随机数进行掺杂

 

 

目前Linux内核的大部分hash函数都有一个随机数作为参数进行掺杂，以使其最后的值不能或者是不易被预测。

 

 

 

安全性

 

 

 

 

 

加密hash函数

 

 

非加密hash函数

 

 

 

单向hash函数

 

有真正意义上的单向hash函数吗？

 

 

 

 

 

 

参考资料

<!--[if !supportLists]-->1、  <!--[endif]-->http://burtleburtle.net/bob/hash/integer.html

<!--[if !supportLists]-->2、  <!--[endif]-->https://naml.us/tags/thomas-wang/

<!--[if !supportLists]-->3、  <!--[endif]-->http://blog.reverberate.org/2012/01/state-of-hash-functions-2012.html

<!--[if !supportLists]-->4、  <!--[endif]-->https://opensource.googleblog.com/2011/04/introducing-cityhash.html

<!--[if !supportLists]-->5、  <!--[endif]-->https://en.wikipedia.org/wiki/Jenkins_hash_function

<!--[if !supportLists]-->6、  <!--[endif]-->https://en.wikipedia.org/wiki/CityHash

 

<!--[if !supportLists]-->7、  <!--[endif]-->https://en.wikipedia.org/wiki/One-way_function

相关推荐