数据结构 - 哈希表

简介

  • 哈希表(Hash Table):也被称为 散列表字典,是根据关键码值(Key)直接进行访问的数据结构。具体来说,它通过将关键码值映射到底层数据结构的一个位置上来访问记录,这个映射关系就叫哈希函数,存放记录的数据结构通常为数组,这样就使得哈希表具备非常高效的数据查找等操作。

我们知道,数组存储的是值类型数据,链表存储的是结点(指针域 + 数据域)类型数据,而哈希表,它存储的是键-值对类型数据。

对于数组和链表等数据结构的查找,都是通过对各个结点进行比对判断,而哈希表的底层数据结构虽然是数组,但是它却另辟蹊径,通过对键进行一个映射(哈希函数),从而可以直接找到对应值的索引位置,然后借助数组数据获取O(1)的性能,使得哈希表的查找效率极高。

可以看出,哈希表通过哈希函数绕过了数组查找比对的过程,同时又利用了数组数据获取高效的性能,使得哈希表的数据操作性能十分高效。
同时,对于传统的数据结构(如数组,链表等),随着数据量的增加,其查找等操作效率会随着下降,而对于哈希表来说,无论数据量大小,它的查找效率能稳定保持在O(1)左右(哈希函数均匀情况下)。这也使得哈希表成为最受欢迎的数据结构之一。

构建哈希表

从上文对哈希表的描述中,可以知道,哈希表具备以下几个特征:

  • 数组:底层数据结构为数组,使之具备高效获取功能。
  • 键值对:存储的结点数据为键值对。
  • 哈希函数:具备一个映射关系(即哈希函数),可以将键值映射到底层数组的某一个索引上,对应的值就存在于该位置。

以下针对上述特征,构建一个简易版哈希表数据结构。如下所示:

:下文中的代码只是用于从底层原理对上层数据结构的实现,未经过严格的单元测试,可能存在严重漏洞,实现上不考虑性能,但着重于理解。

// 头文件:Map.h
#ifndef __MAP_H__
#define __MAP_H__

#define MAX_LENGTH 16

namespace YN {

    template<typename K, typename V>
    class Map;

    template<typename K, typename V>
    struct Entry {
        K key;
        V value;
        // 标识当前结点是否有效
        bool isNull;
        Entry() :isNull(true) {}
        Entry(K _key, V _value) : isNull(true), key(_key), value(_value) {}
    };


    template<typename K, typename V>
    class Iterator {
    protected:
        const Map<K, V>& map;
    public:
        Iterator(const Map<K, V>& _map) : map(_map) {}
    public:
        virtual bool hasNext() = 0;
        virtual V next() = 0;
    };

    template<typename K, typename V>
    class MapIterator : public Iterator<K, V> {
    public:
        MapIterator(const Map<K, V>& _map);
        virtual ~MapIterator();
    private:
        int curIndex;
        int count;
    public:
        bool hasNext() override;
        V next() override;
    };

    template<typename K, typename V>
    class Map {
    private:
        Entry<K, V> arr[MAX_LENGTH];
        Iterator<K, V>* iter;
        int length;
    public:
        Map();
        virtual ~Map();
        // 让 MapIterator 类成为 Map 友元,使得 MapInterator 可以访问 Map 的私有成员
        friend class MapIterator<K, V>;
    public:
        // 增
        // 改
        void put(const K& key, const V& value);
        // 删
        Entry<K, V> remove(const K& key);
        // 查
        V& get(const K& key) const;
        Iterator<K, V>* iterator();
    };
}
#endif

// 源文件:Map.cpp
#include "Map.h"
#include <iostream>

using namespace std;
using namespace YN;

namespace YN {

    template<typename K>
    int hash(const K& key) {
        // 假定 K 类型数据具备 length 方法(鸭子类型)
        return key.length() % MAX_LENGTH;
    }

}

template<typename K, typename V>
YN::MapIterator<K, V>::MapIterator(const Map<K, V>& _map) :Iterator<K, V>(_map), curIndex(0), count(0) {
}

template<typename K, typename V>
YN::MapIterator<K, V>::~MapIterator() {
}

template<typename K, typename V>
bool YN::MapIterator<K, V>::hasNext() {
    return this->curIndex < MAX_LENGTH
        && this->count < this->map.length;
}

template<typename K, typename V>
V YN::MapIterator<K, V>::next() {
    while (this->curIndex < MAX_LENGTH
        && this->count < this->map.length
        && this->map.arr[this->curIndex].isNull) {
        ++this->curIndex;
    }
    ++this->count;
    // 下次遍历从下一个位置开始
    ++this->curIndex;
    return this->map.arr[this->curIndex - 1].value;
}


template<typename K, typename V>
Map<K, V>::Map() :iter(nullptr), length(0) {
    //  memset(this->arr, 0, sizeof(this->arr));
}

