01.jpg

什么是Hash表

先看一下hash表的結(jié)構(gòu)圖：

image

數(shù)組 + 鏈表

哈希表（Hash table，也叫散列表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說安拟，它通過計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來訪問記錄宵喂，這加快了查找速度糠赦。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表

白話一點(diǎn)的說就是通過把Key通過一個(gè)固定的算法函數(shù)（hash函數(shù)）轉(zhuǎn)換成一個(gè)整型數(shù)字，然后就對(duì)該數(shù)字對(duì)數(shù)組的長度進(jìn)行取余拙泽，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)淌山，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。

當(dāng)使用hash表查詢時(shí)顾瞻，就是使用hash函數(shù)將key轉(zhuǎn)換成對(duì)應(yīng)的數(shù)組下標(biāo)泼疑，并定位到該下標(biāo)的數(shù)組空間里獲取value，這樣就充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位朋其。

（上面的話王浴，需細(xì)細(xì)品味）

先了解一下下面幾個(gè)常說的幾個(gè)關(guān)鍵字是什么：

key：我們輸入待查找的值

value：我們想要獲取的內(nèi)容

hash值：key通過hash函數(shù)算出的值（對(duì)數(shù)組長度取模脆炎，便可得到數(shù)組下標(biāo)）

hash函數(shù)（散列函數(shù)）：存在一種函數(shù)F梅猿，根據(jù)這個(gè)函數(shù)和查找關(guān)鍵字key，可以直接確定查找值所在位置秒裕，而不需要一個(gè)個(gè)遍歷比較袱蚓。這樣就預(yù)先知道key在的位置，直接找到數(shù)據(jù)几蜻，提升效率喇潘。
即
地址index=F(key)
hash函數(shù)就是根據(jù)key計(jì)算出該存儲(chǔ)地址的位置，hash表就是基于hash函數(shù)建立的一種查找表梭稚。

Hash函數(shù)的構(gòu)造方法

方法

方法有很多種颖低，比如直接定址法、數(shù)字分析法弧烤、平方取中法忱屑、折疊法、隨機(jī)數(shù)法暇昂、除留余數(shù)法等莺戒，網(wǎng)上相關(guān)介紹有很多，這里就不重點(diǎn)說這個(gè)了

hash函數(shù)設(shè)計(jì)的考慮因素

• 計(jì)算hash地址所需時(shí)間（沒有必要搞一個(gè)很復(fù)雜的函數(shù)去計(jì)算）
• 關(guān)鍵字的長度
• 表長
• 關(guān)鍵字分布是否均勻急波，是否有規(guī)律可循
• 盡量減少?zèng)_突

hash沖突

什么是hash沖突

對(duì)不同的關(guān)鍵字可能得到同一散列地址从铲，即k1≠k2，而f(k1)=f(k2)澄暮，或f(k1) MOD 容量 =f(k2) MOD 容量名段，這種現(xiàn)象稱為碰撞，亦稱沖突泣懊。

通過構(gòu)造性能良好的hash函數(shù)吉嫩，可以減少?zèng)_突，但一般不可能完全避免沖突嗅定，因此解決沖突是hash表的另一個(gè)關(guān)鍵問題自娩。

創(chuàng)建和查找hash表都會(huì)遇到?jīng)_突，兩種情況下解決沖突的方法應(yīng)該一致。

解決hash沖突

• 開放定址法

這種方法也稱再散列法忙迁，基本思想是：當(dāng)關(guān)鍵字key的hash地址p=F(key)出現(xiàn)沖突時(shí)脐彩，以p為基礎(chǔ)，產(chǎn)生另一個(gè)hash地址p1姊扔，如果p1仍然沖突惠奸，再以p為基礎(chǔ)，再產(chǎn)生另一個(gè)hash地址p2恰梢，佛南。。嵌言。知道找出一個(gè)不沖突的hash地址pi嗅回，然后將元素存入其中。

