阅读 432

用Objective-C实现哈希表

哈希表的基本原理

首先回顾一下前面实现的数组和链表,无论是动态数组、链表、还是循环链表,而且如果是从其中查询特定值,都不可避免的要遍历依次遍历所有元素依次去做比较才可以。

做为面向对象开发语言的使用者,一定用过类似于Map的对象,通过 key: value 存储一个键值对。Objective-C中这种对象就是字典:NSDictionary、NSMutableDictionary,Swift中对于Dictionary。而且通过很多介绍的文章都说过,通过key取值的时间复杂度是O(1)。之前我们都只是使用它们,现在我们自己思考,如何利用我们之前已经了解的数据结构,自己实现一个自定义字典。

上面提到,通过数组和链表查询值的时候,时间复杂度都是O(n)级别,那么如何实现仅需要O(1)级别就能够查询到值呢?首先回顾之前的几个数据结构:数组、单向链表、双向链表,哪种数据结构能够做到在任意位置取值都是O(1)?

答案就是数组,数据可以做到通过下标从数组中的任意位置取值都是O(1)的时间复杂度。既然是这样,我们就先决定用静态数组来做为存放数据的底层结构。既然是这样,我们的键值对都是存放在数组中的。但是数组只有通过下标取值才是O(1)的时间复杂度,直接查找值依然需要依次对比元素是否相等。

那么接下来的问题就是,如何将key的遍历查找转换成直接通过index去数组中取值。要做到这一点,我们假设一个函数,这个函数能够做到:将不同的key转换成对应数组长度范围内的一个index,且不同的key转换成的index都不一样。而且这个函数是O(1)级别的数据复杂度,那么当需要将一个键值对存入数组时,只需要通过这个函数计算一下对应在数组中下标,然后将键值对存放在数组中对应位置。当需要通过key从数组中取时,只需要在通过这个函数计算key对应在数组中下标,然后通过下标去数组中直接取出键值对就可以了。存、取、查都是O(1)级别的时间复杂度。

现在就不需要解释什么是哈希表了,上面就是哈希表的原理,静态数组加上一个通过key计算index的函数,就是一个哈希表。下面通过图片看一下我们上面分析的哈希表的存放数据过程:

我们有两对键值对需要存放在我们的自定义字典中,key是名字,value是年龄,分别是 Whip:18、Jack:20。

当存储Whip:18时,首先通过哈希函数计算whip对应在哈希表中的index为2,然后创建一个哈希表的节点对象,key指向Whip,value指向18,然后将节点存储在哈希表中index为2的位置。

当存储Jack:20时,首先通过哈希函数计算Jack对应在哈希表中的index为6,然后创建一个哈希表的节点对象,key指向Jack,value指向20,然后将节点存储在哈希表中index为6的位置。

下面看一下哈希表的取值过程:

当需要需要得到Whip的年龄时,哈希表先通过哈希函数计算出Whip在哈希表中存放的位置index = 2,然后直接在数组中index为2的位置拿到存储的节点,返回节点的value值18。

哈希函数

既然需要通过哈希函数计算不同key对应在数组中的index,那么我们首先就需要实现一个哈希函数。首先哈希函数需要满足以下条件才是合格的:

  • 不同的key生成的索引尽可能不同。
  • 生成的索引要在哈希表长度范围内。

在Objective-C中,NSObject对象自带一个hash方法,可以返回一个对象的哈希值:

Person *p1 = [Person personWithAge:1];
Person *p2 = [Person personWithAge:1];
NSLog(@"%zd %zd", p1.hash, p2.hash);

// 打印
4345476000 4345477856
复制代码

可以看的即使是相同类型的并且属性值相同的对象,返回的哈希值也是不同的。当然也可重写自定义对象的hash方法,返回我们自己希望返回的哈希值,做到让属性值相同的对象,返回相同的hash值:

