C++数据结构之哈希表的实现

目录
  • 哈希表概念
  • 散列函数
    • 直接定址法
    • 除留余数法
    • 平方取中法
  • 哈希冲突
    • 线性探测
    • 二次探测
    • 链地址法
  • 哈希表的实现
    • 闭散列
    • 开散列

哈希表概念

二叉搜索树具有对数时间的表现,但这样的表现建立在一个假设上:输入的数据有足够的随机性。哈希表又名散列表,在插入、删除、搜索等操作上具有「常数平均时间」的表现,而且这种表现是以统计为基础,不需依赖输入元素的随机性。

听起来似乎不可能,倒也不是,例如:

假设所有元素都是 8-bits 的正整数,范围 0~255,那么简单得使用一个数组就可以满足上述要求。首先配置一个数组 Q,拥有 256 个元素,索引号码 0~255,初始值全部为 0。每一个元素值代表相应的元素的出现次数。如果插入元素 i,就执行 Q[i]++,如果删除元素 i,就执行 Q[i]--,如果查找元素 i,就看 Q[i] 是否为 0。

这个方法有两个很严重的问题。

  • 如果元素是 32-bits,数组的大小就是232=4GB,这就太大了,更不用说 64-bits 的数了
  • 如果元素类型是字符串而非整数,就需要某种方法,使其可用作数组的索引

散列函数

如何避免使用一个太大的数组,以及如何将字符串转化为数组的索引呢?一种常见的方法就是使用某种映射函数,将某一元素映射为一个「大小可接受的索引」,这样的函数称为散列函数。

散列函数应有以下特性:

  • 函数的定义域必须包含需要存储的全部关键字,当散列表有 m 个地址时,其值域在 0 到 m - 1 之间
  • 函数计算出来的地址能均匀分布在整个空间

直接定址法

取关键字的某个线性函数为散列地址:Hash(Key)=A∗Key+B

优点:简单、均匀

缺点:需要事先知道关键字的分布情况

使用场景:数据范围比较集中的情况

除留余数法

设散列表的索引个数为 m,取一个不大于 m,但最接近 m 的质数 p 最为除数,按照散列函数:Hash(Key)=key,将关键字转化为哈希地址

平方取中法

假设关键字为 1230,它的平方是 1512900,取中间的 3 位 129 作为哈希地址;

再比如关键字为 321,它的平方是 103041,取中间的 3 位 304(或 30)作为哈希地址。

哈希冲突

使用散列函数会带来一个问题:可能有不同的元素被映射到相同的位置。这无法避免,因为元素个数大于数组的容量,这便是「哈希冲突」。解决冲突问题的方法有很有,包括线性探测、二次探测、开散列等。

线性探测

当散列函数计算出某个元素的插入位置,而该位置上已有其他元素了。最简单的方法就是向下一一寻找(到达尾端,就从头开始找),直到找到一个可用位置。

进行元素搜索时同理,如果散列函数计算出来的位置上的元素值与目标不符,就向下一一寻找,直到找到目标值或遇到空。

至于元素的删除,必须采用伪删除,即只标记删除记号,实际删除操作在哈希表重新整理时再进行。这是因为哈希表中的每一个元素不仅表示它自己,也影响到其他元素的位置。

从上述插入过程我们可以看出,当哈希表中元素变多时,发生冲突的概率也变大了。由此,我们引出哈希表一个重要概念:负载因子。

负载因子定义为:Q = 表中元素个数 / 哈希表的长度

  • 负载因子越大,剩余可用空间越少,发生冲突可能越大
  • 负载因子越小,剩余可用空间越多,发生冲突可能越小,同时空间浪费更多

因此,控制负载因子是个非常重要的事。对于开放定址法(发生了冲突,就找下一个可用位置),负载因子应控制在 0.7~0.8 以下。超过 0.8,查找时的 CPU 缓存不命中按照指数曲线上升。

二次探测

线性探测的缺陷是产生冲突的数据会堆在一起,这与其找下一个空位置的方式有关,它找空位置的方式是挨着往后逐个去找。二次探测主要用来解决数据堆积的问题,其命名由来是因为解决碰撞问题的方程式F(i)=i2是个二次方程式。