通用的再散列函數(shù)的形式：

H = (F(key) + di) MOD m

其中i=1摧茴，2绵载，。苛白。娃豹。，m-1 為碰撞次數(shù)

m為表長购裙。

F(key)為hash函數(shù)懂版。

di為增量序列，增量序列的取值方式不同躏率，相應(yīng)的再散列方式也不同躯畴。

1） 線性探測(cè)再散列

di = 1，2禾锤，3私股，。恩掷。倡鲸。，m-1

沖突發(fā)生時(shí)黄娘，順序查看表中下一單元峭状，直到找出一個(gè)空單元或查遍全表。

2）二次探測(cè)再散列

di = 1^2, -1^2, 2^2, -2^2,..., k^2, -k^2 (k <= m-1)

發(fā)生沖突時(shí)逼争，在表的左右進(jìn)行跳躍式探測(cè)优床，比較靈活。

3）偽隨機(jī)數(shù)探測(cè)再散列

di = 偽隨機(jī)序列

下面有個(gè)網(wǎng)上的示列：
現(xiàn)有一個(gè)長度為11的哈希表誓焦，已填有關(guān)鍵字分別為17胆敞，60，29的三條記錄。其中采用的哈希函數(shù)為f(key)= key MOD 11∫撇悖現(xiàn)有第四個(gè)記錄仍翰，關(guān)鍵字為38。根據(jù)以上哈希算法观话，得出哈希地址為5予借，跟關(guān)鍵字60的哈希地址一樣，產(chǎn)生了沖突频蛔。根據(jù)增量d的取法的不同灵迫，有一下三種場(chǎng)景：

image

線性探測(cè)法： 當(dāng)發(fā)生沖突時(shí)，因?yàn)?code>f(key) + d晦溪，所以首先5 + 1 = 6瀑粥，得到下一個(gè)hash地址為6，又沖突尼变，依次類推利凑，最后得到空閑的hash地址是8浆劲，然后將數(shù)據(jù)填入hash地址為8的空閑區(qū)域嫌术。

二次探測(cè)法： 當(dāng)發(fā)生沖突時(shí)，因?yàn)?code>d = 1^2牌借，所以5 + 1 = 6度气，得到的下一個(gè)hash地址為6，又沖突膨报，因?yàn)?code>d = -1^2,所以5 + (-1) = 4磷籍，得到下一個(gè)hash地址為4，是空閑則將數(shù)據(jù)填入該區(qū)域现柠。

偽隨機(jī)數(shù)探測(cè)法： 隨機(jī)數(shù)法就是完全根據(jù)偽隨機(jī)序列來決定的院领，如果根據(jù)一個(gè)隨機(jī)數(shù)種子得到一個(gè)偽隨機(jī)序列{1，-2够吩，2比然，。周循。强法。，k}湾笛，那么首先得到的地址為6饮怯，第二個(gè)是3，依次類推嚎研，空閑則將數(shù)據(jù)填入蓖墅。

開放定址法在iOS中的應(yīng)用還是有很多的，具體可參考筆記-集合NSSet、字典NSDictionary的底層實(shí)現(xiàn)原理

• 鏈地址法（拉鏈法论矾，位桶法）

將產(chǎn)生沖突的關(guān)鍵字的數(shù)據(jù)存儲(chǔ)在沖突hash地址的一個(gè)線性鏈表中于樟。實(shí)現(xiàn)時(shí)，一種策略是散列表同一位置的所有沖突結(jié)果都是用棧存放的拇囊，新元素被插入到表的前端還是后端完全取決于怎樣方便迂曲。

image

負(fù)載因子（load factor）

這里要提到兩個(gè)參數(shù)：初始容量，加載因子寥袭，這兩個(gè)參數(shù)是影響hash表性能的重要參數(shù)路捧。

容量： 表示hash表中數(shù)組的長度，初始容量是創(chuàng)建hash表時(shí)的容量传黄。