- (NSUInteger)hash {
    NSUInteger hashCode = self.age;
    // 奇素数 hashCode * 31 == (hashCode<<5) - hashCode
    hashCode = (hashCode<<5) - hashCode;
    return hashCode;
}
复制代码

上面的计算是仿照JDK的方式,将整数乘以31得出哈希值,因为31是一个奇素数,和它相乘可以更容易达到唯一性,减少冲突。

既然重写了hash方法,还需要配套重写对象的 isEqual方法,一个正确的判断逻辑需要满足:

  • 两个对象isEqual:判断为true,那么两个对象hash返回值一定相等。
  • 哈希值相等的两个对象,isEqual: 不一定相等。

想象一下,如果两个对象isEqual:返回true,意味着两个对象相等,但是它们的哈希值不想等,意味着它们可能存放在哈希表中的不同位置,这样就相当于Map或者NSDictionary中存放了两个key相同的键值对,这明显是不符合逻辑的。

key的哈希值我们已经知道如何使用默认和自定义的方法返回,下面我们通过key的哈希值计算其在数组中的index。首先key的哈希值也是一个整数,并且长度不一定。比如上面,默认返回:4345477856,我们自定义hash方法后返回31。假设我们的数组长度只有8,那么肯定不能将key的哈希值直接当作数组中的index。

这里我们可以通过 & 位运算来得到,前提是数组的长度是2的n次方,假设数组的长度为 2^3 = 8,8 - 1 = 7,其对应的二进制位为:0111。

下面我们和0111做 & 位运算的效果:

// 十进制253
1111 1101 
&    0111
---------
     0101 = 5
     
     
// 十进制31
0001 1111
&    0111
---------
     0111 = 7
     
     
// 十进制8
0000 1000
&    0111
---------
     0000 = 0
复制代码

可以看到,任何数字和7做&位运算的结果都不会大于8,即key的哈希值通过和数组长度-1的值(数组长度为2的幂)做&位运算就可以得到key哈希值对应在数组中的index:

- (NSUInteger)indexWithKey:(id)key {
    if (!key) return 0;
    NSUInteger hash = [key hash];
    return hash & (self.array.length - 1);
}
复制代码

现在这个函数还不是很好用,比如下面的情况,假定哈希表长度为2^6,2^6 - 1 = 63,二进制位为:0011 1111

// 6390901416293117903
0101 1000 1011 0001 
0000 1010 1111 1010 
0100 1000 1011 0001 
0010 1111 1100 1111
&          011 1111
----------------------
           000 1111 = 15
     
     
// 6390901416293511119
0110 1000 1011 0010 
0000 1010 1111 1010
0100 1000 1011 0111 
0010 1111 1100 1111            
&          011 1111
----------------------
           000 1111 = 15
复制代码

6390901416293117903 和 6390901416293511119 由于最后7位2进制位都是 1001111,所以和 011 1111 做位运算之后结果都是 000 1111 = 15,高位都没有参与运算,导致只要末 7 位一样的哈希值的key在数组中index都相同,而我们应该尽量让所有的哈希值位数都参与运算。

下面将哈希值右移16位,然后和原来的哈希值做 ^ 运算,然后在与数组长度 -1 做 & 运算,之后的结果:

(6390901416293117903 ^ (6390901416293117903 >> 16)) & 63); // 62
(6390901416293511119 ^ (6390901416293511119 >> 16)) & 63); // 56
复制代码

下面是优化后最终哈希表的哈希函数:

- (NSUInteger)indexWithKey:(id)key {
    if (!key) return 0;
    NSUInteger hash = [key hash];
    return (hash ^ (hash >> 16)) & (self.array.length - 1);
}
复制代码

虽然上面的优化可以一定程度避免不同的哈希值计算出相同的index,但是依然不能完全避免,比如:6390901416293117903 和 6681946542211936207,因为它们的二进制的最后八位一样,而右移后的最后八位仍然一样,最终和63做位运算的最后几位也是一样的值,这样就不可避免的出现的不同key通过哈希函数计算后,在数组中的index是相同的情况。

