哈希算法详解（附带 iOS 开发中实际应用）

前言

哈希(Hash)或者说散列表，它是一种基础数据结构。Hash 表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，但它又是是数组和链表的基础上演化而来，既具有数组的有点，又具有链表的有点。能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。应用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。

一、Hash设计思想

试想如果我们对一个数组进行查询，这个数组里，每一个元素都是一个字符串。我们知道数组最快的检索办法是通过数组的下标进行检索，但是对于这种场景，我们无能为力，只能从头查到尾，从而查询出目标元素。

1 2 3 4 5 6
zhangsan lisi wanger wangwu zhangsi gaofei

如果我们要根据名字找到其中的任何一个元素，就需要遍历整个数组。最坏情况下时间复杂度是O(n) ,但是借助 Hash 可以将时间复杂度降为O(1)。

Hash表采用一个映射函数 f :key —> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置，通常情况下，这种映射关系称作为Hash函数，而通过Hash函数和关键字计算出来的存储位置（注意这里的存储位置只是表中的存储位置，并不是实际的物理地址）称作为Hash地址。比如上述例子中，假如联系人信息采用Hash表存储，则当想要找到 “lisi” 的信息时，直接根据 “lisi” 和 Hash 函数计算出 Hash 地址即可。

哈希算法历史悠久，业界著名的哈希算法也有很多，比如 MD5、SHA。哈希算法是指将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。有以下几个特点：

  • 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法或单向散列函数)。
  • 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同。
  • 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。
  • 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

为了更好说明这种设计思想，笔者先设计出一种最笨的 Hash 函数，将所有字符串中的字符转化为数字后相加。

858 433 644 665 756 619
zhangsan lisi wanger wangwu zhangsi gaofei

上表中数组的下标就是字符串对应的数字值。根据对应的数字值，我们就能轻易找到任何想要的对象，时间复杂度为O(1)。

二、Hash函数设计

所谓的 hash 算法就是将字符串转换为数字的算法。通常有以下几种构造 Hash 函数的方法：

2.1 直接定址法

取关键字或者关键字的某个线性函数为 Hash 地址，即address(key) = a * key + b; 如知道学生的学号从2000开始，最大为4000，则可以将address(key)=key-2000(其中a = 1)作为Hash地址。

2.2 平方取中法

对关键字进行平方计算，取结果的中间几位作为 Hash 地址。如有以下关键字序列 {421，423，436} ，平方之后的结果为 {177241，178929，190096} ，那么可以取中间的两位数 {72，89，00} 作为 Hash 地址。

2.3 折叠法

将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。如图书的 ISBN 号为 8903-241-23，可以将 address(key)=89+03+24+12+3 作为 Hash 地址。

2.4 除留取余法

如果知道 Hash 表的最大长度为 m，可以取不大于m的最大质数 p，然后对关键字进行取余运算，address(key)=key % p。这里 p 的选取非常关键，p 选择的好的话，能够最大程度地减少冲突，p 一般取不大于m的最大质数。

三、Hash表大小的确定

Hash 表的空间如果远远大于实际存储的记录数据的个数，则造成空间浪费；如果过小，则容易造成冲突。Hash 表大小确定通常有这两种思路：

  • 如果最初知道存储的数据量，则需要根据存储个数 和 关键字的分布特点来确定 Hash 表的大小。
  • 事先不知道最终需要存储的记录个数，需要动态维护Hash表的容量，此时可能需要重新计算 Hash 地址。

四、Hash 冲突及解决方案

4.1 Hash冲突产生

有这样一个问题：因为我们是用数组大小对哈希值进行取模，有可能不同键值所得到的索引值相同，这里就是冲突。如在最初的实例中，如果多出了sizhang这样一个元素，那么就存在两个 756。

858 433 644 665 756 619 756
zhangsan lisi wanger wangwu zhangsi gaofei sizhang

显然出现的这种情况是不合理的，解决该冲突的方法就是改变数据结构。我们将数组内的元素改变为一个链表，这样就能容下足够多的元素了，冲突问题也能得到解决。具体如何解决请看下面的链地址法。

