【数据结构】哈希表

一、散列表/哈希表定义

       使关键字和其存储位置满足关系：存储位置 = f（关键字），这就是一种新的存储技术——散列技术。

       散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，使得每一个关键字key对应一个存储位置f（key），在查找时，根据这个确定的对应关系找到给定的key的映射f（key），如果待查找集合中存在这个记录，则必定在f（key）的位置上。

       我们把这种对应关系f称为散列函数，又称为哈希函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或者哈希表（Hash Table）。

优势：适用于快速的查找，时间复杂度为O(1)。100M的整数，如果使用哈希表进行存储，所需要的内存大小是200M，10亿整数的内存大小为：4G * 2 = 8G。

缺点：占用内存空间比较大。引用吴军博士的《数学之美》中所言，哈希表的空间效率还是不够高。如果用哈希表存储一亿个垃圾邮件地址，每一个email地址对应 8bytes，而哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用 16bytes。因此一亿个 email 地址占用 1.6GB，如果存储几十亿个 email address，则需要上百GB的内存。除非是超级计算机，一般的服务器是无法存储的。100M * 16 = 1.6G内存，是空间换时间的策略。

二、散列函数

设计特点：

• 计算简单（复杂会降低查找的时间）
• 散列地址分布均匀（减少哈希冲突）

散列函数（哈希函数）：

• 直接定址法：取关键字或者关键字的某一个线性函数值为散列地址。例如：f（key）= a * key + b（a, b 为常数）
• 数字分析法：使用 key 的一部分来计算散列码（包括为了减少哈希冲突而进行位移操作、数字叠加操作等）
• 平方取中法：取关键字 key 的平方后的中间部分数字作用散列地址
• 折叠法&&随机数法：
• 除留余数法：f（key）= key mod p，不仅可以对关键字直接取模，也可以折叠、平方取中法等运算之后取模，p的取值很重要，一般取素数，否则冲突的概率会比较大
• md5/sha加密hash算法等

三、线性哈希的代码实现

3.1 线性哈希的思想

       我们是使用线性数组来进行存储数组的，我们需要实现加入关键字，删除关键字，查找关键字、扩容的功能，下面我们来看一看每一个操作的思想：

       当加入数据的时候，我们需要先进行哈希函数计算关键字应该在的位置，然后在数组中进行查看这个位置中有没有元素，如果有元素，需要在其后面遍历，直到有一个空位为止，将关键字放入到这个空位中。

       当删除数据的时候，我们需要先进行哈希函数计算关键字应该在的位置，然后在数组中相应位置中进行查看是否是要删除的数据，如果不是要删除的数据，我们需要进行遍历数组进行查找是否有这个数据，但是我们不需要一直遍历，当我们遍历到这个位置重来没有数据使用过的时候停止。这时，需要将数组中的每一个数据定义一个状态，表示现在这个位置的数据是出于什么状态，状态有：正在使用状态，未使用状态，已经删除状态。

       当查询数据的时候，我们需要先进行哈希函数计算关键字应该在的位置，然后在数组中相应位置中进行查看是不是我们要查找的数据，如果不是，我们需要向后进行遍历，和删除数据的时候一样，不对，应该是删除数据和查找数据是一样的。

       我们还需要进行数组的扩容，哈希表中有负载因子，当负载因子大于规定的负载因子时，我们需要将数组进行扩容，扩容的时候，我们需要根据素数表进行扩容。

3.2 线性哈希的实现

定义桶的状态：

enum State
{STATE_UNUSE,// 从未使用的桶STATE_USING,// 正在使用的桶STATE_DEL   // 元素被删除了的桶
}

定义桶的类型： 当时是想设计为泛型，但是想一想，我们需要根据 key 来进行计算出每一个关键字所在的位置，如果是其他类型，我们应该怎么进行计算呢？？就不能光使用除留余数法，我们需要重新设计一个哈希函数。

struct Bucket
{int m_key; // 存储的数据State m_state; // 桶的当前状态Bucket(int key = 0, State state = STATE_UNUSE): m_key(key), m_state(state){}
}

定义哈希表的变量：

class HashTable
{
private:Bucket* table_;    // 指向动态开辟的哈希表int tableSize_;    // 哈希表当前的长度int useBucketNum_; // 已经使用的桶的个数double loadFactor_;// 哈希表的装载因子static const int PRIME_SIZE = 10; // 素数表的大小static int primes_[PRIME_SIZE];   // 素数表int primeIdx_; // 当前使用的素数下标
}

哈希表的构造函数：

