哈希表（hash table），又成散列表，它通过建立key与value之间的映射关系，实现高效($O(1)$ )元素查询。

image-20260709105652410

哈希表常用操作

image-20260709105905248

unordered_map<int, string> map;

map[12836] = "小哈";
map[10583] = "小鸭";

string name = map[12836];
map.erase(10583);

for (auto kv: map) {
  cout << kv.first << " -> " << kv.second << endl;
}

for (auto iter = map.begin; iter != map.end(); ++iter) {
  cout << iter->first << " -> " << iter->second << endl;
}

哈希表的实现

哈希表的工作原理是输入一个key，通过哈希函数查询索引并得到value。

image-20260709112329326

struct Pair {
public:
  int key;
  string val;
  Pair(int key, string val) {
    this->key = key;
    this->val = val;
  }
};

class ArrayHashMap {
private:
  vector<Pair*> buckets;
public:
  ArrayHashMap() {
		buckets = vector<Pair*>(100); 
  }
  
  ~ArrayHashMap() {
    for (const auto& bucket : buckets) {
      delete bucket;
    }
    
    buckets.clear();
  }
  
  int hashFunc(int key) {
    int index = key% 100;
    return index;
  }
  
  string get(int key) {
    int index = hashFunc(key);
    Pair* pair = buckets[index];
    if (pair == nullptr) {
      return "";
    }
    return pair->val;
  }
  
  void put(int key, string val) {
    Pair* pair = new Pair(key, val);  
    int index = hashFunc(key);
    buckets[index] = pair;
  }
  
  void remove(int key) {
    int index = hashFunc(key);
    delete buckets[index];
    buckets[index] = nullptr;
  }
  
  // 获取所有健值对
  vector<Pair*> pairSet() {
    vector<Pair*> pairSet;
    for (Pair* pair : buckets) {
      if (pair != nullptr) {
        pairSet.push_back(pair);
      }
    }
    
    return pairSet;
  }
  
  void print() P
    for (Pair* kv : pairSet()) {
      cout << kv->key << "->" << kv->val << endl;
    }
}

哈希冲突

哈希函数的作用是将key所属的较大的输入空间映射到较小的索引所在空间。当输入空间大于输出空间时，会存在多个输入对应相同输出的情况。

image-20260709142459097

扩容

解决哈希冲突的最简单方式是扩容。

image-20260709142547544

但由于哈希表容量capacity变化时需要重新计算健值对的存储位置，因此需要将所有健值迁移到新哈希表，非常耗时。为了避免频繁扩容，引入了负载因子(load factor) 的概念。它的定义是哈希表的元素除以桶数量，以衡量哈希表的严重程度。

链式地址（separate chaining）

将单个元素转换为链表，将健值对作为链表节点，所有冲突的健值存储在同一个链表中。

image-20260709142938447

基于链式地址实现的哈希表的操作会发生变化。

  • 查询：得到桶索引后会遍历链表并对比key。
  • 添加：通过哈希函数访问链表头节点，随后添加到链表中。（一般使用头插，因为最新插入的数据可能被最近访问）
  • 删除：得到桶索引后便利链表删除指定节点。

链式地址也存在一些局限性：

  • 占用空间增大（链表包含节点指针）
  • 查询效率降低（需要遍历链表）
class HashMapChaining {
private:
  int size;
  int capacity;
  double loadThres; // 触发扩容的负载因子阈值
  int extendRatio;   // 扩容倍数
  vector<vector<Pair*>> buckets;
public:
  HashMapChaining(): size(0), capacity(4), loadThres(2.0/ 3.0), extendRatio(2) {
    buckets.resize(capacity);
  }
  
  ~HashMapChaining() {
    for (auto& bucket : buckets) {
      for (Pair* pair : bucket) {
        delete pair;
      }
    }
  }
  
  int hashFunc(int key) {
    return key % capacity;
  }
  
  double loadFactor() {
    return (double)size / (double)capacity;
  }
  
  string get(int key) {
    int index = hashFunc(key);
    for (Pair* pair : buckets[index]) {
      if (pair->key == key) {
        return pair->val;
      }
    }
    
    return "";
  }
  
  void put(int key, string val) {
    if (loadFactor() > loadThres) {
      extend();
    }
    
    int index = hashFunc(key);
    for (Pair* pair : buckets[index]) {
      if (pair->key == key) {
        pair->val = val;
        return;
      }
    }
    
    buckets[index].push_back(new Pair(key, val));
    ++size;
  }
  
  void remove(int key) {
    int index = hashFunc(key);
    auto& bucket = buckets[index];
    for (int i = 0; i < bucket.size(); ++i) {
      if (bucket[i]->key == key) {
        Pair* tmp = bucket[i];
        bucket.erease(bucket.begin() + i);
        delete tmp;
        --size;
        return;
      }
    }
  }
  
  void extend() {
    vector<vector<Pair*>> bucketsTmp = buckets;
    capacity *= extendRatio;
    
    buckets.clear();
    buckets.resize(capactiy);
    size = 0;
    
    for (auto& bucket : bucketsTmp) {
      for (Pair* pair : bucket) {
        put(pair->key, pair->val);
        delete pair;
      }
    }
  }
  
  void print() {
    for (auto& bucket: buckets) {
      cout << "[";
      for (Pair* pair : bucket) {
        cout << pair->key << " -> " << pair->val << ",";
      }
      
      cout << "]\n";
    }
  }
}