4.2 Hash 冲突解决

4.2.1 开放定址法

发生冲突时，使用某种探测技术在 Hash 表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入其中。比较常用的探测方法有线性探测法，如有一组关键字{12，13，25，23，38，34，6，84，91}，Hash 表长为14，Hash 函数为 address(key) = key % 11，当插入12，13，25时可以直接插入，而当插入 23 时，地址 1 被占用了（因为 12%11 和 23%11 的结果相同）。此时沿着地址 1 依次往下探测(探测步长可以根据情况而定)，直到探测到地址4，发现为空，则将 23 插入其中。

4.2.2 链地址法

采用数组和链表相结合的数据结构，将 Hash 地址相同的记录存储在一张线性表中，而每张表的表头的序号即为计算得到的Hash地址。如下图最左边是数组结构，数组内的元素为链表结构。

image

所以针对之前案列冲突的解决方案如下：

image

检索的时候可以这样检索，首先找到gaofei后，之后再遍历链表，找到feigao了。同理对于 sizhang 的冲突也是如此解决。

五、Hash 表的用处以及优劣

5.1 Hash 表的实际应用

上述说了这么多关于 Hash 表的知识点，但是 Hash 表在代码的世界中，实际上又有什么应用场景，可能有些读者会一头雾水，这里笔者就以简单的三个例子来说明 Hash 表的实际应用场景。

  • 1 、找出两文件找出重复的元素
    假设有两个文件，文件中均包含一些短字符串，字符串个数分别为n。它们是有重复的字符串，现在需要找出所有重复的字符串。
    最笨的解决办法可能是：遍历文件 1 中的每个元素，取出每一个元素分别去文件 2 中进行查找，这样的时间复杂度为O（n^2）。
    但是借助 Hash 表可以有一种相对巧妙的方法，分别遍历文件 1 中的元素和文件 2 中的元素，然后放入 Hash Table 中，对于遍历的每一个元素我们只要简单的做一下计数处理即可。最后遍历整个 Hash 列表，找出所有个数大于 1 的元素即为重复的元素。
  • 2、找出两文件找出出现次数最多的元素
    同找出两文件找出重复的元素这样的问题解决方案类似，只是在最后遍历的时找计数最大的元素，即为出现次数最多的元素。
  • 3、路由算法
    多线程处理数据的场景下，通常需要将一个数据集分给不同的线程进行处理，同时要保证，相同的元素需要分到相同的处理线程上。这
    其实这个就是一个很典型的 Hash 值应用场景，对于很多的计算引擎默认都是用 Hash 算法去解决这个问题。因为相同元素的 Hash 值相同，那么我们可以取 Hash 之后进行模运算，运算结果分配到不同的线程。
image

