7.哈希

  哈希(Hash)又称散列,它是一个很常见的算法。在Java的HashMap数据结构中主要就利用了哈希。哈希算法包括了哈希函数和哈希表两部分。我们数组的特性可以知道,可以通过下标快速(O(1))的定位元素,同理在哈希表中我们可以通过键(哈希值)快速的定位某个值,这个哈希值的计算就是通过哈希函数(hash(key) = address )计算得出的。通过哈希值即能定位元素[address] = value,原理同数组类似。

最好的哈希函数当然是每个key值都能计算出唯一的哈希值,但往往可能存在不同的key值的哈希值,这就造成了冲突,评判一个哈希函数是否设计良好的两个方面:

  1.冲突少。

  2.计算快。

  下面给出几种常用的哈希函数,它们的背后都有一定的数学原理且经过大量实践,其数学原理不在这里探究。  

BKDR哈希函数(h = 31 * h + c)

  这个哈希函数被应用在Java的字符串哈希值计算。

//String#hashCode
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];    //BKDR 哈希函数,常数可以是131、1313、13131……
        }
        hash = h;
    }
    return h;
}

DJB2 哈希函数(h = h << 5 + h + c = h = 33 * h + c)

  ElasticSearch就利用了DJB2哈希函数对要索引文档的指定key进行哈希。

SDBM哈希函数(h = h << 6 + h << 16 - h + c = 65599 * h + c)

  在SDBM(一种简单的数据库引擎)中被应用。

  以上只是列举了三种哈希函数,我们做下试验,看看它们的冲突情况是怎么样的。

Java

 1 package com.algorithm.hash;
 2 
 3 import java.util.HashMap;
 4 import java.util.UUID;
 5 
 6 /**
 7  * 三种哈希函数冲突数比较
 8  * Created by yulinfeng on 6/27/17.
 9  */
10 public class HashFunc {
11 
12     public static void main(String[] args) {
13         int length = 1000000;   //100万字符串
14         //利用HashMap来计算冲突数,HashMap的键值不能重复所以length - map.size()即为冲突数
15         HashMap<String, String> bkdrMap = new HashMap<String, String>();
16         HashMap<String, String> djb2Map = new HashMap<String, String>();
17         HashMap<String, String> sdbmMap = new HashMap<String, String>();
18         getStr(length, bkdrMap, djb2Map, sdbmMap);
19         System.out.println("BKDR哈希函数100万字符串的冲突数:" + (length - bkdrMap.size()));
20         System.out.println("DJB2哈希函数100万字符串的冲突数:" + (length - djb2Map.size()));
21         System.out.println("SDBM哈希函数100万字符串的冲突数:" + (length - sdbmMap.size()));
22     }
23 
24     /**
25      * 生成字符串,并计算冲突数
26      * @param length
27      * @param bkdrMap
28      * @param djb2Map
29      * @param sdbmMap
30      */
31     private static void getStr(int length, HashMap<String, String> bkdrMap, HashMap<String, String> djb2Map, HashMap<String, String> sdbmMap) {
32         for (int i = 0; i < length; i++) {
33             System.out.println(i);
34             String str = UUID.randomUUID().toString();
35             bkdrMap.put(String.valueOf(str.hashCode()), str);   //Java的String.hashCode就是BKDR哈希函数, h = 31 * h + c
36             djb2Map.put(djb2(str), str);    //DJB2哈希函数
37             sdbmMap.put(sdbm(str), str);    //SDBM哈希函数
38         }
39     }
40 
41     /**
42      * djb2哈希函数
43      * @param str
44      * @return
45      */
46     private static String djb2(String str) {
47         int hash = 0;
48         for (int i = 0; i != str.length(); i++) {
49             hash = hash * 33 + str.charAt(i);    //h = h << 5 + h + c = h = 33 * h + c
50         }
51         return String.valueOf(hash);
52     }
53 
54     /**
55      * sdbm哈希函数
56      * @param str
57      * @return
58      */
59     private static String sdbm(String str) {
60         int hash = 0;
61         for (int i = 0; i != str.length(); i++) {
62             hash = 65599 * hash + str.charAt(i);    //h = h << 6 + h << 16 - h + c = 65599 * h + c
63         }
64         return String.valueOf(hash);
65     }
66 }

  以下是10万、100万、200万的冲突数情况:

  反复试验实际上三种哈希函数的冲突数差不多。

Python3

 1 import uuid
 2 
 3 def hash_test(length, bkdrDic, djb2Dic, sdbmDic):
 4     for i in range(length):
 5         string = str(uuid.uuid1())  #基于时间戳
 6         bkdrDic[bkdr(string)] = string
 7         djb2Dic[djb2(string)] = string
 8         sdbmDic[sdbm(string)] = string
 9 