当链表很长时，可以将链表转换为AVL树或红黑树，从而将查询操作时间复杂度优化为 $O(\log n)$。

开放寻址(open addressing)

开放寻址法无需引入额外的数据结构，而是通过“多次探测”来处理哈希冲突。

探测主要包括线性探测、平方探测、多次哈希等。

线性探测

image-20260709155210730

线性探测采用固定步长的线性搜索来进行探测。

  • 插入元素：通过哈希函数计算索引后，如果发现桶内已有元素，则向后线性便利，直到找到空桶，将元素插入其中。

  • 查找元素：如果发现哈希冲突，则使用相同步长向后线性便利，直到找到对应元素；如果遇到空桶，则说明目标元素不在哈希表中。

  • 删除操作：为了避免删除导致查找元素操作错误判断空桶，需要配合线性偏移或者懒删除标记来实现删除操作。

    [!NOTE]

    懒删除会利用TOMBSTONE来标记冲突的桶，在该机制下，None 和 TOMBSTONE都代表空桶，都可以放置健值对，但TOMBSTONE在查找时不会被判定为空桶。

    虽然避免了删除过程中的线性偏移，在这种机制下，懒删除会加速哈希表的性能退化。每次删除操作都会产生一个删除标记，这会导致删除标记越来越多。

线性探测的局限性：

  • 聚集现象：数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大。
  • 无法直接删除元素：因为查找依赖空桶作为判断是否存在对应元素的依据，因此删除操作需要配合线性偏移使用。

image-20260709155634215

class HashMapOpenAddressing {
private:
  int size;
  int capacity = 4;
  const double loadThres = 2.0 / 3.0;
  const int extendRatio = 2;
  vector<Pair*> buckets;
  Pair* TOMBSTONE = new Pair(-1, "-1");
  
public:
  HashMapOpenAddressing() : size(0), buckets(capacity, nullptr) {}
  ~HashMapOpenAddressing() {
    for (Pair* pair : buckets) {
      if (pair != nullptr && pair != TOMBSTONE) {
        delete pair;
      }
    }
    
    delete TOMBSTONE;
  }
  
  int hashFunc(int key) {
    return key % capacity;
  }
  
  double loadFactor() {
    return (double) size / capacity;
  }
  
  int findBucket(int key) {
    int index = hashFunc(key);
    int firstTmobstone = -1;
    
    while (buckets[index] != nullptr) {
      if (buckets[index]->key == key) {
        // 如果之前遇到了删除标记，则线性偏移
        if (firstTombstone != -1) {
          buckets[firstTombstone] = buckets[index];
          buckets[index] = TOMBSTONE;
          return firstTombstone;
        }
        
        return index;
      }
      
      if (firstTombstone == -1 && buckets[index] == TOMBSTONE) {
        firstTombstone = index;
      }
      
      index = (index + 1) % capacity;
    }
    
    // key不存在的话，返回第一个可添加点索引。
    return firstTombstone == -1 ? index : firstTombstone;
  }
  
  string get(int key) {
    int index = findBucket(key);
    if (buckets[index] != nullptr && buckets[index] != TOMBSTONE) {
      return buckets[index]->val;
    }
    
    return "";
  }
  
  void put(int key, string val) {
    if (loadFactor() > loadThres) {
      extend();
    }
    
    int index = findBucket(key);
    if (buckets[index] != nullptr && buckets[index] != TOMBSTONE) {
      buckets[index]->val = val;
      return;
    }
    
    buckets[index] = new Pair(key, val);
    ++size;
  }
  
  void remove(int key) {
    int index = findBucket(key);
    if (buckets[index] != nullptr && buckets[index] != TOMBSTONE) {
      delete buckets[index];
      buckets[index] = TOMBSTONE;
      --size;
    }
  }
  
  void extend() {
    vector<Pair*> bucketsTmp = buckets;
    capacity *= extendRatio;
    buckets = vector<Pair*>(capacity, nullptr);
    size = 0;
    for (Pair* pair : bucketsTmp) {
			if (pair != nullptr && pair != TOMBSTONE) { 
        put(pair->key, pair->val);
        delete pair;
      }
    }
  }
  
  void print() {
    for (Pair* pair : buckets) {
      if (pair == nullptr) {
        cout << "nullptr" << endl;
      } else if (pair == TOMBSTONE) {
        cout << " TOMBSTONE " << endl;
      } else {
        cout << pair->key << " -> " << pair->val << endl;
      }
    }
  }
}

平方探测

平放探测在线性探测的基础上，将步长优化为探测次数的平方，试图缓解聚集效应。但它依旧无法彻底解决聚集现象，因为某些位置在平方计算中依旧作为结果高频出现；同时，即使哈希表中有空桶，平方探测也可能无法访问到它。

多次哈希

多次哈希引入了多个哈希函数 $f_1, f_2, f_3…$，这样如果第一个哈希发生冲突，则使用第二个哈希，在这种情况下，常见操作会调整为：

  • 插入元素：如果 $f_1(x)$ 冲突，则使用 $f_2$进行计算，以此类推，直到找到空位。
  • 查找元素：在相同的哈希函数下顺序查找，遇到空位或者key不对应的元素，则尝试其他哈希函数，直到尝试所有哈希函数。

它不会产生聚集现象，但会带来额外的计算量。