加載因子： 是hash表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度（存儲(chǔ)元素的個(gè)數(shù)）杰扫，它衡量的是一個(gè)散列表的空間的使用程度。

loadFactor = 加載因子 / 容量

一般情況下膘掰，當(dāng)loadFactor <= 1時(shí)章姓，hash表查找的期望復(fù)雜度為O(1).

對(duì)使用鏈表法的散列表來說，負(fù)載因子越大识埋，對(duì)空間的利用更充分凡伊，然后后果是查找效率的降低；如果負(fù)載因子太小窒舟，那么散列表的數(shù)據(jù)將過于稀疏系忙，對(duì)空間造成嚴(yán)重浪費(fèi)。系統(tǒng)默認(rèn)負(fù)載因子為0.75惠豺。

擴(kuò)容

當(dāng)hash表中元素越來越多的時(shí)候银还，碰撞的幾率也就越來越高（因?yàn)閿?shù)組的長度是固定的），所以為了提高查詢的效率洁墙，就要對(duì)數(shù)組進(jìn)行擴(kuò)容蛹疯。而在數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了热监，原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置捺弦，并放進(jìn)去，這就是擴(kuò)容狼纬。

什么時(shí)候進(jìn)行擴(kuò)容呢羹呵？當(dāng)表中元素個(gè)數(shù)超過了容量 * loadFactor時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容疗琉。

用OC粗略的實(shí)現(xiàn)了一下擴(kuò)容的：

- (void)resizeOfNewCapacity:(NSInteger)newCapacity {
    NSInteger oldCapacity = _elementArray.count;
    if (oldCapacity == MAX_CAPACITY) {         // 擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大2^30
        _threshold = oldCapacity - 1;       // 修改閾值為int的最大值（2^30 - 1）冈欢，這樣以后就不會(huì)擴(kuò)容了
        return;
    }
    
    // 初始化一個(gè)新的數(shù)組
    NSMutableArray *newArray = [NSMutableArray arrayWithCapacity:newCapacity];
    for (int i = 0; i < newCapacity; i ++) {
        [newArray addObject:@""];
    }
    
    [self transferWithNewTable:newArray];            // 將數(shù)據(jù)轉(zhuǎn)移到新的數(shù)組里
    [_elementArray removeAllObjects];
    [_elementArray addObjectsFromArray:newArray];    // hash表的數(shù)組引用新建的數(shù)組
    _threshold = (NSInteger)_capacity * _loadFactor; // 修改閾值
}

- (void)transferWithNewTable:(NSMutableArray *)array {
    // 遍歷舊數(shù)組，將元素轉(zhuǎn)移到新數(shù)組中
    for (int i = 0; i < _elementArray.count; i ++) {
        if ([[[_elementArray objectAtIndex:i] class] isEqual:[SingleLinkedNode class]]) {
            SingleLinkedNode *node = _elementArray[I];
            if (node != NULL) {
                do {
                    [self insertElementToArrayWith:array andNode:node];
                    node = node.next;
                } while (node != NULL);
            }
        }
    }
}

- (void)insertElementToArrayWith:(NSMutableArray *)array andNode:(SingleLinkedNode *)node {
    NSInteger index = [node.key integerValue] % _capacity;                      // 計(jì)算每個(gè)元素在新數(shù)組中的位置
    if (![[[array objectAtIndex:index] class] isEqual:[SingleLinkedNode class]]) {
        [array replaceObjectAtIndex:index withObject:node];
    }else {
        SingleLinkedNode *headNode = [array objectAtIndex:index];
        while (headNode != NULL) {
            headNode = headNode.next;
        }
        // 直接把元素插入
        headNode.next = node;
    }
}

OC語言的實(shí)現(xiàn)

構(gòu)建HashTable對(duì)象

HashTable.h文件

#import <Foundation/Foundation.h>
@class SingleLinkedNode;

NS_ASSUME_NONNULL_BEGIN

@interface HashTable : NSObject