10 #BDKR哈希函数
11 def bkdr(string):
12     hash = 0
13     for i in range(len(string)):
14         hash = 31 * hash + ord(string[i])   # h = 31 * h + c
15     return hash
16 
17 #DJB2哈希函数
18 def djb2(string):
19     hash = 0
20     for i in range(len(string)):
21         hash = 33 * hash + ord(string[i])   # h = h << 5 + h + c
22     return hash
23 
24 #SDBM哈希函数
25 def sdbm(string):
26     hash = 0
27     for i in range(len(string)):
28         hash = 65599 * hash + ord(string[i])    # h = h << 6 + h << 16 - h + c
29     return hash
30 
31 length = 100
32 bkdrDic = dict() #bkdrDic = {}
33 djb2Dic = dict()
34 sdbmDic = dict()
35 hash_test(length, bkdrDic, djb2Dic, sdbmDic)
36 print("BKDR哈希函数100万字符串的冲突数:%d"%(length - len(bkdrDic)))
37 print("DJB2哈希函数100万字符串的冲突数:%d"%(length - len(djb2Dic)))
38 print("SDBM哈希函数100万字符串的冲突数:%d"%(length - len(sdbmDic)))

  哈希表是一种数据结构,它需要配合哈希函数使用,用于建立索引,便于快速查找——《算法笔记》。一般来讲它就是一个定长的存储空间,比如HashMap默认的哈希表就是定长为16的Entry数组。有了定长的存储空间过后,剩下的问题就是如何将值放入哪个位置,通常如果哈希值是m,长度为n,那么这个值就放到m mod n位置处。

  上图就是哈希和哈希表,以及产生冲突的解决办法(拉链法)。产生冲突后的解决办法有很多,有再哈希一次直到没有冲突,也有向上图一样采用拉链法利用链表将相同位置的元素串联。

  想象一下,上面的例子哈希表的长度为10,产生了1次冲突,如果哈希表长度为20,那么就不会产生冲突查找更快但会浪费更多空间,如果哈希表长度为2,将会倒置3次冲突查找更慢但这样又会节省不少空间。所以哈希表的长度选择至关重要,但同时也是一个重要的难题。

补充:

  哈希在很多方面有应用,例如在不同的值有不同的哈希值,但也可以将哈希算法设计精妙使得相似或相同的值有相似或相同的哈希值。也就是说如果两个对象完全不同,那么它们的哈希值也完全不同;如果两个对象完全相同,那么它们的哈希值也完全相同;两个对象越相似,那么它们的哈希值也就越相似。这实际上就是相似性问题,也就是说这个思想可以被推广应用到相似性的计算(例如Jaccard距离问题),最终应用到广告精准投放、商品推荐等。

  另外,一致性哈希也可应用在负载均衡,如何保证每台服务器能均匀的分摊负载压力,一个好的哈希算法也可做到。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏工科狗和生物喵

【计算机本科补全计划】Java学习笔记(二) 基础语法红黄蓝

正文之前 刚才突然想起来自己CCF报名还没报名成功,就是一阵心绞痛,明晚就截止了,要是没报上,到时候怎么跟老师交差,突然想起来,如果老师问我最近干了啥,可以用准...

37960
来自专栏walterlv - 吕毅的博客

Roslyn 语法树中的各种语法节点及每个节点的含义

2018-07-18 12:24

25810
来自专栏企鹅号快讯

Java初学者的30个常见问题

1.2 基本数据类型 Q. 为什么 -0/3 结果是 0,而 -0.0/3.0 结果是 -0.0?(注意后边的结果0带负号) A. 在Java里,整数是用补码...

19150
来自专栏Crossin的编程教室

【编程课堂】计数器 Counter

上一期的编程课堂我们介绍了 有序字典 OrderedDict,这一期我们再来聊聊 同属 collections 模块的另一种数据类型 Counter。 在了解 ...

30260
来自专栏步履前行

什么是面向对象

面向对象的特征有3个,封装、继承、多态。至于抽象的话,个人认为,应该是前面3大特征中都有抽象的思想,毕竟面向对象本身就是一种抽象。 比如 子类 extends ...

35560
来自专栏C/C++基础

Google C++编程风格指南(四)之类的相关规范

类是C++中基本的代码单元,自然被广泛使用。本节列举了在写一个类时要做什么、不要做什么。

11520
来自专栏流媒体

STL(二)map/multimapmapmultimap

Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据 处理能力。由于这个特...

11830
来自专栏Python专栏

写了这么多年的python,tuple竟然是可变的?

13620
来自专栏企鹅号快讯

Python类与面向对象

面向对象程序 程序 = 指令 + 数据 代码可以选择以指令为核心或以数据为核心进行编程 两种范例 1.以指令为核心:围绕"正在发生什么"编写 面向过程编程:程序...

27180
来自专栏狮乐园

dart class overview

最近在折腾 flutter 相关的东西,所以当然要撸一下 dart 了。编程语言这个东西,接触得多了学习起来速度会提升不少,但是不同的语言具有不同的特色,我们需...

12220

扫码关注云+社区

领取腾讯云代金券