哈希表
数组简单实现哈希表
//
// Created by zhou on 2023/10/6.
// 数组实现哈希表
#include "Array_Hash_Map.h"
#include "iostream"
#include "string"
#include "vector"
using std::string;
using std::vector;
using std::cin;
using std::cout;
using std::endl;
struct Pair{
public:
int key;
string value;
Pair(int key, string value){
this->key = key;
this->value = value;
}
};
/**
* 基于数组实现的哈希表
*/
class ArrayHashMap{
private:
vector<Pair *> buckets;
public:
ArrayHashMap(){
// 初始化数组，包含100个桶
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 nullptr;
return pair->value;
}
/**
* 添加
*/
void put(int key, string value) {
int index = hashFunc(key);
Pair *pair = new Pair(key, value);
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;
}
/**
* 获取所有键
*/
vector<int> keySet() {
vector<int> keySet;
for (Pair *pair : buckets) {
if (pair != nullptr) {
keySet.push_back(pair->key);
}
}
return keySet;
}
/**
* 获取所有值
*/
vector<string> valueSet() {
vector<string> valueSet;
for (Pair *pair : buckets) {
if (pair != nullptr) {
valueSet.push_back(pair->value);
}
}
return valueSet;
}
/**
* 打印哈希表
*/
void print() {
for (Pair *kv : buckets) {
cout << kv->key << "->" << kv->value << endl;
}
}
};
链地址法
//
// Created by zhou on 2023/10/6.
// 哈希冲突与扩容
// 此处利用vector实现
#include "hash_map_chaining.h"
#include "common.h"
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), 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);
// 相当于找到头节点
auto &bucket = buckets[index];
// 类似往后遍历链表
for(Pair *pair : bucket) {
if(pair->key == key) {
return pair->value;
}
}
return nullptr;
}
/**
* 添加
*/
void put(int key, string value) {
// 负载因子超过阈值，需要扩容
if(loadThres < loadFactor()) {
extend();
}
int index = hashFunc(key);
// 若已有key，则更新对应的值
for (auto &pair: buckets[index]) {
if (pair->key == key) {
pair->value = value;
return;
}
}
// 新key则添加进来
buckets[index].push_back(new Pair(key, value));
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 *tempPair = bucket[i];
// 利用迭代器，删除键值对
bucket.erase(bucket.begin() + i);
// 释放内存
delete tempPair;
size--;
return;
}
}
}
/**
* 扩容
*/
void extend() {
// 暂存旧的桶
vector<vector<Pair *>> bucketTemp = buckets;
// 准备扩容大小
capacity *= extendRatio;
// 清除桶的内容
buckets.clear();
// 正式扩容
buckets.resize(capacity);
// 元素计数清零
size = 0;
// 将原哈希表中的键值对搬运到新的哈希表中
for(auto &bucket : bucketTemp) {
for(Pair *pair : bucket) {
// put()函数已有size++，故此处无需size++
put(pair->key, pair->value);
// 释放内存
delete pair;
}
}
}
};
线性探测法
//
// Created by zhou on 2023/10/6.
//
#include "hash_map_open_addressing.h"
#include "common.h"
class HashMapOpenAddressing {
private:
// 元素数量
int size;
// 桶数组容量
int capacity;
// 负载因子阈值
double loadThres;
// 扩容倍数
int extendRatio;
// 桶数组
vector<Pair *> buckets;
// 移除标记
Pair* removed;
public:
HashMapOpenAddressing() {
size = 0;
capacity = 4;
loadThres = 2.0 / 3.0;
extendRatio = 2;
// 初始化桶
buckets = vector<Pair *>(capacity, nullptr);
// 初始化removed标记
removed = new Pair(-1, "-1");
}
int hashFunc(int key) {
return key % capacity;
}
// static_cast 用于将size类型转换成double
double loadFactor() {
return static_cast<double>(size) / capacity;
}
/**
* 查询
*/
string get(int key) {
int index = hashFunc(key);
// 线性探测
for (int i = 0; i < capacity; ++i) {
// 找到最尾回到头部
int j = (index + i) % capacity;
// 若然是空桶，则没找到
if(buckets[j] == nullptr) {
return nullptr;
}
// 若找到了而且对应位置上元素未被移除，则是所找
if(buckets[j]->key == key && buckets[j] != removed) {
return buckets[j]->value;
}
}
return nullptr;
}
/**
* 添加
*/
void put(int key, string value) {
// 负载因子超出阈值，需要扩容
if (loadThres < loadFactor()) {
extend();
}
int index = hashFunc(key);
for (int i = 0; i < capacity; ++i) {
int j = (index + i) % capacity;
// 若是空桶或已被移除，则直接添加新的即可
if (buckets[j] == nullptr || buckets[j] == removed) {
buckets[j] = new Pair(key, value);
size++;
return;
}
// 若已有相同的key，则更新对应的值
if (buckets[j]->key == key) {
buckets[j]->value = value;
return;
}
}
}
/**
* 删除
*/
void remove(int key) {
int index = hashFunc(key);
for (int i = 0; i < capacity; ++i) {
int j = (index + i) % capacity;
// 空桶，没找到，不用删
if (buckets[j] == nullptr) return;
// 找到，移除，并做标记
if(buckets[j]->key == key) {
delete buckets[j];
buckets[j] = removed;
size--;
return;
}
}
}
/**
* 扩容
*/
void extend() {
// 暂存在临时桶
vector<Pair *> tempBucket = buckets;
// 扩容
capacity *= extendRatio;
// 初始化新桶
buckets = vector<Pair *>(capacity, nullptr);
size = 0;
// 将元素移入新桶
for (auto &pair: tempBucket) {
// 如果不是空的而且没有移除标记的，则是需要移入的元素
if (pair != nullptr && pair != removed) {
put(pair->key, pair->value);
}
}
}
};
