HashTable

一般常用的unordered_set、unordered_map都是基于哈希表实现的，哈希表主要需要注意的是哈希冲突，迭代器等

基础

哈希映射

使用哈希函数将键映射到索引的数据结构。
即将原始数组索引通过哈希函数映射到一个哈希值上，从而将一个大范围索引，减小到一个小的固定范围

哈希冲突

由于是大范围变为小范围所以显然映射并不是一对一的，所以对于哈希值为相同索引的多个不同键的存储通常使用链式存储方法，即对于哈希表中的一个索引位置，其存放的是一个链式结构，其中每个元素为不同的键

哈希表的扩容

如果键值数量不变，随着索引的数量增加链表会变得越来越长导致效率降低，所以此时需要扩容。
需要重新计算所有的哈希值，然后分配到更大的哈希表中

性能优化

二次哈希函数、空间配置器、内存池等

并发性和多线程安全性

简单实现

实现插入、删除、查找、打印功能

成员变量

哈希表节点

class HashNode
{
  public:
    Key key;
    Value value;
    explicit HashNode(const Key& key):key(key),value(){}
    HashNode(const Key &key, const Value &value) : key(key), value(value) {}
    bool operator==(const HashNode &other) const { return key == other.key; }
    bool operator!=(const HashNode &other) const { return key != other.key; }
    bool operator<(const HashNode &other) const { return key < other.key; }
    bool operator>(const HashNode &other) const { return key > other.key; }
    bool operator==(const Key &key_) const { return key == key_; }
    void print() const 
    {
       std::cout << key << " "<< value << " ";
    }
};

其余成员变量

//每个节点对于的链表结构
using Bucket = std::list<HashNode>;
//一个数组用来存储所有数组
vector<Bucket> buckets;
Hash HashFunction;
//哈希表的大小
size_t tablesize;
//哈希表中元素的数量
size_t numElements;
//负载因子
float maxLoadFactor = 0.75f;
//哈希函数
size_t hash(const Key& key) const {return HashFunction(key)%tablesize;}
//重新分配哈希值
void rehash(size_t newSize)
{
  std::vector<Bucket> newBuckets(newSize);
  for(Bucket& bucket:buckets)
  {
    for(HashNode& hashnode : bucket)
    {
      size_t newIndex = (hashnode.key)%newSize;
      newBuckets[newIndex].push_back(hashnode);
    }
  }
  buckets = std::move(newBuckets);
  tablesize = newSize;
}

构造函数

需要传入哈希表大小，和哈希函数等

HashTable(size_t size = 10, const Hash &hashFunc = Hash())
: buckets(size), hashFunction(hashFunc), tableSize(size), numElements(0) 
{}

插入

首先考虑是否需要rehash，接着计算插入的key对应的桶的index，然后判断当前key是否已经存在桶里

void insert(const Key& key,const Value& value)
{
  if((numElements+1) > maxLoadFactor*tablesize)
  {
    if(tablesize == 0) tablesize += 1;
    rehash(tablesize*2);
  }
  size_t index = hash(key);
  //获取对应桶
  std::list<HashNode>& bucket = buckets[index];
  //判断是否已经存在
  if(std::find(bucket.begin(),bucket.end(),key) == bucket.end())
  {
    bucket.push_back(HashNode(key,value));
    numElements++; 
  }
}

移除某个键

当寻找到了某个键利用erase从桶里面删除掉

void erase(const Key &key) 
{
    size_t index = hash(key);  
    auto &bucket = buckets[index];
    auto it = std::find(bucket.begin(), bucket.end(), key); 
    if (it != bucket.end()) 
    {                               
      bucket.erase(it); 
      numElements--; 
    }
}

查找键是否存在于哈希表中

Value* find(const Key &key) 
{
    size_t index = hash(key);  
    auto &bucket = buckets[index];
    auto it = std::find(bucket.begin(), bucket.end(), key); 
    if (it != bucket.end()) 
    {                               
      return &it->value;
    }
    return nullptr;
}

总结

哈希表的工作原理

哈希表通过哈希函数实现快速插入和搜索。通过哈希函数将键映射到表中的索引位置存储键值对，为了解决不同键映射到了同一索引的哈希冲突，一般采用链表或者开放地址

哈希冲突的解决

一般有三种方法

1. 链表法：每个哈希表索引维护一个链表，映射到该索引的键值对将加入到对应链表中
2. 开放寻址法：发送冲突，寻找下一个空闲的索引
3. 双重哈希

哈希函数的选择

应该满足以下条件

1. 快速加速
2. 哈希值分布均匀
3. 一致性
4. 不同的键因尽可能对应不同的索引

负载因子

已存储元素数量与哈希表中总位置数量的最大比率。衡量哈希表满程度的指标
当负载因子过大时，更容易造成哈希冲突，因为一般当比率超过负载因子时，哈希表会进行扩容来增加存储位置，从而减少冲突和维护操作的效率

rehash

rehash发生在比率超过负载因子时，会进行新的索引哈希值，然后将原有的键值对移动到新创建的哈希表中。

插入、删除、查找的时间复杂度

如果没有冲突，那么都是\(O(1)\)
最坏的情况，即所有键都对应到一个索引那么就是\(O(n)\)

扩容

创建一个更大的哈希表：即将tablesize扩大，然后计算新的哈希值，逐个move键值对

线程安全

1. 互斥锁：线程访问哈希表时，需要先获取锁
2. 读写锁：适用于读操作多于写操作的情况，读数据时可以多个线程访问，但访问时只能有1个线程
3. 原子操作
4. 细粒度锁：对哈希表中的一个list或者一个桶加锁

实现问题

1. 内存使用不当：哈希表过大造成空桶过多
2. 冲突处理不佳
3. 哈希函数选择不当：不同键值对对应同一个索引
4. 扩容代价过高