@property (nonatomic, strong) NSMutableArray *elementArray;
@property (nonatomic, assign) NSInteger capacity;       // 容量  數(shù)組（hash表）長度
@property (nonatomic, assign) NSInteger modCount;       // 計(jì)數(shù)器盈简，計(jì)算put的元素個(gè)數(shù)（不包括重復(fù)的元素）
@property (nonatomic, assign) float threshold;          // 閾值
@property (nonatomic, assign) float loadFactor;         // 加載因子

/**
 初始化Hash表

 @param capacity 數(shù)組的長度
 @return hash表
 */
- (instancetype)initWithCapacity:(NSInteger)capacity;

/**
 插入

 @param newNode 存入的鍵值對(duì)newNode
 */
- (void)insertElementByNode:(SingleLinkedNode *)newNode;

/**
 查詢

 @param key key值
 @return 想要獲取的value
 */
- (NSString *)findElementByKey:(NSString *)key;

@end

NS_ASSUME_NONNULL_END

HashTable.m文件：

#define MAX_CAPACITY pow(2, 30)

#import "HashTable.h"
#import "SingleLinkedNode.h"

@implementation HashTable

- (instancetype)initWithCapacity:(NSInteger)capacity {
    self = [super init];
    if (self) {
        _capacity = capacity;
        _loadFactor = 0.75;
        _threshold = (NSInteger) _loadFactor * _capacity;
        _modCount = 0;
        // 直接初始化數(shù)組凑耻，這里為了方便理解hash太示，所以就直接給定capacity，java中默認(rèn)是16
        _elementArray = [NSMutableArray arrayWithCapacity:capacity];
        for (int i = 0; i < capacity; i ++) {
            [_elementArray addObject:@""];
        }
    }
    return self;
}

- (void)insertElementByNode:(SingleLinkedNode *)newNode {
    if (newNode.key.length == 0) {
        return;
    }
    
    // 判斷是否需要擴(kuò)容
    if (_threshold < _modCount * _capacity) {
        _capacity *= 2;
        [self resizeOfNewCapacity:_capacity];
    }
    
    // 計(jì)算存儲(chǔ)位置
    NSInteger keyValue = [newNode.key integerValue]; // F(x) = x; 得到hash值
    NSInteger index = keyValue % _capacity;         // hash值 MOD 容量 = 數(shù)組下標(biāo)
    
    newNode.hashValue = keyValue;
    
    
    // 如果插入的區(qū)域是空閑的香浩，則直接把數(shù)據(jù)存入該空間區(qū)域
    if (![[[_elementArray objectAtIndex:index] class] isEqual:[SingleLinkedNode class]]) {
        [_elementArray replaceObjectAtIndex:index withObject:newNode];
        _modCount++;
    }else {
        // 發(fā)生沖突类缤，通過鏈表法解決沖突
        SingleLinkedNode *headNode = [_elementArray objectAtIndex:index];
        while (headNode != NULL) {
            // 插入的key重復(fù)，則覆蓋原來的元素
            if ([headNode.key isEqualToString:newNode.key]) {
                headNode.value = newNode.value;
                return;
            }
            headNode = headNode.next;
        }
        _modCount++;
        // 直接把元素插入
        headNode.next = newNode;
    }
}

- (NSString *)findElementByKey:(NSString *)key {
    if (key.length == 0) {
        return nil;
    }
    
    // 計(jì)算存儲(chǔ)位置
    NSInteger keyValue = [key integerValue];
    NSInteger index = keyValue % _capacity;    // hash函數(shù)keyValue % _capacity (0~9)
    
    if (index >= _capacity) {
        return nil;
    }
    
    if (![[[_elementArray objectAtIndex:index] class] isEqual:[SingleLinkedNode class]]) {
        return nil;
    }else {
        // 遍歷鏈表邻吭，知道找到key值相等的node餐弱，然后返回value
        SingleLinkedNode *headNode = [_elementArray objectAtIndex:index];
        while (headNode != NULL) {
            if ([headNode.key isEqualToString:key]) {
                return headNode.value;
            }
            headNode = headNode.next;
        }
        return nil;
    }
}