哈希冲突

对键值对需要存放如哈希表,通过key计算出index后,发现哈希表中该位置已经存放了其它键值对。数组中index位置键值对的key和当前正在添加的键值对的key,通过哈希函数计算出得index是一样的,就会出现这种问题。出现这种问题分为两种情况:

  • 当前的key和数组中index位置的key是相等的,这种只需要将新键值覆盖就可以了。
  • 当前的key和数组的index位置的key是不相等的,即两个不同的key,通过哈希函数计算得出的index相同。

出现第二种情况就是所谓的哈希冲突,这种冲突是不可避免的,解决哈希冲突的办法有很多种:

  • 再次通过其它规则计算index,直到找到一个空的位置。
  • 找到index前面或者后面第一个不为空的位置。
  • 仍在index位置放置元素,并将两个元素以链表等形式存储。

我们这里采用第三种方式,即发现冲突的时候,以链表的形式将一个index内的所有元素串起来,如下图:

存储Jack:20 的时候,通过哈希函数计算出得index = 2,发现哈希表中index为2的位置已经有了其它节点,这时就将最后一个节点的next指向新的节点。

这种情况下的取值如下图:

首先通过哈希函数计算key对应的index,然后找到数组中对应位置的第一个节点,比较该节点存储的key和查询的key是否相等,如果不相等则通过该节点next指针找到下一个节点,重复判断过程,直到找到key相等的节点。

哈希表的基本结构

通过上面的分析,哈希表的结构其实已经很清晰了,首先哈希表是一个静态数组,数据中存放哈希表的节点,哈希表的节点是一个单向链表的结构,每一个节点通过next指针指向下一个节点,节点另外需要两个指针指向key和value。我们还需要实现一个哈希函数,可以通过key计算出其对应在哈希表中的位置,这个函数我们前面已经实现了。

我这里将哈希表封装成一个类似字典的类,外部接口完全和系统的NSMutableDictionary一致,实现的功能也是一样的。首先创建一个JKRHashMap_LinkedList类。

_size来保存当前哈希表存放的键值对的数量,注意区分这里的_size是存放键值对的数量,而不是哈希表的长度。

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface JKRHashMap_LinkedList<KeyType, ObjectType> : NSObject{
@protected
    /// 节点个数
    NSUInteger _size;
}

/// 元素个数
- (NSUInteger)count;
/// 清空所有元素
- (void)removeAllObjects;
/// 删除元素
- (void)removeObjectForKey:(KeyType)key;
/// 添加一个元素
- (void)setObject:(nullable ObjectType)object forKey:(nullable KeyType)key;
/// 获取元素
- (nullable ObjectType)objectForKey:(nullable KeyType)key;
/// 是否包含元素
- (BOOL)containsObject:(nullable ObjectType)object;
/// 是否包含key
- (BOOL)containsKey:(nullable KeyType)key;

@end

@interface JKRHashMap_LinkedList<KeyType, ObjectType> (JKRExtendedHashMap)

- (nullable ObjectType)objectForKeyedSubscript:(nullable KeyType)key;
- (void)setObject:(nullable ObjectType)obj forKeyedSubscript:(nullable KeyType)key;

@end


NS_ASSUME_NONNULL_END
复制代码

然后创建哈希表的节点对象:

@interface JKRHashMap_LinkedList_Node : NSObject

@property (nonatomic, strong) id key;
@property (nonatomic, strong) id value;
@property (nonatomic, strong) JKRHashMap_LinkedList_Node *next;

@end
复制代码

哈希表的基本功能

初始化

首先哈希表中应该有一个静态数组,由于Objective-C不提供,所以在第一篇文章中已经提前实现了一个静态数组,它需要在哈希表初始化的时候创建,并且长度为2的幂:

@interface JKRHashMap_LinkedList ()