template<typename K, typename V>
Map<K, V>::~Map() {
    if (this->iter) {
        delete this->iter;
    }
}

template<typename K, typename V>
void Map<K, V>::put(const K& key, const V& value) {
    // 对键进行哈希计算
    int keyIndex = YN::hash<K>(key);
    // 获取对应元素
    Entry<K, V>& entry = this->arr[keyIndex];
    // 设置键值对有效
    entry.isNull = false;
    // 依据键哈希索引存入数据
    entry.key = key;
    entry.value = value;
    // 长度加1
    ++this->length;
}

template<typename K, typename V>
Entry<K, V> Map<K, V>::remove(const K& key) {
    int keyIndex = YN::hash<K>(key);
    Entry<K, V>& entry = this->arr[keyIndex];
    // 这里状态设置无效,相当于删除(毕竟 C++ 没有空对象这一说法)
    this->arr[keyIndex].isNull = true;
    --this->length;
    return entry;
}

template<typename K, typename V>
V& Map<K, V>::get(const K& key) const {
    int keyIndex = YN::hash<K>(key);
    return this->arr[keyIndex];
}

template<typename K, typename V>
Iterator<K, V>* Map<K, V>::iterator() {
    if (this->iter) {
        delete this->iter;
    }
    return this->iter = new YN::MapIterator<K, V>(*this);
}

上述代码中的类Map就是我们对哈希表的抽象,其底层数据结构为一个定长数组Entry<K, V> arr[MAX_LENGTH],元素为键值对对象Entry<K,V>
我们对哈希表Map提供了增put、删remove、改put、查get以及遍历操作iterator,提供了这些数据基本操作,Map就具备了可用性。比如:

template<typename K, typename V>
void traverseMap(Map<K, V>& map) {
    Iterator<K, V>* iter = map.iterator();
    while (iter->hasNext()) {
        V value = iter->next();
        cout << value << endl;
    }
}

int main() {
    Map<string, string> map;
    map.put("zhangsan", "13688377123");
    map.put("lisi", "13688377456");
    map.put("wangwu", "13688377789");
    traverseMap(map);

    cout << "-------------remove lisi ----" << endl;

    map.remove("lisi");
    traverseMap(map);

    return 0;
}

一个需要注意的地方就是,每次对数组进行操作的时候,都需要对键进行一个映射,映射由哈希函数负责,上述代码中,我们使用的哈希函数如下所示:

template<typename K>
int hash(const K& key) {
    // 假定 K 类型数据具备 length 方法(鸭子类型)
    return key.length() % MAX_LENGTH;
}

其实很简单,这里我们只是将传递进来的键按其长度作为标准,取模使得长度索引落在底层数组索引范围内。
:由于 C++ 采用多继承机制,因此其没有像 Java 等其他单继承语言提供的泛型限定机制,因此这里采用类似动态语言的鸭子类型,假定传递的键类型具备有length方法。

但是按照上述哈希函数的特性,如果我们传入的多个键具备相同的长度,比如"aaa""bbb",这样多个不同的键会映射到同一个索引上,导致数据覆盖。对于这种现象,我们称之为键值冲突(Collision),其本质原因就是哈希函数对不同的输入产生相同的输出,也即发生了『哈希碰撞』。

哈希函数设计

从上文分析中,我们可以得出:哈希函数设计的好坏,对哈希表的数据操作效率有直接且深刻的影响

所有的哈希函数都会存在哈希碰撞(即冲突)问题,但一个好的哈希函数,会考虑到关键字的分布特点,以设计出尽量满足关键字分布均匀的哈希函数,这样存在哈希碰撞的概率就会减少很多,哈希表的性能会愈发高效。

简单来讲,哈希函数的构造目标应满足以下两个原则:

  • 哈希地址落在记录总数之内(即哈希结果小于底层数组长度)
  • 尽可能减少哈希碰撞

当前主流的哈希函数构造方法主要有如下几种:

  • 直接定址法:取关键字或关键字的某个线性函数作为哈希地址,即Hash(key)=keyHash(key)=key*a+b
    比如我们上述代码采用关键字的长度,即Hash(key) = length(key)
  • 平方取中法:对关键字进行平方运算,然后取结果的中间几位作为哈希地址。
    比如有以下关键字序列{421,423,436},平方之后的结果为{177241,178929,190096},那么可以取中间的两位数{72,89,00}作为哈希地址。
  • 折叠法:将关键字拆分成位数相同的几部分(最后一部分位数可以不同),然后叠加这几部分内容作为哈希地址。
    比如图书的 ISBN 号为 8903-241-23,则可以拆分为:89,03,24,12,3,然后进行叠加作为哈希地址:Hash(key)=89+03+24+12+3
  • 除留取余法:假设哈希表最大长度为m,有一个不大于m的质数p,则可将关键字对p进行取余运算作为哈希地址:Hash(key)=key mod p (p<=m)
    :除留取余法的关键在于质数p的选取,理论研究表明,p通常取不大于m的最大质数可达到最好效果。

