数据结构--哈希表

哈希表的定义

哈希表（Hash table，也叫散列表），是根据关键码值(Key, value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
简单来描述就是：
记录的存储位置=H(关键字)
这里的对应关系H称为散列函数，又称为哈希（Hash函数），采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。
哈希函数的定义：
把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。理想的哈希函数对于不同的输入应该产生不同的结构，同时散列结果应当具有同一性（输出值尽量均匀）和雪崩效应（微小的输入值变化使得输出值发生巨大的变化）。

哈希表的数据结构

数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。
数组的存储区间是连续的，它的特点是：寻址容易，插入和删除困难；
链表的存储区间离散，占用内存比较宽松，它的特点是：寻址困难，插入和删除容易。
哈希表综合了两者的特性，做出了一种寻址容易，插入删除也容易的数据结构。哈希表有多种不同的实现方法，拉链法是最常用的一种方法，可以理解为“链表的数组”。
需要注意的是，哈希表不一定是数组+链表的组合，这只是哈希表的一种实现而已。

哈希表的优缺点

优点

不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即O(1)的时间级。而且哈希表不仅速度快，编程实现也相对容易。

缺点

哈希表是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

哈希函数的构造方法

哈希函数的构造方法

常用：除留余数法：
最直观的一种，上图使用的就是这种散列法，公式：
H（key）=key MOD p （p<=m m为表长）
很明显，如何选取p是个关键问题。

哈希冲突

哈希冲突即不同key值产生相同的地址，H（key1）=H（key2）；
比如我们要存储3 6 9，p取3时3 MOD 3 == 6 MOD 3 == 9 MOD 3 此时3 6 9都发生了hash冲突。

哈希冲突的解决办法

开放定址法

Hash冲突之开放地址法

即当一个关键字和另一个关键字发生冲突时，使用某种探测技术在Hash表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入其中。比较常用的探测方法有线性探测法、平方探测法、再次哈希法（双散列）等。
比如线性探测法就是有一组关键字{12，13，25，23，38，34，6，84，91}，Hash表长为14，Hash函数为address(key)=key%11，当插入12，13，25时可以直接插入，而当插入23时，地址1被占用了，因此沿着地址1依次往下探测（探测步长可以根据情况而定），直到探测到地址4，发现为空，则将23插入其中。

链地址法

神速Hash

采用数组和链表相结合的办法，将Hash地址相同的记录存储在一张线性表中，而每张表的表头的序号即为计算得到的Hash地址。如上述例子中，采用链地址法形成的Hash表存储表示为：

公共溢出区法

建立一个特殊存储空间，专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。

再散列法

准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个……

哈希表的平均查找长度

Hash表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度。
查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数；查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数，可以理解为向表中插入某个元素，该元素在每个位置都有可能，然后计算出在每个位置能够插入时需要比较的次数，再除以表长即为查找不成功时的平均查找长度。

哈希表应用

海量数据处理

算法：海量日志数据，提取出某日访问百度次数最多的那个IP

哈希表的C++实现

c++ 实现hashmap

//哈希表简单实现，使用链地址法解决冲突
#include <string>

//哈希表节点
template <typename key_type, typename value_type>
class HashNode {
public:
    key_type key_;
    value_type value_;
    HashNode *next_;

    HashNode(key_type key, value_type value) {
        key_ = key;
        value_ = value;
        next_ = nullptr;
    }
    ~HashNode() {}

    //=运算符重载（以下的实现中未用到）
    HashNode& operator=(const HashNode& node) {
        key_ = node.key;
        value_ = node.value;
        next_ = node.next;
        return *this;  //返回当前对象本身（若返回类型为HashNode， 则是克隆， 若返回类型为HashNode&， 则是本身，return this返回当前对象的地址）
    }
};

template <typename key_type, typename value_type, typename HashFunc>
class HashTable {
public:
    HashTable(int size);
    ~HashTable();
    bool insert(const key_type& key, const value_type& value);
    bool del(const key_type& key);
    value_type& find(const key_type& key);
    value_type& operator[](const key_type& key);
private:
    HashFunc hash;
    HashNode<key_type, value_type> **table;  //存放散列单元数据的二维数组
    unsigned int size_;  //表的长度
    value_type value_null;
};

//构造函数，初始化
template <typename key_type, typename value_type, typename HashFunc>
HashTable<key_type, value_type, HashFunc>::HashTable(int size) : size_(size) {
    hash = HashFunc();
    table = new HashNode<key_type, value_type> *[size_];  //动态申请size_行的二维数组
    for (int i = 0; i < size_; i++) table[i] = nullptr;
    value_null = NULL;
}

//析构函数，释放资源
template<typename key_type, typename value_type, typename HashFunc>
HashTable<key_type, value_type, HashFunc>::~HashTable() {
    for (int i = 0; i < size_; i++) {  //逐个释放节点
        HashNode<key_type, value_type> *cur_node = table[i];
        while (cur_node) {
            HashNode<key_type, value_type> *temp = cur_node;
            cur_node = cur_node->next_;
            delete temp;
            temp = nullptr;
        }
    }
    delete table;
    table = nullptr;
}

//插入
template<typename key_type, typename value_type, typename HashFunc>
bool HashTable<key_type, value_type, HashFunc>::insert(const key_type &key, const value_type &value) {
    value_type &temp = find(key);
    if (temp != value_null) {  //key已经存在，更新
        temp = value;
    }
    else {
        int index = hash(key) % size_;  //计算哈希节点在哈希表中的位置
        HashNode<key_type, value_type> *node = new HashNode<key_type, value_type>(key, value);
        node->next_ = table[index];  //将该哈希节点插入此链表的头节点位置
        table[index] = node;
    }
    return true;
}

//删除
template<typename key_type, typename value_type, typename HashFunc>
bool HashTable<key_type, value_type, HashFunc>::del(const key_type& key) {
    int index = hash(key) % size_;  //计算哈希节点在哈希表中的位置
    HashNode<key_type, value_type> *node = table[index];
    HashNode<key_type, value_type> *pre = nullptr;
    while (node) {
        if (node->key_ == key) {
            if (!pre) table[index] = node->next_;  //pre == nullptr，删除的是链表的头节点
            else pre->next_ = node->next_;  //删除的是中间节点
            delete node;
            node = nullptr;
            return true;
        }
        pre = node;
        node = node->next_;
    }
    return false;  //对应的key未找到
}

//查找
template<typename key_type, typename value_type, typename HashFunc>
value_type& HashTable<key_type, value_type, HashFunc>::find(const key_type& key) {
    int index = hash(key) % size_;  //计算哈希节点在哈希表中的位置
    if (table[index]) {  //table[index] != nullptr
        HashNode<key_type, value_type> *node = table[index];
        while (node) {
            if (node->key_ == key) {
                return node->value_;
            }
            node = node->next_;
        }
    }
    return value_null;
}

//"[]"运算符重载，元素不存在时插入新值
template<typename key_type, typename value_type, typename HashFunc>
value_type& HashTable<key_type, value_type, HashFunc>::operator[](const key_type& key) {
    value_type &value = find(key);
    if (value == value_null) {  //元素不存在时插入新值
        int index = hash(key) % size_;  //计算哈希节点在哈希表中的位置
        HashNode<key_type, value_type> *node = new HashNode<key_type, value_type>(key, value);
        node->next_ = table[index];  //将该哈希节点插入此链表的头节点位置
        table[index] = node;
        return node->value_;
    }
    return value;
}

//定义hash函数，<<8代表取string最后四个字符的ASCII值，为了减弱规律性，使用<<7
class HashFunc {
public:
    int operator()(const std::string &key) {
        int hash = 0;
        for (int i = 0; i < key.length(); ++i) {
            hash = hash << 7 ^ key[i];
        }
        return (hash & 0x7FFFFFFF);
    }
};

参考链接：
小朋友学数据结构：哈希表
哈希表（散列表）原理详解
数据结构 Hash表（哈希表）
HashMap实现原理分析