@property (nonatomic, strong) JKRArray *array;

@end

@implementation JKRHashMap_LinkedList

- (instancetype)init {
    self = [super init];
    self.array = [JKRArray arrayWithLength:1 << 4];
    return self;
}

@end
复制代码

哈希函数

前面已经实现了,这里直接就可以使用:

- (NSUInteger)indexWithKey:(id)key {
    if (!key) return 0;
    NSUInteger hash = [key hash];
    return (hash ^ (hash >> 16)) & (self.array.length - 1);
}
复制代码

通过key查找节点

正如上面分析的查找过程,

  • 1,首先通过哈希函数找到key对应的index。
  • 2,通过index获取哈希表中对应位置的节点。
  • 3,如果节点为空,则key不在哈希表中,返回null。
  • 4,如果节点存在,则比较节点的key的查询key是否相等,相等直接返回该节点,否则进入下一步。
  • 5,得到该节点的下一个节点,重复第三步。
- (JKRHashMap_LinkedList_Node *)nodeWithKey:(id)key {
    NSUInteger index = [self indexWithKey:key];
    JKRHashMap_LinkedList_Node *node= self.array[index];
    while (node) {
        if (node.key == key || [node.key isEqual:key]) {
            return node;
        } else if (key && node.key && [key class] == [node.key class] && [key respondsToSelector:@selector(compare:)] && [key compare:node.key] == 0){
            return node;
        }
        node = node.next;
    }
    return node;
}
复制代码

通过key获取object

上面已经实现了通过key获取节点,这里只需要将返回的节点的value返回:

- (id)objectForKey:(id)key {
    JKRHashMap_LinkedList_Node *node = [self nodeWithKey:key];
    return node ? node.value : nil;
}
复制代码

是否存包含key

上面已经实现了通过key获取节点,这里只需要判断返回的节点是否为空:

- (BOOL)containsKey:(id)key {
    return [self nodeWithKey:key] != nil;
}
复制代码

返回哈希表的键值对数量

只需要返回_size:

- (NSUInteger)count {
    return _size;
}
复制代码

添加键值对

添加键值对的步骤:

  • 1,通过key计算出index。
  • 2,通过index取出哈希表对应位置的节点。
  • 3,如果节点为空,直接创建一个新节点并存储传入的key和value,并将节点指针存入哈希表, _size++。否则进入下一步。
  • 4,判断节点的key和传入的key是否相等,如果相等,则需要进行覆盖操作,将传入的key和value覆盖节点的key和value。否则进入下一步。
  • 5,保存一下该节点为preNode,然后获取该节点的下一个节点,判断节点是否为空,如果为空,创建一个新节点,将key和value存入新节点的key和value,并将preNode的next指向新节点,_size++。否则返回步骤4。
- (void)setObject:(id)object forKey:(id)key {
    NSUInteger index = [self indexWithKey:key];
    JKRHashMap_LinkedList_Node *node = self.array[index];
    if (!node) {
        node = [JKRHashMap_LinkedList_Node new];
        node.key = key;
        node.value = object;
        self.array[index] = node;
        _size++;
        return;
    }
    
    JKRHashMap_LinkedList_Node *preNode = nil;
    while (node) {
        if (node.key == key || [node.key isEqual:key]) {
            break;
        } else if (key && node.key && [key class] == [node.key class] && [key respondsToSelector:@selector(compare:)] && [key compare:node.key] == 0) {
            break;
        }
        preNode = node;
        node = node.next;
    }
    
    if (node) {
        node.key = key;
        node.value = object;
        return;
    }
    
    JKRHashMap_LinkedList_Node *newNode = [JKRHashMap_LinkedList_Node new];
    newNode.key = key;
    newNode.value = object;
    preNode.next = newNode;
    _size++;
}
复制代码