更多哈希函数构造方法,可查看:hash函数的构造方法

哈希表冲突解决方法

哈希碰撞无法避免,因此冲突无法避免。

构造一个好的哈希函数是为了尽量让关键字均匀分布在哈希表中,这样对数据的访问效率会更高效,同时在很大的程度上减少冲突,但是仍然存在一定的可能发生哈希碰撞,此时需要对哈希碰撞导致的键值冲突进行处理,这样才能从根本上保证哈希表的数据存储安全(不会因为冲突导致某个键值被覆盖)。

当前主流的哈希冲突解决方法有如下几种方式:

  • 开放寻址法:即当一个关键字和另一个关键字发生冲突时,后面插入的关键字采用某种探测技术(比如:线性探测法,平方探测法...),对哈希表序列进行探测,直到找到一个未存储数据的空单元,则插入其中即可。
    比如,假定现有一个哈希表,其内容为[0,1,2,NULL,4,5,NULL],其中,NULL表示未存储数据,01等表示实际存储的数据值,可以很容易看出,该哈希表使用的哈希函数为:Hash(key)=key%7(7为数组长度),假设此时我们要插入数值8,则Hash(8)=8%7=1,哈希表索引1已经有数据,则此时可以采用线性探测法,沿着哈希表索引1往后依次进行探测,直到探测到索引3,发现没有数据存储,则将8插入到索引3中。后续要获取关键字8时,先对关键字8进行哈希计算,得到1,但是索引1的键值为1,与当前查询的键值不匹配,则可知道存在哈希碰撞,此时只需在当前位置往后进行遍历,依次比对键值,直到找到键值为8的数据即为所求(:哈希表存储的是键值对,当前的例子刚好键和值相同)。

    :可以看到,当发生哈希碰撞时,哈希表退化为线性查找,此时查找时间复杂度退化为O(n)

  • 链地址法:也成为 拉链法,采用的是数组和链表结合的方式,底层数组元素不再是键值对,而是存储一个链表。当发生冲突时,只需将数据插入到冲突地址所在的链表后边即可。当获取数据时,找到关键字所在地址,得到的是一个链表,对该链表进行遍历,然后找到匹配当前关键字的结点即可。

  • 再散列法:即存在多个哈希函数,当某个关键字使用第一个哈希函数发生冲突时,就使用下一个哈希函数,直至不发生冲突。

  • 创建公共溢出区:即创建两个表:基本表 + 溢出表。其中,基本表作为主要的哈希表,数据优先存储到基本表中,但是当发生冲突时,就将数据存储到溢出表中。溢出表的实现应该是一个线性表,当查询数据时,如果基本表中键值不匹配,就线性查找溢出表,直到找到关键字相匹配的数据。

其实,只要牢记哈希表存储的元素为键值对,上述的冲突解决方法就很好理解了。

总结

理论上来说,如果哈希函数是均匀的,则哈希表查询、删除、修改一个元素的时间复杂度为O(1)

但是由于哈希碰撞无法避免,因此哈希表存在冲突问题,因此需要对冲突进行处理,常见的处理方法为 开放寻址法链地址法再散列法创建公共溢出区

当冲突很严重时,即多个关键字都映射到同一个哈希地址时,哈希表的数据操作性能由O(1)退化到线性表操作的O(n)

因此,一个设计良好的哈希算法十分重要。可根据需要存储数据的数据量及其特征,采用不同的哈希函数设计。
常见的哈希函数设计方法有:直接定址法平方取中法折叠法除留取余法...

哈希表中其实还有一个概念也挺重要的:装填因子。其定义如下:

装填因子 = 填入表中的元素个数 / 哈希表的长度

因此,当装填因子越趋近于 1 时,则标识哈希表存储空间快满了,此时随便再插入一个数据,很大概率会产生冲突。这时候可以通过动态扩容,从而减小装填因子,减少冲突。

因此,一个好的哈希表应当满足如下 3 个条件:

  • 哈希函数构造良好,数据插入均匀分布
  • 具备冲突处理,具备容错性与健壮性
  • 具备动态扩容能力,能够很好规避数据量变多导致的问题

参考

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 217,084评论 6 503
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,623评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 163,450评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,322评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,370评论 6 390
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,274评论 1 300
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,126评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,980评论 0 275
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,414评论 1 313
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,599评论 3 334
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,773评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,470评论 5 344
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,080评论 3 327
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,713评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,852评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,865评论 2 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,689评论 2 354