更具体地说,如果散列函数计算出新元素的位置为 H,而该位置实际已被使用,那么将尝试H+12,H+22,H+32,...,H+i2,而不是像线性探测那样依次尝试H+1,H+2,H+3,...,H+i。

大量实验表明:当表格大小为质数,而且保持负载因子在 0.5 以下(超过 0.5 就重新配置),那么就可以确定每插入一个新元素所需要的探测次数不超过 2。

链地址法

这种方法是在每一个表格元素中维护一个链表,在呢个链表上执行元素的插入、查询、删除等操作。这时表格内的每个单元不再只有一个节点,而可能有多个节点。

节点的定义:

template <class Value>
struct __hashtable_node {
	__hashtable_node* next;
    Value val;
};

哈希表的实现

闭散列

接口总览

template <class K, class V>
class HashTable {
	struct Elem {
		pair<K, V> _kv;
		State _state = EMPTY;
	};
public:
	Elem* Find(const K& key);
	bool Insert(const pair<K, V>& kv);
	bool Erase(const K& key);
private:
	vector<Elem> _table;
	size_t _n = 0;
};

节点的结构

因为在闭散列的哈希表中的每一个元素不仅表示它自己,也影响到其他元素的位置。所以要使用伪删除,我们使用一个变量来表示。

/// @brief 标记每个位置状态
enum State {
    EMPTY,    // 空
    EXIST,    // 有数据
    DELETE    // 有数据,但已被删除
};

哈希表的节点结构,不仅存储数据,还存储状态。

/// @brief 哈希表的节点
struct Elem {
    pair<K, V> _kv;    // 存储数据
    State _state;    // 存储状态
};

查找

查找的思路比较简单:

  • 利用散列函数获取映射后的索引
  • 遍历数组看是否存在,直到遇到空表示查找失败
/// @brief 查找指定 key
/// @param key 待查找节点的 key 值
/// @return 找到返回节点的指针,没找到返回空指针
Elem* Find(const K& key) {
    if (_table.empty()) {
        return nullptr;
    }

    // 使用除留余数法的简化版本,并没有寻找质数
    // 同时,该版本只能用于正整数,对于字符串等需使用其他散列函数
    size_t start = key % _table.size();
    size_t index = start;
    size_t i = 1;

    // 直到找到空位置停止
    while (_table[index]._state != EMPTY) {
        if (_table[index]._state == EXIST && _table[index]._kv.first == key) {
            return &_table[index];
        }

        index = start + i;
        index %= _table.size();
        ++i;
        // 判断是否重复查找
        if (index == start) {
			return nullptr;
        }
    }
    return nullptr;
}

在上面代码的查找过程中,加了句用于判断是否重复查找的代码。理论上上述代码不会出现所有的位置都有数据,查找不存在的数据陷入死循环的情况,因为哈希表会扩容,闭散列下负载因子不会到 1。

但假如,我们插入了 5 个数据,又删除了它们,之后又插入了 5 个数据,将 10 个初始位置都变为非 EMPTY。此时我们查找的值不存在的话,是会陷入死循环的。

插入

插入的过程稍微复杂一些:

1.首先检查待插入的 key 值是否存在

2.其次需要检查是否需要扩容

3.使用线性探测方式将节点插入

/// @brief 插入节点
/// @param kv 待插入的节点
/// @return 插入成功返回 true,失败返回 false
bool Insert(const pair<K, V>& kv) {
    // 检查是否已经存在
    Elem* res = Find(kv.first);
    if (res != nullptr) {
        return false;
    }

    // 看是否需要扩容
    if (_table.empty()) {
        _table.resize(10);
    } else if (_n > 0.7 * _table.size()) {	// 变化一下负载因子计算,可以避免使用除法
        HashTable backUp;
        backUp._table.resize(2 * _table.size());
        for (auto& [k, s] : _table) {
            // C++ 17 的结构化绑定
            // k 绑定 _kv,s 绑定 _state
            if (s == EXIST) {
                backUp.Insert(k);
            }
        }
        // 交换这两个哈希表,现代写法
        _table.swap(backUp._table);
    }

    // 将数据插入
    size_t start = kv.first % _table.size();
    size_t index = start;
    size_t i = 1;

    // 找一个可以插入的位置
    while (_table[index]._state == EXIST) {
        index = start + i;
        index %= _table.size();
        ++i;
    }
    _table[index]._kv = kv;
    _table[index]._state = EXIST;
    ++_n;
    return true;
}