删除键值对

  • 1,通过key计算出index。
  • 2,通过index取出当前哈希表对应的节点。
  • 3,判断该节点是否为空,如果节点为空,直接返回。否则进入下一步。
  • 4,判断该节点的key是否和传入的key相等,如果相等,删除该节点,_size--。 否则进入下一步。
  • 5,拿到该节点的下一个节点,重复第4步。
- (void)removeObjectForKey:(id)key {
    NSUInteger index = [self indexWithKey:key];
    JKRHashMap_LinkedList_Node *node= self.array[index];
    JKRHashMap_LinkedList_Node *preNode = nil;
    while (node) {
        if (node.key == key || [node.key isEqual:key]) {
            if (preNode) {
                preNode.next = node.next;
            } else {
                self.array[index] = node.next;
            }
            _size--;
            return;
        } else if (key && node.key && [key class] == [node.key class] && [key respondsToSelector:@selector(compare:)] && [key compare:node.key] == 0){
            if (preNode) {
                preNode.next = node.next;
            } else {
                self.array[index] = node.next;
            }
            _size--;
            return;
        }
        preNode = node;
        node = node.next;
    }
}
复制代码

是否包含某元素

因为哈希表的value存放在节点中,并且无法直接找到其位置,只能通过遍历哈希表所有节点实现:

- (BOOL)containsObject:(id)object {
    if (_size == 0) {
        return NO;
    }
    
    for (NSUInteger i = 0; i < self.array.length; i++) {
        JKRHashMap_LinkedList_Node *node= self.array[i];
        while (node) {
            if (node.value == object || [node.value isEqual:object]) {
                return YES;
            }
            node = node.next;
        }
    }
    return NO;
}
复制代码

让自定义的哈希表支持字典运算符

- (id)objectForKeyedSubscript:(id)key {
    return [self objectForKey:key];
}

- (void)setObject:(id)obj forKeyedSubscript:(id)key {
    [self setObject:obj forKey:key];
}
复制代码

重写打印方便查看哈希表结构

- (NSString *)description {
    NSMutableString *string = [NSMutableString string];
    [string appendString:[NSString stringWithFormat:@"<%@, %p>: \ncount:%zd length:%zd\n{\n", self.className, self, _size, self.array.length]];
    for (NSUInteger i = 0; i < self.array.length; i++) {
        [string appendString:[NSString stringWithFormat:@"\n\n--- index: %zd ---\n\n", i]];
        JKRHashMap_LinkedList_Node *node= self.array[i];
        if (node) {
            while (node) {
                [string appendString:[NSString stringWithFormat:@"[%@:%@ -> %@%@] ", node.key , node.value, node.next ? [NSString stringWithFormat:@"%@:", node.next.key] : @"NULL", node.next ? node.next.value : @""]];
                node = node.next;
                if (i) {
                    [string appendString:@", "];
                }
            }
        } else {
            [string appendString:@"   "];
            [string appendString:@"NULL"];;
        }
    }
    [string appendString:@"\n}"];
    return string;
}

复制代码

哈希表的功能测试

JKRHashMap_LinkedList *dic = [JKRHashMap_LinkedList new];
for (NSUInteger i = 0; i < 30; i++) {
    NSString *key = getRandomStr();
    dic[key] = [NSString stringWithFormat:@"%zd", i];
}
NSLog(@"%@", dic);