public:HashTable(int size = primes_[0], double loadFactor = 0.75): useBucketNum_(0), loadFactor_(loadFactor), primeIdx_(0){// 把用户传入的size调整到最近的比较大的素数上if (size != primes_[0]){for (; primeIdx_ < PRIME_SIZE; primeIdx_++){if (primes_[primeIdx_] >= size)break;}// 用户传入的size值过大，已经超过最后一个素数，调整到最后一个素数if (primeIdx_ == PRIME_SIZE){primeIdx_--;}}tableSize_ = primes_[primeIdx_];table_ = new Bucket[tableSize_];}

哈希表的析构函数：

public:~HashTable(){delete[]table_;table_ = nullptr;}

哈希表的插入、删除、查询函数：

public:// 插入元素bool insert(int key){// 考虑扩容double factor = useBucketNum_*1.0 / tableSize_;cout << "factor:" << factor << endl;if (factor > loadFactor_){// 哈希表开始扩容expand();}int idx = key % tableSize_;int i = idx;do{if (table_[i].state_ != STATE_USING){table_[i].state_ = STATE_USING;table_[i].key_ = key;useBucketNum_++;return true; // O(1)}i = (i + 1) % tableSize_;} while (i != idx); // O(n)return false;}// 删除元素bool erase(int key){int idx = key % tableSize_;int i = idx;do{if (table_[i].state_ == STATE_USING && table_[i].key_ == key){table_[i].state_ = STATE_DEL;useBucketNum_--;}i = (i + 1) % tableSize_;} while (table_[i].state_ != STATE_UNUSE && i != idx);return true;}// 查询  count(key)bool find(int key){int idx = key % tableSize_;int i = idx;do{if (table_[i].state_ == STATE_USING && table_[i].key_ == key){return true;}i = (i + 1) % tableSize_;} while (table_[i].state_ != STATE_UNUSE && i != idx);return false;}private:// 扩容操作void expand(){++primeIdx_;if (primeIdx_ == PRIME_SIZE){throw "HashTable is too large, can not expand anymore!";}Bucket* newTable = new Bucket[primes_[primeIdx_]];for (int i = 0; i < tableSize_; i++){if (table_[i].state_ == STATE_USING) // 旧表有效的数据，重新哈希放到扩容后的新表{int idx = table_[i].key_ % primes_[primeIdx_];int k = idx;do{if (newTable[k].state_ != STATE_USING){newTable[k].state_ = STATE_USING;newTable[k].key_ = table_[i].key_;break;}k = (k + 1) % primes_[primeIdx_];} while (k != idx);}}delete[]table_;table_ = newTable;tableSize_ = primes_[primeIdx_];}

四、链式哈希的代码实现

代码实现：

// 链式哈希表
class HashTable
{
public:HashTable(int size = primes_[0], double loadFactor = 0.75): useBucketNum_(0), loadFactor_(loadFactor), primeIdx_(0){if (size != primes_[0]){for (; primeIdx_ < PRIME_SIZE; primeIdx_++){if (primes_[primeIdx_] >= size)break;}if (primeIdx_ == PRIME_SIZE){primeIdx_--;}}table_.resize(primes_[primeIdx_]);}public:// 增加元素 不能重复插入keyvoid insert(int key){// 判断扩容double factor = useBucketNum_ * 1.0 / table_.size();cout << "factor:" << factor << endl;if (factor > loadFactor_){expand();}int idx = key % table_.size();  // O(1)if (table_[idx].empty()){useBucketNum_++;table_[idx].emplace_front(key);}else{// 使用全局的::find泛型算法，而不是调用自己的成员方法findauto it = ::find(table_[idx].begin(), table_[idx].end(), key);  // O(n)if (it == table_[idx].end()){// key不存在table_[idx].emplace_front(key);}}}// 删除元素void erase(int key){int idx = key % table_.size();  // O(1)// 如果链表节点过长：如果散列结果比较集中（散列函数有问题！！！）//                 如果散列结果比较离散，链表长度一般不会过程，因为有装载因子auto it = ::find(table_[idx].begin(), table_[idx].end(), key); // O(n)if (it != table_[idx].end()){table_[idx].erase(it);if (table_[idx].empty()){useBucketNum_--;}}}// 搜索元素bool find(int key){int idx = key % table_.size();  // O(1)auto it = ::find(table_[idx].begin(), table_[idx].end(), key); // return it != table_[idx].end();}private:// 扩容函数void expand(){if (primeIdx_ + 1 == PRIME_SIZE){throw "hashtable can not expand anymore!";}primeIdx_++;useBucketNum_ = 0;vector<list<int>> oldTable;// swap会不会效率很低？？？ 交换了两个容器的成员变量table_.swap(oldTable);table_.resize(primes_[primeIdx_]);for (auto list : oldTable){for (auto key : list){int idx = key % table_.size();if (table_[idx].empty()){useBucketNum_++;}table_[idx].emplace_front(key);}}}private:vector<list<int>> table_; // 哈希表的数据结构int useBucketNum_;        // 记录桶的个数double loadFactor_;       // 记录哈希表装载因子static const int PRIME_SIZE = 10; // 素数表的大小static int primes_[PRIME_SIZE];   // 素数表int primeIdx_; // 当前使用的素数下标
};