删除

删除的过程非常简单:

1.查找指定 key

2.找到了就将其状态设为 DELETE,并减少表中元素个数

/// @brief 删除指定 key 值
/// @param key 待删除节点的 key
/// @return 删除成功返回 true,失败返回 false
bool Erase(const K& key) {
    Elem* res = Find(key);
    if (res != nullptr) {
        res->_state = DELETE;
        --_n;
        return true;
    }
    return false;
}

开散列

接口总览

template <class K, class V>
class HashTable {
	struct Elem {
		Elem(const pair<K, V>& kv)
			: _kv(kv)
			, _next(nullptr)
		{}

		pair<K, V> _kv;
		Elem* _next;
	};
public:
	Elem* Find(const K& key);
	bool Insert(const pair<K, V>& kv);
	bool Erase(const K& key);
private:
	vector<Elem*> _table;
	size_t _n = 0;
};

节点的结构

使用链地址法解决哈希冲突就不再需要伪删除了,但需要一个指针,指向相同索引的下一个节点。

/// @brief 哈希表的节点
struct Elem {
    Elem(const pair<K, V>& kv)
        : _kv(kv)
            , _next(nullptr)
        {}

​​​​​​​    pair<K, V> _kv;    // 存储数据
    Elem* _next;    // 存在下一节点地址
};

查找

查找的实现比较简单:

1.利用散列函数获取映射后的索引

2.遍历该索引位置的链表

/// @brief 查找指定 key
/// @param key 待查找节点的 key 值
/// @return 找到返回节点的指针,没找到返回空指针
Elem* Find(const K& key) {
    if (_table.empty()) {
        return nullptr;
    }

    size_t index = key % _table.size();
    Elem* cur = _table[index];
    // 遍历该位置链表
    while (cur != nullptr) {
        if (cur->_kv.first == key) {
            return cur;
        }
        cur = cur->_next;
    }
    return nullptr;
}

插入

开散列下的插入比闭散列简单:

1.首先检查待插入的 key 值是否存在

2.其次需要检查是否需要扩容

3.将新节点以头插方式插入

/// @brief 插入节点
/// @param kv 待插入的节点
/// @return 插入成功返回 true,失败返回 false
bool Insert(const pair<K, V>& kv) {
    // 检查是否已经存在
    Elem* res = Find(kv.first);
    if (res != nullptr) {
        return false;
    }

    // 检查是否需要扩容
    if (_table.size() == _n) {
        vector<Elem*> backUp;
        size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
        backUp.resize(newSize);

        // 遍历原哈希表,将所有节点插入新表
        for (int i = 0; i < _table.size(); ++i) {
            Elem* cur = _table[i];
            while (cur != nullptr) {
                // 取原哈希表的节点放在新表上,不用重新申请节点
                Elem* tmp = cur->_next;
                size_t index = cur->_kv.first % backUp.size();
                cur->_next = backUp[index];
                backUp[index] = cur;
                cur = tmp;
            }
            _table[i] = nullptr;
        }
        _table.swap(backUp);
    }

    // 将新节点以头插的方式插入
    size_t index = kv.first % _table.size();
    Elem* newElem = new Elem(kv);
    newElem->_next = _table[index];
    _table[index] = newElem;
    ++_n;
    return true;
}

删除

开散列的删除与闭散列有些许不同:

1.获取 key 对应的索引

2.遍历该位置链表,找到就删除