5.2 Hash 表的优缺点及注意点

  • 优点
    哈希表的效率非常高，查找、插入、删除操作只需要接近常量的时间即0(1）的时间级。如果需要在一秒种内查找上千条记录通常使用哈希表，哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。如果不需要遍历数据，不二的选择。
  • 缺点
    它是基于数组的，数组创建后难于扩展。有些情况下，哈希表被基本填满时，性能下降得非常严重，所以开发者必须要清楚表中将要存储的数据量。或者也可以定期地把数据转移到更大的哈希表中，不过这个过程耗时相对比较大。
  • 注意点
    在设计Hash算法的时候。一定要保证相同字符串产生的 Hash 值相同，同时要尽量的减小Hash冲突的发生，这样才算是好的 hash 算法。

六、Hash 在 iOS 中的应用

这一部分的篇幅可能稍稍有点大，笔者原本打算给这一部分抽出来单独写一篇文章，但是发现没有 Hash 概念做铺垫，文章略显空洞，所以这里干脆把所有东西整合到一起，请读者耐下心来看。

这一部分的内容就以下面的一个问题为中心。并在此问题上不断的扩充，以点带面。

iOS系统API给我们提供一个自动过滤重复元素的容器 NSMutableSet/NSSet，如：当我们向该实例对象中添加字符串时，如果重复添加两个相同的字符串，集合中只会保留一个。NSMutableSet/NSSet内部一些实现机制要比我们自己写的滤重方法效率高。但是对于自定义一个类如Person，如果想利用NSMutableSet/NSSet来过滤重复元素（如多个Person实例的uid相同），我们必须要同时实现- (BOOL)isEqual:和- (NSUInteger)hash这两个方法。这里先简单介绍他们的关系：两个相等的实例，他们的hash值一定相等。但是hash值相等的两个实例，不一定相等。重点来了，利用 NSMutableSet/NSSet 具体如何实现过滤 Person 重复元素 ？

在解决这个问题之前我先用简单的篇幅 6.1 小结 和 6.2 小结 分别介绍- (BOOL)isEqual:和- (NSUInteger)hash这两个方法。具体可以参考这篇文章。

6.1 关于- (BOOL)isEqual:方法

  • 为什么要有isEqual方法？
    OC 中 == 运算符只是简单地判断是否是同一个对象, 而 isEqual 方法可以判断对象是否相同。

  • 如何重写isEqual方法？
    但对于自定义类型来说, 做判等时通常需要重写isEqual方法。

@interface Person : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic, strong) NSDate *birthday;
@end


- (BOOL)isEqual:(id)object {
    if (self == object) {
        return YES;
    }

    if (![object isKindOfClass:[Person class]]) {
        return NO;
    }

    return [self isEqualToPerson:(Person *)object];
}

- (BOOL)isEqualToPerson:(Person *)person {
    if (!person) {
        return NO;
    }

    BOOL haveEqualNames = (!self.name && !person.name) || [self.name isEqualToString:person.name];
    BOOL haveEqualBirthdays = (!self.birthday && !person.birthday) || [self.birthday isEqualToDate:person.birthday];

    return haveEqualNames && haveEqualBirthdays;
}

上述代码主要步骤如下:
1、 ==运算符判断是否是同一对象, 因为同一对象必然完全相同
2、 判断是否是同一类型, 这样不仅可以提高判等的效率, 还可以避免隐式类型转换带来的潜在风险
3、通过封装的isEqualToPerson方法, 提高代码复用性
4、 判断person是否是nil, 做参数有效性检查
5、 对各个属性分别使用默认判等方法进行判断
6、 返回所有属性判等的与结果

6.2 关于- (NSUInteger)hash方法

  • hash方法什么时候被调用?
    如果在 Person 类中重写- (NSUInteger)hash方法，该方法只在 Person 实例对象被添加至NSSet或将Person实例对象设置为NSDictionary的 key 时会调用。注意是设置为 key 而不是 value

  • hash方法和判等的关系？
    为了优化判等的效率, 基于 hash 的 NSSet 和 NSDictionary 在判断成员是否相等时, 通常会这样做:
    首先判断 hash 值是否和目标 hash 值相等。如果相同再进行对象之后的判等逻辑, 作为判等的结果； 如果不等, 直接判断为不相等。
    简单地说:hash值是对象判等的必要非充分条件。

  • 如何重写 hash 方法？
    很多人在iOS开发中, 都是这么重写hash方法的，如果自己亲自测试一下会发现直接重写父类方法并不能实现过滤重复元素的功能。

- (NSUInteger)hash {
    return [super hash];
}

对于上面的 Person 类正确的 Hash 实现方法应该是借助位运算。代码如下：

- (NSUInteger)hash {
    return [self.name hash] ^ [self.birthday hash];
}

6.3 同时实现- (BOOL)isEqual: 和 - (NSUInteger)hash方法，实现过滤自定义实例的功能

6.3.1 代码实现
@interface Person : NSObject
@property (nonatomic, assign) NSInteger uid;
@property (nonatomic, strong) NSString *name;
@end

@implementation Person
- (instancetype)initWithID:(NSInteger)uid name:(NSString *)name{
    if (self = [super init]) {
        self.uid = uid;
        self.name = name;
    }
    return self;
}