- (void)resizeOfNewCapacity:(NSInteger)newCapacity {
    NSInteger oldCapacity = _elementArray.count;
    if (oldCapacity == MAX_CAPACITY) {         // 擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大2^30
        _threshold = oldCapacity - 1;       // 修改閾值為int的最大值（2^30 - 1），這樣以后就不會(huì)擴(kuò)容了
        return;
    }
    
    // 初始化一個(gè)新的數(shù)組
    NSMutableArray *newArray = [NSMutableArray arrayWithCapacity:newCapacity];
    for (int i = 0; i < newCapacity; i ++) {
        [newArray addObject:@""];
    }
    
    [self transferWithNewTable:newArray];            // 將數(shù)據(jù)轉(zhuǎn)移到新的數(shù)組里
    [_elementArray removeAllObjects];
    [_elementArray addObjectsFromArray:newArray];    // hash表的數(shù)組引用新建的數(shù)組
    _threshold = (NSInteger)_capacity * _loadFactor; // 修改閾值
}

- (void)transferWithNewTable:(NSMutableArray *)array {
    // 遍歷舊數(shù)組囱晴，將元素轉(zhuǎn)移到新數(shù)組中
    for (int i = 0; i < _elementArray.count; i ++) {
        if ([[[_elementArray objectAtIndex:i] class] isEqual:[SingleLinkedNode class]]) {
            SingleLinkedNode *node = _elementArray[I];
            if (node != NULL) {
                do {
                    [self insertElementToArrayWith:array andNode:node];
                    node = node.next;
                } while (node != NULL);
            }
        }
    }
}

- (void)insertElementToArrayWith:(NSMutableArray *)array andNode:(SingleLinkedNode *)node {
//    下面這個(gè)方法沒有成功的獲取到新數(shù)組中的位置
//    NSInteger index = [self indexForHashValue:node.hashValue andNewCapacity:array.count];
    NSInteger index = [node.key integerValue] % _capacity;                      // 計(jì)算每個(gè)元素在新數(shù)組中的位置
    if (![[[array objectAtIndex:index] class] isEqual:[SingleLinkedNode class]]) {
        [array replaceObjectAtIndex:index withObject:node];
    }else {
        SingleLinkedNode *headNode = [array objectAtIndex:index];
        while (headNode != NULL) {
            headNode = headNode.next;
        }
        // 直接把元素插入
        headNode.next = node;
    }
}

- (NSInteger)indexForHashValue:(NSInteger)hash andNewCapacity:(NSInteger)newCapacity {
    return hash & (newCapacity - 1);
}

@end

SingleLinkedNode.h文件：

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface SingleLinkedNode : NSObject <NSCopying>

@property (nonatomic, strong) NSString *key;
@property (nonatomic, strong) NSString *value;
@property (nonatomic, strong) SingleLinkedNode *next;
@property (nonatomic, assign) NSInteger hashValue;

- (instancetype)initWithKey:(NSString *)key value:(NSString *)value;

@end

NS_ASSUME_NONNULL_END

SingleLinkedNode.m文件：

#import "SingleLinkedNode.h"

@implementation SingleLinkedNode

- (instancetype)initWithKey:(NSString *)key value:(NSString *)value {
    if (self = [super init]) {
        _key = key;
        _value = value;
    }
    return self;
}

@end

上面代碼看起來或許有些亂膏蚓，感興趣的小伙伴可以在這里下載demo傳送門

總結(jié)：
這篇文章主要是了解hash表，以及hash表的實(shí)現(xiàn)特性畸写，并且使用OC語言簡單的粗略的實(shí)現(xiàn)了Hash表驮瞧，如果有什么錯(cuò)誤，希望小伙伴們留言告知枯芬，謝謝论笔。