/// @brief 删除指定 key 值
/// @param key 待删除节点的 key
/// @return 删除成功返回 true,失败返回 false
bool Erase(const K& key) {
    size_t index = key % _table.size();
    Elem* prev = nullptr;
    Elem* cur = _table[index];
    while (cur != nullptr) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                // 是该位置第一个节点
                _table[index] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            delete cur;	// 释放该节点
            --_n;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

到此这篇关于C++数据结构之哈希表的实现的文章就介绍到这了,更多相关C++哈希表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++ 哈希表的基本用法及说明

    目录 C++ 哈希表基本用法 为什么要用哈希表 遍历 查找 插入 删除 C++ 哈希表基础知识 常见的三种哈希结构 C++ 哈希表基本用法 哈希表是一种很常见的数据结构,我现在平时刷算法题一般使用C++刷(不要问我为什么,懂的都懂).C++关于哈希表有很多数据结构,平时使用的比较多的有unordered_set 跟 unordered_map.其中unordered_map 存储的是键值对. 其实我们在某些情况下可以使用数组构建哈希表(具体是哪些情况的呢,自行搜索).但是数组的大小是受限制的,而

  • C++ 实现哈希表的实例

    C++ 实现哈希表的实例 该散列表的散列函数采用了除法散列函数.乘法散列函数.全域散列函数,每一个槽都是使用有序单向链表实现. 实现代码: LinkNode.h #include<iostream> using namespace std; class Link; class LinkNode { private: int key; LinkNode* next; friend Link; public: LinkNode():key(-1),next(NULL){} LinkNode(int

  • C++数据结构哈希表详解

    目录 实现 散列函数 开散列方法 闭散列方法(开地址方法) 删除* 实现 哈希表,即散列表,可以快速地存储和查询记录.理想哈希表的存储和查询时间都是 O(1). 本<资料>中哈希表分以下几部分:散列函数.存储和查找时的元素定位.存储.查找.删除操作因为不常用,所以只给出思想,不给出代码. 根据实际情况,可选择不同的散列方法. 以下代码假设哈希表不会溢出. // N表示哈希表长度,是一个素数,M表示额外空间的大小,empty代表"没有元素". const int N=9997

  • C++中的数组、链表与哈希表

    目录 数组和链表 数组 链表 什么是链表? 链表的操作 双向链表(list) list的成员函数 哈希表 什么是哈希表? 哈希碰撞 哈希表应用场景 构建哈希表 哈希表基本使用 Leetcode对应题目 前缀和 差分数组 滑动窗口 二分查找 数组和链表 C++的数组和链表分别是什么?分别有什么种类?它们都有什么特性?针对这些特征,使用情形是什么? 数组 什么是数组? 一个数组就像是一个变量,它可以存储一组值,但是所有值都是相同的数据类型. 一个int数组定义:int hours [6] 该数组类型

  • Java深入了解数据结构之哈希表篇

    目录 1,概念 2,冲突-避免 3,冲突-避免-哈希函数设计 4,冲突-避免-负载因子调节 5,冲突-解决-闭散列 ①线性探测 ②二次探测 6,冲突-解决-开散列/哈希桶 7,完整代码 1,概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键 码的多次比较.顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( ),搜索的效率取决于搜索过程中 元素的比较次数. 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素. 如果构造一

  • C++数据结构之哈希表的实现

    目录 哈希表概念 散列函数 直接定址法 除留余数法 平方取中法 哈希冲突 线性探测 二次探测 链地址法 哈希表的实现 闭散列 开散列 哈希表概念 二叉搜索树具有对数时间的表现,但这样的表现建立在一个假设上:输入的数据有足够的随机性.哈希表又名散列表,在插入.删除.搜索等操作上具有「常数平均时间」的表现,而且这种表现是以统计为基础,不需依赖输入元素的随机性. 听起来似乎不可能,倒也不是,例如: 假设所有元素都是 8-bits 的正整数,范围 0~255,那么简单得使用一个数组就可以满足上述要求.首

  • java数据结构和算法中哈希表知识点详解

    树的结构说得差不多了,现在我们来说说一种数据结构叫做哈希表(hash table),哈希表有是干什么用的呢?我们知道树的操作的时间复杂度通常为O(logN),那有没有更快的数据结构?当然有,那就是哈希表: 1.哈希表简介 哈希表(hash table)是一种数据结构,提供很快速的插入和查找操作(有的时候甚至删除操作也是),时间复杂度为O(1),对比时间复杂度就可以知道哈希表比树的效率快得多,并且哈希表的实现也相对容易,然而没有任何一种数据结构是完美的,哈希表也是:哈希表最大的缺陷就是基于数组,因

  • php内核解析:PHP中的哈希表

    PHP中使用最为频繁的数据类型非字符串和数组莫属,PHP比较容易上手也得益于非常灵活的数组类型. 在开始详细介绍这些数据类型之前有必要介绍一下哈希表(HashTable). 哈希表是PHP实现中尤为关键的数据结构. 哈希表在实践中使用的非常广泛,例如编译器通常会维护的一个符号表来保存标记,很多高级语言中也显式的支持哈希表. 哈希表通常提供查找(Search),插入(Insert),删除(Delete)等操作,这些操作在最坏的情况下和链表的性能一样为O(n). 不过通常并不会这么坏,合理设计的哈希

  • 简单讲解哈希表

    目录 一.哈希表的概念 1.查找算法 2.哈希表 3.哈希数组 4.关键字 5.哈希函数 6.哈希冲突 7.哈希地址 二.常用哈希函数 1.直接定址法 2.平方取中法 3.折叠法 4.除留余数法 5.位与法 三.常见哈希冲突解决方案 1.开放定址法 1)原理讲解 2)动画演示 2.再散列函数法 1)原理讲解 2)动画演示 3.链地址法 1)原理讲解 2)动画演示 4.公共溢出区法 1)原理讲解 2)动画演示 四.哈希表的实现 1.数据结构定义 2.哈希表初始化 3.哈希函数计算 4.哈希表查找

  • Java数据结构之实现哈希表的分离链接法

    哈希表的分离链接法 原理 Hash Table可以看作是一种特殊的数组.他的原理基本上跟数组相同,给他一个数据,经过自己设置的哈希函数变换得到一个位置,并在这个位置当中放置该数据.哦对了,他还有个名字叫散列 0 1 数据1 数据2 就像这个数组,0号位置放着数据1,1号位置放数据2 而我们的哈希表则是通过一个函数f(x) 把数据1变成0,把数据2变成1,然后在得到位置插入数据1和数据2. 非常重要的是哈希表的长度为素数最好!! 而且当插入数据大于一半的时候我们要进行扩充!!! 冲突问题产生 现在

  • C语言数据结构哈希表详解

    /* * 程序名:hash.c,此程序演示哈希表的实现,数据元素单链表带头结点. * */ #include <stdio.h> #include <stdlib.h> #include <string.h> // 哈希表中数据元素的结构体. typedef struct Element { unsigned int key; // 关键字. int value; // 数据元素其它数据项,可以是任意数据类型. // char value[1001]; // 数据元素其

  • TypeScript 基础数据结构哈希表 HashTable教程

    目录 前言 1. 哈希表介绍和特性 2. 哈希表的一些概念 3. 地址冲突解决方案 3.1 方案一:链地址法 3.2 方案二:开放地址法 4. 哈希函数代码实现 5. 哈希表封装 5.1 整体框架 v1 版 5.2 添加 put 方法 v2 版 5.3 添加 get 方法 v3 版 5.4 添加 delete 方法 v4 版 6. 哈希表的自动扩容 前言 哈希表是一种 非常重要的数据结构,几乎所有的编程语言都有 直接或者间接 的应用这种数据结构. 很多学习编程的人一直搞不懂哈希表到底是如何实现的

  • Redis之常用数据结构哈希表

    目录 1.哈希冲突 2.链式哈希 3.rehash 4.渐进式 rehash 5.rehash 触发条件 哈希表是一种保存键值对(key-value)的数据结构 哈希表优点在于,它能以 O(1) 的复杂度快速查询数据. 怎么做到的呢? 将 key 通过 Hash 函数的计算,就能定位数据在表中的位置,因为哈希表实际上是数组,所以可以通过索引值快速查询到数据. 在哈希表大小固定的情况下,随着数据不断增多,那么哈希冲突的可能性也会越高. Redis 采用了**「链式哈希」**来解决哈希冲突,在不扩容

随机推荐