- (BOOL)isEqual:(Person *)object{
    BOOL result;
    if (self == object) {
        result = YES;
    }else{
        if (object.uid == self.uid) {
            result = YES;
        }else{
            result = NO;
        }
    }
    NSLog(@"%@ compare with %@ result = %@",self,object,result ? @"Equal":@"NO Equal");
    return result;
}

- (NSString *)description{
    return [NSString stringWithFormat:@"%p(%ld,%@)",self,self.uid,self.name];
}

- (NSUInteger)hash{
    NSUInteger hashValue = self.uid; //在这里只需要比较uid就行。这
    样的话就满足如果两个实例相等，那么他们的 hash 一定相等，但反过
    来hash值相等，那么两个实例不一定相等。但是在 Person 这个实例
    中，hash值相等那么实例一定相等。（不考虑继承之类的）
    NSLog(@"hash = %lu,addressValue = %lu,address = %p",(NSUInteger)hashValue,(NSUInteger)self,self);
    return hashValue;
}
@end


//调用重写hash后的方法
- (void)viewDidLoad {
    [super viewDidLoad];
    self.mutSet = [NSMutableSet set];
    Person *person1 = [[Person alloc] initWithID:1 name:@"nihao"];
    Person *person2 = [[Person alloc] initWithID:2 name:@"nihao2"];
    NSLog(@"begin add %@",person1);
    [self.mutSet addObject:person1];
    NSLog(@"after add %@",person1);

    NSLog(@"begin add %@",person2);
    [self.mutSet addObject:person2];
    NSLog(@"after add %@",person2);

    NSLog(@"count = %d",self.mutSet.count);

    Person *person3 = [[Person alloc] initWithID:1 name:@"nihao"];
    NSLog(@"begin add %@",person3);
    [self.mutSet addObject:person3];
    NSLog(@"after add %@",person3);

    NSLog(@"count = %d",self.mutSet.count);
}
6.3.2 关于一些结论

  • NSMutableSet/NSSet中添加 Person 对象的时候，就会调用- (NSUInteger)hash方法。

  • NSMutableSet/NSSet中添加 personA 对象的时候，如果NSMutableSet/NSSet 中之前就已经存在 personB对象，且 personB 对象的 - (NSUInteger)hash返回值和personA的- (NSUInteger)hash返回值相等, 则 personA 会继续调用- (BOOL)isEqual:方法 ，其中此方法以personB为参数；否则不等, 继续下一个元素判断。

  • 具体的判等过程如下。
    1、如果 personB 的- (NSUInteger)hash返回值是否和 personA 的- (NSUInteger)hash返回值相等,则直接执行第 3 步；如果不相等，则执行第 2 步。
    2、判断 NSMutableSet/NSSet 中是否存在下一个没有比较过的元素，如果有继续执行第 1 步；如果没有，则personA 会被添加到NSMutableSet/NSSet 集合中，执行结束命令。
    3、调用 personA 的- (BOOL)isEqual:其中该方法 以personB为参数，如果返回结果为 NO(两者不相等)， 则执行第 2 步；如果返回结果为Yes(两者是相同元素)，则 NSMutableSet/NSSet 中存在和 personA 相同的元素，personA不会被添加到集合中，直接执行结束命令。

七、总结

本文章主要讲解了 Hash 的设计思想、Hash 函数设计、Hash 冲突的产生和解决、 Hash 的优缺点以及应用，最后结合实际代码，说明了 Hash 在 iOS 判等过程中的实际应用。关于 Hash 实际上还有很多值得我们研究的问题，就单单是 Hash 函数设计而言，就足够我们花上很多功夫去研究，当然感兴趣的同学可以去仔细研究下。

来源：
链接：https://www.jianshu.com/p/2a71b027b723

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,033评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,725评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,473评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,846评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,848评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,691评论 1赞 282
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,053评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,700评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,856评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,676评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,787评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,430评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,034评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,990评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,218评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,174评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,526评论 2赞 343