数据结构 - 哈希表

2020-10-03  本文已影响0人  Whyn

简介

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

对于数组和链表等数据结构的查找，都是通过对各个结点进行比对判断，而哈希表的底层数据结构虽然是数组，但是它却另辟蹊径，通过对键进行一个映射（哈希函数），从而可以直接找到对应值的索引位置，然后借助数组数据获取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函数的构造方法

哈希表冲突解决方法

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

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

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

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

总结

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

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

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

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

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

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

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

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

参考

上一篇 下一篇

猜你喜欢

热点阅读