// 打印:
<JKRHashMap_LinkedList, 0x102814a10>: 
count:30 length:16
{


--- index: 0 ---

[Wlqvuq:2 -> Xecsbw:9] [Xecsbw:9 -> Kvfexi:11] [Kvfexi:11 -> NULL] 

--- index: 1 ---

[Ifaeuy:15 -> NULL] , 

--- index: 2 ---

[Bmitqy:3 -> Ynqbcw:12] , [Ynqbcw:12 -> NULL] , 

--- index: 3 ---

[Djwmew:0 -> Epzzlc:4] , [Epzzlc:4 -> Jqjrvq:22] , [Jqjrvq:22 -> NULL] , 

--- index: 4 ---

[Myvwre:28 -> NULL] , 

--- index: 5 ---

[Mrgpfv:8 -> Ltdazq:25] , [Ltdazq:25 -> Tzweni:27] , [Tzweni:27 -> NULL] , 

--- index: 6 ---

   NULL

--- index: 7 ---

[Eyvque:5 -> Ltmzik:24] , [Ltmzik:24 -> NULL] , 

--- index: 8 ---

[Rvnupm:7 -> NULL] , 

--- index: 9 ---

[Ryrort:16 -> NULL] , 

--- index: 10 ---

[Rsdkaw:1 -> Hgszuk:20] , [Hgszuk:20 -> Jtrtes:26] , [Jtrtes:26 -> NULL] , 

--- index: 11 ---

[Txonlm:29 -> NULL] , 

--- index: 12 ---

[Bvbdbe:14 -> NULL] , 

--- index: 13 ---

[Pszvix:6 -> Dtizif:19] , [Dtizif:19 -> Czkxyj:21] , [Czkxyj:21 -> Kzatxv:23] , [Kzatxv:23 -> NULL] , 

--- index: 14 ---

[Ustobp:10 -> Erqclk:13] , [Erqclk:13 -> Fbliqs:17] , [Fbliqs:17 -> Jpcvbm:18] , [Jpcvbm:18 -> NULL] , 

--- index: 15 ---

   NULL

}
复制代码

可以看到,哈希表中的值平均分散在数组中,出现哈希冲突时,以单向链表的形式存储。

和NSMutableDictionary对比哈希表的性能测试

既然要做性能的对比测试,首先需要数据,这里使用苹果公布的objc4源代码,官方下载地址:opensource.apple.com/tarballs/ob…,将其中runtime的源码文件夹当作资源文件:

读取其中所有文件的代码,取出其中的所有单词,计算不同单词出现的次数。

这个需求刚好可以利用字典或者我们自定义的哈希表,将单词做为key,将单词出现的次数做为value,计算逻辑如下:

  • 首先读取所有文件并截取出所有单词(包括重复的)。
  • 遍历所有单词,将单词做为key,依次添加到哈希表中。
  • 添加前,先通过key从哈希表中取值,如果取到,则value为取到的值+1,否则为1,将key、value存入哈希表中。

这样当依次遍历添加完所有单词后,哈希表中存放的就是每个单词出现的次数。

首先取出所有单词:

NSMutableArray * allFileStrings() {
    NSFileManager *fileManager = [NSFileManager defaultManager];
    NSError *fileManagerError;
    NSString *fileDirectory = @"/Users/Lucky/Documents/SourceCode/runtime";
    
    NSArray<NSString *> *array = [fileManager subpathsOfDirectoryAtPath:fileDirectory error:&fileManagerError];
    if (fileManagerError) {
        NSLog(@"读取文件夹失败");
        nil;
    }
    NSLog(@"文件路径: %@", fileDirectory);
    NSLog(@"文件个数: %zd", array.count);
    NSMutableArray *allStrings = [NSMutableArray array];
    [array enumerateObjectsUsingBlock:^(NSString *  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        NSString *filePath = [fileDirectory stringByAppendingPathComponent:obj];
        NSError *fileReadError;
        NSString *str = [NSString stringWithContentsOfFile:filePath encoding:NSUTF8StringEncoding error:&fileReadError];
        if (fileReadError) {
            return;
        }
        [str enumerateSubstringsInRange:NSMakeRange(0, str.length) options:NSStringEnumerationByWords usingBlock:^(NSString * _Nullable substring, NSRange substringRange, NSRange enclosingRange, BOOL * _Nonnull stop) {
            [allStrings addObject:substring];
        }];
    }];
    NSLog(@"所有单词的数量: %zd", allStrings.count);
    return allStrings;
}
复制代码

然后依次遍历并加入哈希表中:

JKRHashMap_LinkedList *map = [JKRHashMap_LinkedList new];
[JKRTimeTool teskCodeWithBlock:^{
    NSMutableDictionary *map = [NSMutableDictionary new];
    [allStrings enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        NSNumber *count = map[obj];
        if (count) {
            count = [NSNumber numberWithInteger:count.integerValue+1];
        } else {
            count = [NSNumber numberWithInteger:1];
        }
        map[obj] = count;
    }];
    NSLog(@"NSMutableDictionary 计算不重复单词数量和出现次数 %zd", map.count);
    NSLog(@"NSMutableDictionary 计算单词出现的次数NSObject: %@", map[@"NSObject"]);
    NSLog(@"NSMutableDictionary 计算单词出现的次数include: %@", map[@"include"]);
    NSLog(@"NSMutableDictionary 计算单词出现的次数return: %@", map[@"return"]);
    
    __block NSUInteger allCount = 0;
    [allStrings enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        allCount += [map[obj] integerValue];
        [map removeObjectForKey:obj];
    }];
    
    NSLog(@"NSMutableDictionary 累加计算所有单词数量 %zd", allCount);
}];

// 打印:
文件个数: 104
所有单词的数量: 165627
JKRHashMap_LinkedList 计算不重复单词数量和出现次数 10490
JKRHashMap_LinkedList 计算单词出现的次数NSObject: 34
JKRHashMap_LinkedList 计算单词出现的次数include: 379
JKRHashMap_LinkedList 计算单词出现的次数return: 2681
JKRHashMap_LinkedList 累加计算所有单词数量 165627
耗时: 14.768 s
复制代码

下面使用NSMutableDictionary测试一遍:

[JKRTimeTool teskCodeWithBlock:^{
    NSMutableDictionary *map = [NSMutableDictionary new];
    [allStrings enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        NSNumber *count = map[obj];
        if (count) {
            count = [NSNumber numberWithInteger:count.integerValue+1];
        } else {
            count = [NSNumber numberWithInteger:1];
        }
        map[obj] = count;
    }];
    NSLog(@"NSMutableDictionary 计算不重复单词数量和出现次数 %zd", map.count);
    NSLog(@"NSMutableDictionary 计算单词出现的次数NSObject: %@", map[@"NSObject"]);
    NSLog(@"NSMutableDictionary 计算单词出现的次数include: %@", map[@"include"]);
    NSLog(@"NSMutableDictionary 计算单词出现的次数return: %@", map[@"return"]);
    
    __block NSUInteger allCount = 0;
    [allStrings enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        allCount += [map[obj] integerValue];
        [map removeObjectForKey:obj];
    }];
    
    NSLog(@"NSMutableDictionary 累加计算所有单词数量 %zd", allCount);
}];

// 打印:
文件个数: 104
所有单词的数量: 165627
NSMutableDictionary 计算不重复单词数量和出现次数 10490
NSMutableDictionary 计算单词出现的次数NSObject: 34
NSMutableDictionary 计算单词出现的次数include: 379
NSMutableDictionary 计算单词出现的次数return: 2681
NSMutableDictionary 累加计算所有单词数量 165627
耗时: 0.058 s
复制代码

发现所有的计算结果都是一样的,证明我们的哈希表确实可以和系统的NSMutableDictionary完成一样的功能,但是时间上有这非常大差距:14.768s VS 0.058s,好吧,简直慢到不能忍。

哈希表的优化-扩容

首先分析下为什么我们的哈希表这么慢,其实很简单,因为我们的哈希表默认容量是 1 << 4 = 16,长度只有16的数组内,分散存放了10490条数据,平均数组的一个位置存放了655个节点,即每个单向链表平均长度达到了655,而基于我们上面实现的哈希表的存、取、读都是通过单向链表从头节点开始遍历,那么当哈希表元素过多,链表长度越长时,遍历所需时间必然越长。

