精华内容
下载资源
问答
  • LHash:轻量级哈希函数
  • 这是 Murmur3 哈希函数的 C 语言移植版本,Murmur3 是一个非加密的哈希算法,主要设计目的是快速和高质量,原有代码是 C 的,先移植到 C 并兼容标准 C 和 gcc 编译器。 标签:murmur3
  • 创建最小的完美哈希函数 为给定的键集生成最小的完美哈希函数。 给定的代码模板填充有参数,因此输出是实现哈希函数的代码。 可以轻松地为任何编程语言构造模板。 安装 最小的完美哈希函数生成器是用纯Python编写的...
  • 哈希函数

    万次阅读 多人点赞 2018-03-01 08:12:14
    在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。在介绍一些集合...

    什么是 Hash

    Hash(哈希),又称“散列”。

    散列(hash)英文原意是“混杂”、“拼凑”、“重新表述”的意思。

    在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。

    在介绍一些集合时,我们总强调需要重写某个类的 equlas() 方法和 hashCode() 方法,确保唯一性。这里的 hashCode() 表示的是对当前对象的唯一标示。计算 hashCode 的过程就称作 哈希。

    为什么要有 Hash

    我们通常使用数组或者链表来存储元素,一旦存储的内容数量特别多,需要占用很大的空间,而且在查找某个元素是否存在的过程中,数组和链表都需要挨个循环比较,而通过 哈希 计算,可以大大减少比较次数

    这里写图片描述

    举个栗子:

    现在有 4 个数 {2,5,9,13},需要查找 13 是否存在。

    1.使用数组存储,需要新建个数组 new int[]{2,5,9,13},然后需要写个循环遍历查找:

        int[] numbers = new int[]{2,5,9,13};
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 13){
                System.out.println("find it!");
                return;
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    这样需要遍历 4 次才能找到,时间复杂度为 O(n)。

    2.而假如存储时先使用哈希函数进行计算,这里我随便用个函数:

     H[key] = key % 3;
    
    • 1
    • 2

    四个数 {2,5,9,13} 对应的哈希值为:

     H[2] = 2 % 3 = 2;
     H[5] = 5 % 3 = 2;
     H[9] = 9 % 3 = 0;
     H[13] = 13 % 3 = 1;
    
    • 1
    • 2
    • 3
    • 4
    • 5

    然后把它们存储到对应的位置。

    当要查找 13 时,只要先使用哈希函数计算它的位置,然后去那个位置查看是否存在就好了,本例中只需查找一次,时间复杂度为 O(1)。

    因此可以发现,哈希 其实是随机存储的一种优化,先进行分类,然后查找时按照这个对象的分类去找。

    哈希通过一次计算大幅度缩小查找范围,自然比从全部数据里查找速度要快。

    比如你和我一样是个剁手族买书狂,家里书一大堆,如果书存放时不分类直接摆到书架上(数组存储),找某本书时可能需要脑袋从左往右从上往下转好几圈才能发现;如果存放时按照类别分开放,技术书、小说、文学等等分开(按照某种哈希函数计算),找书时只要从它对应的分类里找,自然省事多了。

    哈希函数

    哈希的过程中需要使用哈希函数进行计算。

    哈希函数是一种映射关系,根据数据的关键词 key ,通过一定的函数关系,计算出该元素存储位置的函数。

    表示为:

    address = H [key]

    几种常见的哈希函数(散列函数)构造方法

    • 直接定址法 
      • 取关键字或关键字的某个线性函数值为散列地址。
      • 即 H(key) = key 或 H(key) = a*key + b,其中a和b为常数。
      • 比如这里写图片描述
    • 除留余数法 
      • 取关键字被某个不大于散列表长度 m 的数 p 求余,得到的作为散列地址。
      • 即 H(key) = key % p, p < m。 
      • 比如这里写图片描述
    • 数字分析法 
      • 当关键字的位数大于地址的位数,对关键字的各位分布进行分析,选出分布均匀的任意几位作为散列地址。
      • 仅适用于所有关键字都已知的情况下,根据实际应用确定要选取的部分,尽量避免发生冲突。
      • 比如 这里写图片描述
    • 平方取中法 
      • 先计算出关键字值的平方,然后取平方值中间几位作为散列地址。
      • 随机分布的关键字,得到的散列地址也是随机分布的。
      • 比如 这里写图片描述
    • 折叠法(叠加法) 
      • 将关键字分为位数相同的几部分,然后取这几部分的叠加和(舍去进位)作为散列地址。
      • 用于关键字位数较多,并且关键字中每一位上数字分布大致均匀。 
      • 比如 这里写图片描述
    • 随机数法 
      • 选择一个随机函数,把关键字的随机函数值作为它的哈希值。
      • 通常当关键字的长度不等时用这种方法。 

    构造哈希函数的方法很多,实际工作中要根据不同的情况选择合适的方法,总的原则是尽可能少的产生冲突

    通常考虑的因素有关键字的长度分布情况哈希值的范围等。

    如:当关键字是整数类型时就可以用除留余数法;如果关键字是小数类型,选择随机数法会比较好。

    哈希冲突的解决

    选用哈希函数计算哈希值时,可能不同的 key 会得到相同的结果,一个地址怎么存放多个数据呢?这就是冲突。

    常用的主要有两种方法解决冲突:

    1.链接法(拉链法)

    拉链法解决冲突的做法是: 
    将所有关键字为同义词的结点链接在同一个单链表中。

    若选定的散列表长度为 m,则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。

    凡是散列地址为 i 的结点,均插入到以 T[i] 为头指针的单链表中。 
    T 中各分量的初值均应为空指针。

    在拉链法中,装填因子 α 可以大于 1,但一般均取 α ≤ 1。

    这里写图片描述

    2.开放定址法

    用开放定址法解决冲突的做法是:

    用开放定址法解决冲突的做法是:当冲突发生时,使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探测到开放的地址则表明表中无待查的关键字,即查找失败。

    简单的说:当冲突发生时,使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到

    按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

    a.线性探查法

    hi=(h(key)+i) % m ,0 ≤ i ≤ m-1 

    基本思想是: 
    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1],…,直到 T[m-1],此后又循环到 T[0],T[1],…,直到探查到 有空余地址 或者到 T[d-1]为止。

    b.二次探查法

    hi=(h(key)+i*i) % m,0 ≤ i ≤ m-1 

    基本思想是: 
    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1^2],T[d+2^2],T[d+3^2],…,等,直到探查到 有空余地址 或者到 T[d-1]为止。

    缺点是无法探查到整个散列空间。

    c.双重散列法

    hi=(h(key)+i*h1(key)) % m,0 ≤ i ≤ m-1 

    基本思想是: 
    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+h1(d)], T[d + 2*h1(d)],…,等。

    该方法使用了两个散列函数 h(key) 和 h1(key),故也称为双散列函数探查法。

    定义 h1(key) 的方法较多,但无论采用什么方法定义,都必须使 h1(key) 的值和 m 互素,才能使发生冲突的同义词地址均匀地分布在整个表中,否则可能造成同义词地址的循环计算。

    该方法是开放定址法中最好的方法之一。

    哈希的应用

    • 哈希表
    • 分布式缓存

    哈希表(散列表)

    哈希表(hash table)是哈希函数最主要的应用。

    哈希表是实现关联数组(associative array)的一种数据结构,广泛应用于实现数据的快速查找。

    这里写图片描述

    用哈希函数计算关键字的哈希值(hash value),通过哈希值这个索引就可以找到关键字的存储位置,即桶(bucket)。哈希表不同于二叉树、栈、序列的数据结构一般情况下,在哈希表上的插入、查找、删除等操作的时间复杂度是 O(1)。

    查找过程中,关键字的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。 
    影响产生冲突多少有以下三个因素:

    1. 哈希函数是否均匀;
    2. 处理冲突的方法;
    3. 哈希表的加载因子。

    哈希表的加载因子和容量决定了在什么时候桶数(存储位置)不够,需要重新哈希。

    加载因子太大的话桶太多,遍历时效率变低;太大的话频繁 rehash,导致性能降低。所以加载因子的大小需要结合时间和空间效率考虑。

    在 HashMap 中的加载因子为 0.75,即四分之三。

    分布式缓存

    网络环境下的分布式缓存系统一般基于一致性哈希(Consistent hashing)。简单的说,一致性哈希将哈希值取值空间组织成一个虚拟的环,各个服务器与数据关键字K使用相同的哈希函数映射到这个环上,数据会存储在它顺时针“游走”遇到的第一个服务器。可以使每个服务器节点的负载相对均衡,很大程度上避免资源的浪费。

    在动态分布式缓存系统中,哈希算法的设计是关键点。使用分布更合理的算法可以使得多个服务节点间的负载相对均衡,可以很大程度上避免资源的浪费以及部分服务器过载。 使用带虚拟节点的一致性哈希算法,可以有效地降低服务硬件环境变化带来的数据迁移代价和风险,从而使分布式缓存系统更加高效稳定。

    Thanks

    http://www.nowamagic.net/librarys/veda/detail/1273

    http://blog.csdn.net/cywosp/article/details/23397179/

    http://www.cnblogs.com/qiaoshanzi/p/5295554.html

    http://baike.baidu.com/view/549615.htm

    https://books.google.co.jp/books?id=wCWmdhdX1AYC&pg=PA214&lpg=PA214&dq=%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95&source=bl&ots=5ieOT99Dob&sig=UcYbua2lwYocCQr32HF0XDF34h4&hl=zh-CN&sa=X&ved=0ahUKEwj104zw__fPAhUDw7wKHf3cAhIQ6AEISzAJ#v=onepage&q=%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95&f=false

    http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/chazhao/chazhao9.4.3.3.htm

    http://www.cnblogs.com/qiaoshanzi/p/5295554.html

    (function () { ('pre.prettyprint code').each(function () { var lines =  (this).text().split(\n).length;var numbering = $(' ').addClass('pre-numbering').hide(); (this).addClass(hasnumbering).parent().append( numbering); for (i = 1; i
    展开全文
  • 正在学习区块链,如果我哪里有错误希望大家指出,如果有任何想法也欢迎留言。这些笔记本身是在typora上写的,如果有显示不正确的敬请谅解...比特币用的哈希函数是SHA-256。  一共有三点,其中前两点都很简单,于算法而
  • 在大多数情况下,其速度比 , , 和其他可移植的哈希函数(不使用特定的硬件技巧)快15%。 目前, 在x86_64上的性能优于t1ha 。 但是,下一版本t1ha3_atonce()在所有平台上,甚至在具有和大多数RISC-V实现的E2K...
  • 最小完美哈希函数库。 主要用Java编写。 包括C版本(当前仅对MPHF进行评估)。 可以在线性时间内生成每个密钥需要少于1.58位的MPHF。 可以以小于100 ns / key的速度生成MPHF,以小于100 ns / key的速度评估,每...
  • 哈希函数的特征_哈希函数及其特征

    千次阅读 2020-07-06 22:57:28
    哈希函数的特征Prerequisite: Hashing data structure 先决条件: 哈希数据结构 The hash function is the component of hashing that maps the keys to some location in the hash table. As part of the hashing...

    哈希函数的特征

    Prerequisite: Hashing data structure

    先决条件: 哈希数据结构

    The hash function is the component of hashing that maps the keys to some location in the hash table. As part of the hashing technique, we need a hash function to map the available keys to the set of indexes in the hash table. Say we have a set of keys ranging from [-1000, 1000] and have a hash table of size 10, index ranging from [0, 10].

    哈希函数是哈希的组件,它将密钥映射到哈希表中的某个位置。 作为哈希技术的一部分,我们需要一个哈希函数将可用键映射到哈希表中的索引集。 假设我们有一组范围从[-1000,1000]的键,并且有一个大小为10的哈希表,索引范围是[0,10]。

    That's why to map the keys we need hash functions. A hash function is termed as the perfect hash function is what is able to map the keys to unique locations. But unfortunately, there is no systematic way to generate hash function as the size of the key list is very large considered to hash table size.

    这就是为什么要映射我们需要哈希函数的键的原因。 哈希函数被称为完美哈希函数,它是能够将密钥映射到唯一位置的函数。 但是遗憾的是,由于键列表的大小对于哈希表的大小而言非常大,因此没有系统的方法来生成哈希函数。

    A popular hash function is a folding method where we fold the integers and sum the partitions and then take mod 10 finally.

    流行的哈希函数是一种折叠方法 ,其中我们折叠整数并将分区求和,然后最终取mod 10。

    For example,

    例如,

    The hash function for the folding method is = 
        sum of the fold of size two %10
    Say we have integer 60784567
    So sum will be 60 + 78 + 45 + 67 = 250
    So final location is 250 % 10 = 0
    
    

    The below program computes the above folding method which is an example of the hash function.

    下面的程序将计算上述折叠方法 ,该方法哈希函数的一个示例。

    #include <bits/stdc++.h>
    using namespace std;
    
    //folding method
    
    int main()
    {
        string s;
      
        cout << "enter number\n";
        cin >> s;
    
        //folding and summing
        int sum = 0;
        for (int i = 0; i < s.length(); i += 2) {
            if (i + 1 < s.length())
                sum += stoi(s.substr(i, 2));
            else
                //when only one digit is left for folding
                sum += stoi(s.substr(i, 1));
        }
    
        cout << s << "->" << sum % 10;
    
        return 0;
    }
    
    

    Output:

    输出:

    enter number
    60784567
    60784567->0
    
    

    Now if some other number also finds location 0, then it's called collision.

    现在,如果其他一些数字也找到位置0,则称为碰撞

    Characteristics of good hash function

    哈希函数良好的特征

    1. Minimum collision

      最小碰撞

    2. High gain factor (distributes keys evenly). Like say we have 10 locations in the hash table, then almost 9 locations should have keys. It should not be the case that 4-5 locations have keys only where the keys collided.

      高增益因子(均匀分布密钥)。 像说在哈希表中有10个位置,那么几乎9个位置应该有键。 并非4-5个位置仅在按键碰撞的地方具有按键。

    3. Have a high load factor. Load factor means the number of keys stored/hash table size

      负载系数高。 负载因子是指存储的密钥数/哈希表大小

    4. Easy to compute

      易于计算

    Exercises on hash function

    哈希函数练习

    Use the below hash function to compute the hashing and comment on the goodness of the hash function.

    使用下面的哈希函数来计算哈希并评论哈希函数的优缺点。

    1) F(key) = number of digits of key

    1)F(key)=密钥位数

    #include <bits/stdc++.h>
    using namespace std;
    
    //hash function 1
    int main()
    {
        string s;
        cout << "enter number\n";
        cin >> s;
    
        //f(s)=no of digit in s=length of s
        cout << s << "->" << s.length();
    
        return 0;
    }
    
    

    Output:

    输出:

    enter number
    123452
    123452->6
    
    

    The above hash function is not good at all. Say we have set of keys all having the same digits, then all the keys will collide and the rest of the locations will remain empty.

    上面的哈希函数根本不好。 假设我们有一组键都具有相同的数字,那么所有键将发生冲突,其余位置将保持为空。

    2) F(key) = (rand()*key) % 10

    2)F(键)=(rand()*键)%10

    #include <bits/stdc++.h>
    using namespace std;
    
    //hash function 2
    int main()
    {
        int n;
        cout << "enter number\n";
        cin >> n;
    
        //f(n)=rand()*n
        cout << n << "->" << (rand() * n) % 10;
    
        return 0;
    }
    
    

    Output:

    输出:

    enter number
    103456
    103456->2
    
    

    The above hash function is good as we are multiplying random integers and bringing randomness, the collision rate will be less.

    上面的哈希函数很好,因为我们要乘以随机整数并带来随机性,则冲突率会更低。

    Comparison of the above hash functions:

    上面的哈希函数比较:

    #include <bits/stdc++.h>
    using namespace std;
    
    //comparing goodness of hash function 1 &  2
    int main()
    {
    
        //set of input numbers
        vector<int> arr{ 12345, 234245, 1223123, 765845, 345234, 234534, 98675, 34523, 123, 3245 };
    
        //using hash function 1
        cout << "using hash function 1\n";
        for (int a : arr) {
            cout << a << "->" << to_string(a).length() % 10 << endl;
        }
    
        //using hash function 2
        cout << "\n\nusing hashh function 2\n";
        for (int a : arr) {
            cout << a << "->" << (rand() * a) % 10 << endl;
        }
    
        return 0;
    }
    
    

    Output:

    输出:

    using hash function 1
    12345->5
    234245->6
    1223123->7
    765845->6
    345234->6
    234534->6
    98675->5
    34523->5
    123->3
    3245->4
    
    
    using hashh function 2
    12345->9
    234245->4
    1223123->3
    765845->-1
    345234->-4
    234534->4
    98675->6
    34523->0
    123->5
    3245->-9
    
    
    

    翻译自: https://www.includehelp.com/data-structure-tutorial/hash-functions-and-its-characteristics.aspx

    哈希函数的特征

    展开全文
  • 基于级联混沌的单向哈希函数
  • 量子哈希函数及其在量子密钥分发,伪随机数生成和图像加密中的隐私放大中的应用
  • Google的系列快速哈希函数的Node.js实现。 FarmHash是CityHash的后继者。 FarmHash系列中的功能不适用于加密。 一种快速,加密安全的替代方案是 。 由于V8 JavaScript引擎仅本机支持32位无符号整数,因此64位方法...
  • 1)设计几个不同的哈希函数,比较他们的地址冲突率(可以用更大的名字集合做实验)。 (2)研究这30个人名的特点,努力找一个哈希函数,使得对于不同的拼音名一定不发生地址冲突。 (3)在哈希函数确定的前提下尝试...
  • Bob Jenkins的lookup3.c哈希函数JavaScript端口 用法 var hash = require ( './' ) . hashlittle ; hash ( new Uint8Array ( [ 1 , 2 , 3 ] ) , 0xdeadbeef ) ; // 0x271b32ed hashlittle(buf,initval = 0) buf...
  • 如今越来越多的物联网设备带来了对哈希函数的需求,而传统的哈希函数又因为资源受限而不能直接应用,所以必须得针对该类设备重新设计,提出了一种新的轻量哈希函数HBL(Hash Function Based on LEA),它采用了主流...
  • 基于随机函数的哈希函数研究,王勇,蔡国永,本文提出将哈希函数随机化的观点,将传统的确定的哈希函数替换成随机的哈希函数,随机函数具有多种具体形式,在运算的时候通过消
  • 一、什么是哈希(Hash) 哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射,将任意长度的输入消息M...这是哈希函数安全性的基础。 灵敏性:对输入数据敏感,哪怕只改了一个Bit,得到的哈希值也大不相同

    目录

    一、什么是哈希(Hash)

    二、哈希的原理和特点

    三、哈希的实际用途

    四、典型的哈希函数

    (一)MD5

    (二)SHA

    五、Hash构造函数的方法


    一、什么是哈希(Hash)

    哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射,将任意长度的输入消息M(或文件F)映射成为一个较短的定长哈希值H(M),也叫散列值(HashValue)、杂凑值或消息摘要。可见,这是一种单向密码体制,只有加密过程,没有解密过程(因此Hash求逆很困难)。

    二、哈希的原理和特点

    1. 单向性:从哈希值不能反向推导原始数据(计算不可行),即从哈希输出无法倒推输入的原始数值。这是哈希函数安全性的基础。
    2. 灵敏性:对输入数据敏感,哪怕只改了一个Bit,得到的哈希值也大不相同。换言之,消息M的任何改变都会导致哈希值H(M)发生改变。
    3. 易压易算:Hash本质上是把一个大范围集合映射到另一个小范围集合。故输入值的个数必须与小范围相当或者更小,不然冲突就会很多。所以,哈希算法执行效率要高,散列结果要尽量均衡。
    4. 抗碰撞性:理想Hash函数是无碰撞的,但实际上很难做到这一点。有两种抗碰撞性:一种是弱抗碰撞性,即对于给定的消息,要发现另一个消息,满足在计算上是不可行的;另一种是强抗碰撞性,即对于任意一对不同的消息,使得在计算上也是不可行的。

    也可以这么理解正向快速、逆向困难、输入敏感、冲突避免

    三、哈希的实际用途

    Hash能把一个大范围映射到一个小范围,能对输入数据或文件进行校验,还可用于查找等。具体的:

    1. 唯一标识或数据检验:能够对输入数据或文件进行校验,判断是否相同或是否被修改。如图片识别,可针对图像二进制流进行摘要后MD5,得到的哈希值作为图片唯一标识;如文件识别,服务器在接受文件上传时,对比两次传送文件的哈希值,若相同则无须再次上传(传统的奇偶校验和CRC校验一定程度上能检测并纠正数据传输中的信道误码,但没有抗数据篡改的能力)。
    2. 安全加密:对于敏感数据比如密码字段进行MD5或SHA加密传输。哈希算法还可以检验信息的拥有者是否真实。如,用保存密码的哈希值代替保存密码,基本可以杜绝泄密风险。
    3. 数字签名。由于非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。对Hash值,又称“数字摘要”进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的。
    4. 散列函数:是构造散列表的关键。它直接决定了散列冲突的概率和散列表的性质。不过相对哈希算法的其他方面应用,散列函数对散列冲突要求较低,出现冲突时可以通过开放寻址法或链表法解决冲突。对散列值是否能够反向解密要求也不高。反而更加关注的是散列的均匀性,即是否散列值均匀落入槽中以及散列函数执行的快慢也会影响散列表性能。所以散列函数一般比较简单,追求均匀和高效。
    5. *负载均衡:常用的负载均衡算法有很多,比如轮询、随机、加权轮询。如何实现一个会话粘滞的负载均衡算法呢?可以通过哈希算法,对客户端IP地址或会话SessionID计算哈希值,将取得的哈希值与服务器列表大小进行取模运算,最终得到应该被路由到的服务器编号。这样就可以把同一IP的客户端请求发到同一个后端服务器上。
    6. *数据分片:比如统计1T的日志文件中“搜索关键词”出现次数该如何解决?我们可以先对日志进行分片,然后采用多机处理,来提高处理速度。从搜索的日志中依次读取搜索关键词,并通过哈希函数计算哈希值,然后再跟n(机器数)取模,最终得到的值就是应该被分到的机器编号。这样相同哈希值的关键词就被分到同一台机器进行处理。每台机器分别计算关键词出现的次数,再进行合并就是最终结果。这也是MapReduce的基本思想。再比如图片识别应用中给每个图片的摘要信息取唯一标识然后构建散列表,如果图库中有大量图片,单机的hash表会过大,超过单机内存容量。这时也可以使用分片思想,准备n台机器,每台机器负责散列表的一部分数据。每次从图库取一个图片,计算唯一标识,然后与机器个数n求余取模,得到的值就是被分配到的机器编号,然后将这个唯一标识和图片路径发往对应机器构建散列表。当进行图片查找时,使用相同的哈希函数对图片摘要信息取唯一标识并对n求余取模操作后,得到的值k,就是当前图片所存储的机器编号,在该机器的散列表中查找该图片即可。实际上海量数据的处理问题,都可以借助这种数据分片思想,突破单机内存、CPU等资源限制。
    7. *分布式存储:一致性哈希算法解决缓存等分布式系统的扩容、缩容导致大量数据搬移难题。

    四、典型的哈希函数

    常见Hash算法有MD5和SHA系列,目前MD5和SHA1已经被破解,一般推荐至少使用SHA2-256算法。

    (一)MD5

    MD5属于Hash算法中的一种,它输入任意长度的信息,在处理过程中以512位输入数据块为单位,输出为128位的信息(数字指纹)。常用场景:

    1、防篡改,保障文件传输可靠性:如SVN中对文件的控制;文件下载过程中,网站提供MD5值供下载后判断文件是否被篡改;BT中对文件块进行校验的功能。

    2、增强密码保存的安全性:例如网站将用户密码的MD5值保存,而不是存储明文用户密码,当然,还会加SALT,进一步增强安全性。

    3、数字签名:在部分网上赌场中,使用MD5算法来保证过程的公平性,并使用随机串进行防碰撞,增加解码难度。

    算法实现过程:

    第一步:消息填充,补长到512的倍数。最后64位为消息长度(填充前的长度)的低64位,一定要补长(64+1~512),内容为100…0(如若消息长448,则填充512+64)。

    第二步:分割,把结果分割为512位的块:Y0,Y1,…(每一个有16个32比特长字)。

    第三步:计算,初始化MD buffer,128位常量(4个32bit字),进入循环迭代,共L次。每次一个输入128位,另一个输入512位,结果输出128位,用于下一轮输入。

    第四步:输出,最后一步的输出即为散列结果128位。

    (二)SHA-1  Secure Hash Algorithm

    安全哈希算法(Secure Hash Algorithm)主要适用于数字签名标准(Digital Signature Standard DSS)里面定义的数字签名算法(Digital Signature Algorithm DSA)。对于长度小于2^64b的消息,SHA-1将输入流按照每块512b(64B)进行分块,并产生20B或160b的信息摘要。

    https://images2015.cnblogs.com/blog/929265/201607/929265-20160701092331874-1851324775.png

    1.补位

    消息补位使其长度在对512取模以后的余数是448。也就是说,(补位后的消息长度)% 512 = 448。即使长度已经满足对512取模后余数是448,补位也必须要进行。

    补位是这样进行的:先补一个1,然后再补0,直到长度满足对512取模后余数是448。总而言之,补位是至少补一位,最多补512位。还是以前面的“abc”为例显示补位的过程。

    原始信息:  011000010110001001100011

    补位第一步:0110000101100010011000111,首先补一个“1”

    补位第二步:01100001011000100110001110…..0,然后补423个“0”

    我们可以把最后补位完成后的数据用16进制写成下面的样子,确保是448b:

    61626380000000000000000000000000

    00000000000000000000000000000000

    00000000000000000000000000000000

    0000000000000000

    2.补长度

    补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64,那么第一个字就是0。

    在进行了补长度的操作以后,整个消息就变成下面这样了(16进制格式):

    61626380000000000000000000000000

    00000000000000000000000000000000

    00000000000000000000000000000000

    00000000000000000000000000000018

    如果原始的消息长度超过了512,我们需要将它补成512的倍数。然后我们把整个消息分成一个一个512位的数据块。分别处理每一个数据块,从而得到消息摘要。

    3.使用的常量

    一系列的常量字K(0),K(1),...,K(79),如果以16进制给出。它们如下:

    Kt=0x5A827999(0<=t<=19)

    Kt=0x6ED9EBA1(20<=t<=39)

    Kt=0x8F1BBCDC(40<=t<=59)

    Kt=0xCA62C1D6(60<=t<=79).

    4.需要使用的函数

    在SHA1中我们需要一系列的函数。每个函数ft(0<=t<=79)都操作32位字B,C,D并且产生32位字作为输出。

    ft(B,C,D)可以如下定义:

    ft(B,C,D)=(BANDC)or((NOTB)ANDD)(0<=t<=19)

    ft(B,C,D)=BXORCXORD(20<=t<=39)

    ft(B,C,D)=(BANDC)or(BANDD)or(CANDD)(40<=t<=59)

    ft(B,C,D)=BXORCXORD(60<=t<=79).

    5.计算消息摘要

    必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区,每个都由5个32位的字组成,还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A,B,C,D,E。第一个5个字的缓冲区被标识为H0,H1,H2,H3,H4。80个字的缓冲区被标识为W0,W1,...,W79。

    另外还需要一个一个字的TEMP缓冲区。

    为了产生消息摘要,在第4部分中定义的16个字的数据块M1,M2,...,Mn会依次进行处理,处理每个数据块Mi包含80个步骤。


    在处理每个数据块之前,缓冲区{Hi}被初始化为下面的值(16进制)

    H0=0x67452301

    H1=0xEFCDAB89

    H2=0x98BADCFE

    H3=0x10325476

    H4=0xC3D2E1F0.


    现在开始处理M1,M2,...,Mn。为了处理Mi,需要进行下面的步骤

    (1)将Mi分成16个字W0,W1,...,W15,W0是最左边的字

    (2)对于t=16到79令Wt=S1(Wt-3XORWt-8XORWt-14XORWt-16).

    (3)令A=H0,B=H1,C=H2,D=H3,E=H4.

    (4)对于t=0到79,执行下面的循环

    TEMP=S5(A)+ft(B,C,D)+E+Wt+Kt;

    E=D;D=C;C=S30(B);B=A;A=TEMP;

    (5)令H0=H0+A,H1=H1+B,H2=H2+C,H3=H3+D,H4=H4+E.

    在处理完所有的Mn,后,消息摘要是一个160位的字符串,以下面的顺序标识H0H1H2H3H4。

    (三)SHA-2系列

    SHA-2是六个不同算法的合称,包括:SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。除了生成摘要的长度、循环运行的次数等一些微小差异外,这些算法的基本结构是一致的。对于任意长度的消息,SHA256都会产生一个256bit长的消息摘要。

    详细参见:sha256算法原理 - Practical - 博客园

    至今尚未出现对SHA-2有效的攻击,SHA-2和SHA-1并没有接受公众密码社区的详细检验,所以它们的密码安全性还不被广泛信任。

    总体上,HAS-256与MD4、MD5以及HSA-1等哈希函数的操作流程类似,在哈希计算之前首先要进行以下两个步骤:

    • 对消息进行补位处理,最终的长度是512位的倍数;
    • 以512位为单位对消息进行分块为M1,M2,…,Mn
    • 处理消息块:从一个初始哈希H0开始,迭代计算:Hi = Hi-1 + CMi(Hi-1)

    其中C是SHA256的压缩函数,+是mod 2^32加法,Hn是消息区块的哈希值。

    五、Hash构造函数的方法

    1.直接定址法(极少用)

    以数据元素关键字k本身或它的线性函数作为它的哈希地址,即:H(k)=k或H(k)=a×k+b;(其中a,b为常数)。

    此法仅适合于:地址集合的大小==关键字集合的大小,其中a和b为常数。

    2.数字分析法

    假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us),分析关键字集中的全体,并从中提取分布均匀的若干位或它们的组合作为地址。数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时,可以通过对关键字的各位进行分析,丢掉分布不均匀的位,作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

    此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。

    3.折叠法

    将关键字分割成若干部分,然后取它们的叠加和为哈希地址。两种叠加处理的方法:移位叠加:将分割后的几部分低位对齐相加;边界叠加:从一端沿分割界来回折叠,然后对齐相加。

    所谓折叠法是将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位),这方法称为折叠法。这种方法适用于关键字位数较多,而且关键字中每一位上数字分布大致均匀的情况。

    折叠法中数位折叠又分为移位叠加和边界叠加两种方法,移位叠加是将分割后是每一部分的最低位对齐,然后相加;边界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    此法适于:关键字的数字位数特别多。

    4.平方取中法

    这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方,然后根据可使用空间的大小,选取平方数是中间几位为哈希地址。哈希函数H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别,平方值的中间几位和这个数的每一位都相关,则对不同的关键字得到的哈希函数值不易产生冲突,由此产生的哈希地址也较为均匀。

    此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象。

    5.减去法



    减去法是数据的键值减去一个特定的数值以求得数据存储的位置。

    6.基数转换法

    将十进制数X看作其他进制,比如十三进制,再按照十三进制数转换成十进制数,提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数,并且两个基数应该是互素的。

    7.除留余数法

    假设哈希表长为m,p为小于等于m的最大素数,则哈希函数为h(k)=k%p,其中%为模p取余运算。除留余数法的模p取不大于表长且最接近表长m素数时效果最好,且p最好取1.1n~1.7n之间的一个素数(n为存在的数据元素个数)。

    8.随机数法

    设定哈希函数为:H(key)=Random(key)其中,Random为伪随机函数

    此法适于:对长度不等的关键字构造哈希函数。

    9.随机乘数法

    亦称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f<1,乘积f*k的分数部分在0~1之间,用这个分数部分的值与n(哈希表的长度)相乘,乘积的整数部分就是对应的哈希值,显然这个哈希值落在0~n-1之间。其表达公式为:Hash(k)=「n*(f*k%1)」其中“f*k%1”表示f*k的小数部分,即f*k%1=f*k-「f*k」

    此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p.Knuth对常数f的取法做了仔细的研究,他认为f取任何值都可以,但某些值效果更好。如f=(-1)/2=0.6180329...比较理想。

    10.字符串数值哈希法

    把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址,只要N较小,Hash地址将较均匀分布[0,N]区间内。对于N很大的情形,可使用ELFHash(ExecutableandLinkingFormat,ELF,可执行链接格式)函数,它把一个字符串的绝对长度作为输入,并通过一种方式把字符的十进制值结合起来,对长字符串和短字符串都有效,这种方式产生的位置可能不均匀分布。

    11.旋转法

    旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上,而是搭配其他哈希函数使用。

    展开全文
  • 用C语言实现MD5哈希函数,它是将文件的每一行进行MD5加密,输出一个128位的哈希值。
  • 认识哈希函数

    2019-06-20 12:35:54
    首先,先来介绍一下哈希函数的概念。哈希函数的输入域可以是非常大的范围,比如,一个字符串,但是它的输出域是固定的范围。并具有以下性质: 典型的哈希函数都有无限的输入值域。 当给哈希函数传入相同的输入值...

    首先,先来介绍一下哈希函数的概念。哈希函数的输入域可以是非常大的范围,比如,一个字符串,但是它的输出域是固定的范围。并具有以下性质:

    1. 典型的哈希函数都有无限的输入值域。
    2. 当给哈希函数传入相同的输入值时,返回值一样。
    3. 当给哈希函数传入不同的输入值时,返回值可能一样,也可能不一样,这是当然的,因为输出域是固定的范围,所以会有不同的输入值对应在输出域的一个元素上,这就涉及到了哈希碰撞的问题。
    4. 最重要的性质是很多不同的输入值所得到的返回值会均匀的分布在输出域上。

    第1~3点性质是哈希函数的基础,第4点性质是评价一个哈希函数优劣的关键,不同输入值所得到的所有返回值越均匀分布与输入值出现的规律无关。

    哈希函数的构造方法

    1)直接定址法:

    取关键字或关键字的某个线性函数值为哈希地址:H(key) = key 或 H(key) = a·key + b
    其中a和b为常数,这种哈希函数叫做自身函数。

    注意:由于直接定址所得地址集合和关键字集合的大小相同。因此,对于不同的关键字不会发生冲突。但实际中能使用这种哈希函数的情况很少。

    2)相乘取整法:

    首先用关键字key乘上某个常数A(0 < A < 1),并抽取出key.A的小数部分;然后用m乘以该小数后取整。

    注意:该方法最大的优点是m的选取比除余法要求更低。比如,完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用,但对某些值效果会更好。Knuth建议选取 0.61803……。

    3)平方取中法:

    取关键字平方后的中间几位为哈希地址。

    通过平方扩大差别,另外中间几位与乘数的每一位相关,由此产生的散列地址较为均匀。这是一种较常用的构造哈希函数的方法。

    将一组关键字(0100,0110,1010,1001,0111) 
    平方后得(0010000,0012100,1020100,1002001,0012321) 
    若取表长为1000,则可取中间的三位数作为散列地址集:(100,121,201,020,123)。
    

    4)除留余数法:

    取关键字被数p除后所得余数为哈希地址:H(key) = key MOD p (p ≤ m)。

    注意:这是一种最简单,也最常用的构造哈希函数的方法。它不仅可以对关键字直接取模(MOD),也可在折迭、平方取中等运算之后取模。值得注意的是,在使用除留余数法时,对p的选择很重要。一般情况下可以选p为质数或不包含小于20的质因素的合数。

    5)随机数法:

    选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 H(key) = random (key),其中random为随机函数。通常,当关键字长度不等时采用此法构造哈希函数较恰当。

    哈希冲突解决方法

    1)开放定址法:

    就是在发生冲突后,通过某种探测技术,去依次探查其他单元,直到探查到不冲突为止,将元素添加进去。

    假如是在index的位置发生哈希冲突,那么通常有一下几种探测方式:

    • 线性探测法(线性探测再散列)
      向后依次探测index+1,index+2…位置,看是否冲突,直到不冲突为止,将元素添加进去。

    • 平方探测法
      不探测index的后一个位置,而是探测2^i 位置 ,比如探测2^0 位置上时发生冲突,接着探测2^1位置,依此类推,直至冲突解决。

    注意:

    (1)用开放定址法建立散列表时,建表前须将表中所有单元(更严格地说,是指单元中存储的关键字)
    置空。
    (2)两种探测方法的优缺点。
         线性探测法虽然在哈希表未满的情况下,总能保证找到不冲突的地址,但是容易发生二次哈希冲
         突的现象。比如在处理若干次次哈希冲突后k,k+1,k+2位置上的都存储了数据,那下一次存储地
         址在k,k+1,k+2,k+3位置的数据都将存在k+3位置上,这就产生了二次冲突。
         这里引入一个新的概念,堆积现象是指用线性探测法处理哈希冲突时,k,k+1,k+2位置已存有数
         据,下一个数据请求地址如果是k,k+1,k+2,k+3的话,那么这四个数据都会要求填入k+3的位置。
         
         平方探测法可以减少堆积现象的发生,但是前提是哈希表的总容量要是素数4n+3才可以。
    

    2)链地址法(开散列法)

    基本思想:

    链表法就是在发生冲突的地址处,挂一个单向链表,然后所有在该位置冲突的数据,都插入这个链表中。插入数据的方式有多种,可以从链表的尾部向头部依次插入数据,也可以从头部向尾部依次插入数据,也可以依据某种规则在链表的中间插入数据,总之保证链表中的数据的有序性。Java的HashMap类就是采取链表法的处理方案。

    例:已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79),则按哈希函数 H(key) = key MOD13 和链地址法处理冲突构造所得的哈希表为:
    在这里插入图片描述

    3)再哈希法:(双散列法)

    在发生哈希冲突后,使用另外一个哈希算法产生一个新的地址,直到不发生冲突为止。这个应该很好理解。

    再哈希法可以有效的避免堆积现象,但是缺点是不能增加了计算时间和哈希算法的数量,而且不能保证在哈希表未满的情况下,总能找到不冲突的地址。

    4)建立一个公共溢出区:

    建立一个基本表,基本表的大小等于哈希表的大小。建立一个溢出表,所有哈希地址的第一个记录都存在基本表中,所有发生冲突的数据,不管哈希算法得到的地址是什么,都放入溢出表中。

    但是有一个缺点就是,必须事先知道哈希表的可能大小,而且溢出表里的数据不能太多,否则影响溢出表的查询效率。实际上就是要尽量减少冲突。

    参考链接:https://blog.csdn.net/m0_37925202/article/details/82015731

    展开全文
  • 常用哈希函数介绍

    千次阅读 2021-03-31 16:21:32
    哈希函数介绍 什么是哈希?在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数哈希函数就是一种映射,是从关键字到存储地址的映射。 通常,包含哈希函数的算法的算法复杂度都假设为O(1),这就是为...
  • 终端中哈希函数的动画。 视频: : 用法 只需对要散列的数据运行sha256.rb脚本。 # simple ruby sha256.rb abc # hash binary or hex data by using `0b` or `0x` prefixes ruby sha256.rb 0b01100001 ruby sha256....
  • 哈希函数与数据完整性
  • 基于量子游走的哈希函数
  • 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。具体的介绍网上有很详细的描述,如闲聊哈希...
  • 提出了一种适用于低成本无源RFID标签的低复杂性哈希函数M-hash。M-hash以并行线性反馈移位寄存器作为基本电路,采用并行压缩方式计算哈希值,利用压缩过程的信息损失而带来的单向性提供哈希函数的安全性。经过严格的...
  • 哈希:纯Rust编写的加密哈希函数的集合
  • 密码学哈希函数 什么是哈希函数? (What is a Hash Function?) A Hash Function is a mathematical function that converts a numerical value into another compressed numeric value. So, it compresses the text....
  • 基于可变参数广义混沌映射的快速高效哈希函数
  • 用C语言实现常用的字符串哈希函数,比如RSHash、JSHash、PJWHash、FNVHash等
  • 哈希原理与常见哈希函数

    千次阅读 2020-01-09 18:11:06
    转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。 1.哈希特点 (1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。 F(x)=rand() :每次返回一个随机值,是不好的哈希 (2)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 236,203
精华内容 94,481
关键字:

哈希函数