为了防止每条链表过长,我们需要在哈希表元素达到一定数量就要扩展哈希表数组的长度,这非常类似于动态数组的扩容操作。同时,如果哈希表数组长度发生变化,每个key对应哈希函数计算出的index必然发生变化,那么原来存放在哈希表中的节点还需要重新调整在哈希表中的位置。

那么什么时候去扩充哈希表的容量呢,据科学统计,当哈希表的存储的元素个数大于数组的长度 * 0.75时,扩容最优,我们就采用这个规则。

首先在添加键值对的方法最开始添加一个扩容方法:

- (void)setObject:(id)object forKey:(id)key {
    [self resize];
    // ...
}
复制代码

当数组元素个数小于哈希表长度 * 0.75 时,不去扩容,否则就扩容。

- (void)resize {
    if (_size <= self.array.length * 0.75) return;
    
}
复制代码

扩容需要创建一个新的容量更大的数组,这里我们采用扩容后的数组是原来的数组的两倍:

JKRArray *oldArray = self.array;
self.array = [JKRArray arrayWithLength:oldArray.length << 1];
复制代码

需要将原来数组中的所有节点重新排列在哈希表中,这里采用复用原来的节点,只将它们的位置重新排列,而不是依次取出值重新添加到哈希表中,因为这样需要重建创建所有节点,我们这里节省不必要的开销:

for (NSUInteger i = 0; i < oldArray.length; i++) {
    JKRHashMap_LinkedList_Node *node = oldArray[i];
    while (node) {
        JKRHashMap_LinkedList_Node *moveNode = node;
        node = node.next;
        moveNode.next = nil;
        // 重新排列节点
        [self moveNode:moveNode];
    }
}
复制代码

重新排列节点的逻辑如下:

  • 1,取出该节点的key计算index。
  • 2,通过index取出节点。
  • 3,判断节点是否为空。如果为空进入第4步,否则进入第5步。
  • 4,将数组index位置存放该节点。
  • 5,依次遍历到最后一个节点,将最后一个节点的next指向该节点。

完整扩容逻辑如下:

- (void)resize {
    if (_size <= self.array.length * 0.75) return;
    JKRArray *oldArray = self.array;
    self.array = [JKRArray arrayWithLength:oldArray.length << 1];
    for (NSUInteger i = 0; i < oldArray.length; i++) {
        JKRHashMap_LinkedList_Node *node = oldArray[i];
        while (node) {
            JKRHashMap_LinkedList_Node *moveNode = node;
            node = node.next;
            moveNode.next = nil;
            [self moveNode:moveNode];
        }
    }
}

- (void)moveNode:(JKRHashMap_LinkedList_Node *)newNode {
    NSUInteger index = [self indexWithKey:newNode.key];
    JKRHashMap_LinkedList_Node *node = self.array[index];
    if (!node) {
        self.array[index] = newNode;
        return;
    }
    JKRHashMap_LinkedList_Node *preNode = nil;
    while (node) {
        preNode = node;
        node = node.next;
    }
    preNode.next = newNode;
}
复制代码

扩容后性能对比

扩容后重复上面的测试,打印如下:

NSMutableDictionary 计算不重复单词数量和出现次数 10490
耗时: 0.066 s
JKRHashMap_LinkedList 计算不重复单词数量和出现次数 10490
耗时: 0.192 s
复制代码

时间已经从之前的 14.768s 减少到 0.192s。

接下来

仅仅使用单向链表实现的哈希表并不能够保证所有情况的查找速度,当哈希函数计算出现问题或者数据量特别大的时候,很可能出现某一条单向链表长度非常长。

在JDK开源的哈希表解决方案中,单链表长度超过一定值时,将链表转换成红黑树的方法解决这个问题,后面也会采用红黑树的方式重新实现一遍哈希表。但是在这之前,会先介绍队列和栈的实现,因为它们这是二叉树操作的基础。

源码

点击查看源码-

关注下面的标签,发现更多相似文章
评论