哈希知识详解

🕗 发布于 2024-12-09 08:38 哈希算法算法 数据结构

一、哈希

以前，在面对海量数据的查找时，最快就是红黑树 logN，无法满足需求。

于是探索出了另一种用关键字 key 值与其存储位置建立映射的思想，让查找效率提升到 O(1) ，这个就是哈希。

二、哈希函数

1、直接定值法

①、直接定值法：用当前的值与数组建立一一对应的关系。

例如，a,b,c,d 在数组 v 上的映射为 v[0],v[1],v[2],v[3]

②、直接定值法的缺点：如果给的值直接跨度较大就非常消耗空间。

例如：1,1000 在数组 v 上的映射为 v[1] v[1000] 。为了存两个数开了1000多空间，十分浪费。

2、除留余数法

除留余数法就是：映射位置为 key 值模上空间大小。( i = key % 空间大小 )

三、哈希冲突

用上述方法可能会有哈希冲突的问题(也就是不同的 key 值映射到了同一个地方)

如：除留余数法，空间大小为7,key值 1 和 8 会映射在同一个地方(1%7 = 8%7 = 1)

四、哈希冲突解决

1、闭散列(开放定值法)

假设空间大小为 N

线性探测：假设用除留余数法，i = key % N，如果找到的当前位置有值了，那就向后找，直到找到空位置，放进去。

查找：执行 i = (i + 1) % N，不断向后查找(后面找完了，就从第一个位置开始继续找)，直到找到空位置。

可以看到，哈希冲突越多，我们查找的效率越低。因此，我们可以想办法让数据的个数和空间大小维持在一个比例，降低哈希冲突。也就是维持负载因子 / 载荷因子的大小

(负载因子 / 载荷因子 = 数据个数 / 空间大小 )。

闭散列(开放定值法) 一般将这个比例维持在 0.7 左右。

删除：如上图，如果我们删除 8，那么查找 16 的时候就找到空位置 2，无法找到 16。因此，我们删除不能只是简单的将值删除，还应该将表的每个位置增设标志位。

闭散列代码

插入：

1、判断当前负载因子 / 载荷因子是否超过 0.7，如果超过，就扩容。

2、因为扩容后的空间大小变化了，因此，所有的数据需要重新插入，我们可以定义一个临时对象 HashTable temp，把当前所有数据插入 temp 中，再将 temp 中的数据换出来，完成重新插入。

3、根据新的空间大小和 key 值，找到映射位置。如果当前位置有值，就向后查找空闲位置(标志位不为 EXIST)，找到就插入

查找：

1、先判断当前 key 值的映射位置 keyi 是否正确，如果不对，继续向后查找

2、如果查找到了，返回下标；如果没找到，找了一圈回到 keyi ，则返回 -1

删除：

1、通过 key 用 Find 找到 keyi，如果不存在，就返回

2、如果存在，则将标志位设为 DELETE 并 --_size

// 定义的状态
enum Status
{
EMPTY,
EXIST,
DELETE
};

// 哈希表中的数据
template<class K, class V>
struct HashData
{
typedef HashData<K, V> self;
public:
HashData()
:_status(EMPTY)
{}

/*HashData(const std::pair<K, V>& value)
{
_data = value;
_status = EXIST;
}

self& operator=(const self& val)
{
_data = val._data;
_status = val._status;

return *this;
}*/
public:
std::pair<K, V> _data; // 数据
Status _status; // 状态
};


template<class K, class V>
class HashTable
{
public:
static const double rate;
public:
HashTable(int n = 0)
{
_table.resize(n);
}

void Insert(const std::pair<K, V>& value)
{
// 空间大小
int n = _table.size();

// 如果比例超过 rate 就扩容
if (_size >= rate * n)
{
// 扩容为原来的 2 倍 (哈希表的大小最好为素数，这里就简化一下)
int newcapacity = n == 0 ? 4 : 2 * n;

// 因为扩容后空间大小变了，因此每个数据的映射位置也会变化，所以要重新插入
// 定义一个临时的哈希表
HashTable<K, V> temp(newcapacity);
// 把原来的数据重新插入新表中
for (auto e : _table)
{
if(e._status == EXIST)
temp.Insert(e._data);
}

// 将新表换出来
_table.swap(temp._table);
_size = temp._size;
n = newcapacity;
}
// 通过除留余数法 找到对应下标
int keyi = value.first % n;

// 找到第一个标记位不为 EXIST 的位置，放入
while (_table[keyi]._status == EXIST)
{
keyi = (keyi + 1) % n;
}
_table[keyi]._data = value;
_table[keyi]._status = EXIST;
_size++;
}

    // 找到了就返回下标，没找到返回 -1
int Find(const K& key)
{
int n = _table.size();
// 通过除留余数法 找到对应下标
int keyi = key % n;
if (_table[keyi]._data.first == key)
{
return keyi;
}

// 从第 2 个位置继续查找
int pos = (keyi + 1) % n;
while (_table[pos]._status != EMPTY)
{
// 转一圈回来了，全是 DELETE 和 EXIST
if (pos == keyi)
break;
if (_table[pos]._data.first == key)
{
return pos;
}
pos = (pos + 1) % n;
}

return -1;
}

void Erase(const K& key)
{
int n = _table.size();
// 如果没找到，就直接返回
int pos = Find(key);
if (pos == -1) return;

// size-- 并设置标志位
_table[pos]._status = DELETE;
_size--;
}

private:
std::vector<HashData<K, V>> _table; // 哈希表
int _size; // 当前负载
};
template<class K, class V>
const double HashTable<K, V>::rate = 0.7; // 比例为 0.7

2、哈希桶

与闭散列不同，哈希桶(也叫做拉链法) 是在对应位置放单链表，当有哈希冲突的时候，就把值尾插挂在对应位置的单链表下。

优化：当一个位置的单链表的节点个数超过 8 个时，可以考虑挂红黑树。

哈希桶的结构

// 哈希表下挂的 单链表的节点
template<class T>
struct HashNode
{
HashNode()
{}

HashNode(const T& val)
:_val(val)
{}

HashNode<T>* _next = nullptr; // next 指针，指向下一个位置
T _val = T(); // 值
};

// K 表示 key(关键字) 的类型
// T 表示 值 的类型
// KOFT 表示通过 T 找到对应的 key 的仿函数(封装map和set就可以一起使用了)
// map 的值是 pair<K, T>，set 的值和 key 一样，因此，通过传入仿函数就可以让它们一起使用
// HASH 表示哈希函数，如，string 就需要通过哈希函数转化才能求位置
template<class K, class T, class KOFT, class HASH>
class HashBucket
{
    // typedef
using node = HashNode<T>;
    // 设置 负载因子 / 载荷因子 的比例
static const double rate;// 静态成员变量，类内定义，类外初始化

public:
HashBucket(int n = 0)
{
        // 将数组的大小开为 n
_table.resize(n, nullptr);
}

private:
std::vector<node*> _table;// 哈希表，每个位置存一个单链表
size_t _size;// 数据个数
};
template<class K, class T, class KOFT, class HASH>
const double HashBucket<K, T, KOFT, HASH>::rate = 0.7;// 初始化比例

查找方法

1、先判断哈希表是否为空

2、通过哈希函数得到值，用除留余数法得到对应的下标

3、通过下标找到单链表 _table[keyi] ，在这个单链表中遍历查找即可

iterator Find(const K& key)
{
    // 如果表是空的，那么不需要查找
if (_table.size() == 0)
return end();

// 通过哈希函数，除留余数法 得到对应下标 keyi
HASH hashfunc;
int keyi = hashfunc(key) % _table.size();

KOFT kot;

// 从单链表中查找值
node* head = _table[keyi];
while (head)
{
// 找到返回
if (kot(head->_val) == key)
{
return iterator(head, this);
}
head = head->_next;
}
// 没找到返回 end()
return end();
}

插入方法

1、先判断 key 值是否已经存在，存在就不插入了

2、如果负载因子 / 载荷因子的比例超过定义的 rate，扩容

扩容思想和上面的闭散列类似，因为哈希桶的大小发生变化，要重新插入原有值。我们可以先定义一个临时的大小为 newcapacity 的哈希桶，再将原本的数据插入新的临时哈希桶中，只要把临时桶的资源换出来，就完成了重新插入。

3、通过哈希函数和 key 找到对应下标，通过下标找到该插入的单链表

4、创建新节点，头插到单链表中，将 _size++ 完成插入

// 设计前面的 iterator 可以帮助 运算符[], 拿到迭代器
std::pair<iterator, bool> Insert(const T& val)
{
// 拿到 key 值
KOFT kot;
const K& key = kot(val);

// 通过Find判断是否存在对应的 key
iterator it = Find(key);
if (it != end())
return std::make_pair(it, false);

int n = _table.size();
if (_size >= n * rate)
{
// 如果 size 为空，设置初始容量为 4，否则新容量为原来的 2 倍
int newcapacity = _size == 0 ? 4 : 2 * n;

// 设置临时对象
HashBucket temp(newcapacity);
for (node* head : _table)
{
// 因为容量发生变化，所以所有数据的映射位置发生变化
// 将所有数据重新插入 temp
while (head)
{
temp.Insert(head->_val);
head = head->_next;
}
}

// 将 temp 中的资源换出来
_table.swap(temp._table);
_size = temp._size;
n = newcapacity;
}

// 得到对应下标 keyi
HASH hashfunc;
int keyi = hashfunc(key) % n;

// 创建新节点
node* newnode = new node(val);

// 头插
newnode->_next = _table[keyi];
_table[keyi] = newnode;

// ++size
++_size;

return std::make_pair(iterator(newnode, this), true);
}

删除方法

1、和插入一样，先进行查找，如果没找到 key，就直接返回

2、通过 key 和哈希函数得到对应的下标，找到对应单链表

3、问题转化为在单链表中查找节点，找到返回即可

bool Erase(const K& key)
{
// 先进行查找，没找到直接返回
iterator iter = Find(key);
if (iter == end())
return false;

// 通过 key 得到下标
HASH hashfunc;
int keyi = hashfunc(key) % _table.size();

KOFT kot;

node* prev = nullptr;
node* cur = _table[keyi];
while (cur)
{
if (kot(cur->_val) == key)
{
if (prev == nullptr)
_table[keyi] = cur->_next;
else
prev->_next = cur->_next;

delete cur;
break;
}
prev = cur;
cur = cur->_next;
}
return true;
}

析构

遍历哈希表，将所有单链表释放。

~HashBucket()
{
// 释放所有单链表的节点
for (node* head : _table)
{
while (head)
{
node* next = head->_next;
delete head;
head = next;
}
}
}

迭代器

1、迭代器基本结构

哈希桶的迭代器需要节点，因为进行++操作时，需要查找表的下一个非空节点，因此还需要这个哈希桶的指针。

哈希桶的 operator== 和 operator!= 判断节点的地址是否相同即可

解引用*和->，* 返回值引用，-> 返回值的地址

注意：因为通过哈希表指针使用了私有成员 _table ，因此要把迭代器设为友元，或设置 GetTable() 函数返回。

// 声明
template<class K, class T, class KOFT, class HASH>
class HashBucket;

template<class K, class T, class KOFT, class HASH>
class __HashIterator
{
public:
typedef HashNode<T> node;
typedef HashBucket<K, T, KOFT, HASH> HT;
typedef __HashIterator<K, T, KOFT, HASH> self;

__HashIterator(node* node, HT* ht)
:_node(node)
,_ht(ht)
{}

bool operator!=(const self& iter)
{
return _node != iter._node;
}
bool operator==(const self& iter)
{
return _node == iter._node;
}
T& operator*()
{
return _node->_val;
}
T* operator->()
{
return &(_node->_val);
}

node* _node;
HT* _ht;
};

2、迭代器 ++

++iterator，前置++，返回自己

思路：找到下一个不为空的节点，因为是++，所以不需要回到开头，后面都为空就返回。

self& operator++()
{
// 如果 _node 为空，说明在 end() 位置，直接返回
if (_node == nullptr)
return *this;

// 如果该节点的 next 不为空，返回它的下一个节点
if (_node->_next)
{
_node = _node->_next;
return *this;
}

// 如果它是该链表的最后一个节点，找下一条链表的头
//  获取当前节点的映射位置 keyi
KOFT kot;
HASH hashfunc;
const K& key = kot(_node->_val);
int keyi = hashfunc(key) % _ht->_table.size();

// 向后查找哈希表中不为空的链表
while (++keyi < _ht->_table.size())
{
// 找到，_node 为当前链表的头，也就是 _table[keyi]
if (_ht->_table[keyi])
{
_node = _ht->_table[keyi];
break;
}
}
// 没找到，_node 返回空
if (keyi == _ht->_table.size())
_node = nullptr;
return *this;
}

完整哈希桶代码

namespace bucket
{
// 哈希表下挂的 单链表的节点
template<class T>
struct HashNode
{
HashNode()
{}

HashNode(const T& val)
:_val(val)
{}

HashNode<T>* _next = nullptr;
T _val = T();
};
// 声明
template<class K, class T, class KOFT, class HASH>
class HashBucket;

template<class K, class T, class KOFT, class HASH>
class __HashIterator
{
public:
typedef HashNode<T> node;
typedef HashBucket<K, T, KOFT, HASH> HT;
typedef __HashIterator<K, T, KOFT, HASH> self;

__HashIterator(node* node, HT* ht)
:_node(node)
,_ht(ht)
{}

bool operator!=(const self& iter)
{
return _node != iter._node;
}
bool operator==(const self& iter)
{
return _node == iter._node;
}
T& operator*()
{
return _node->_val;
}
T* operator->()
{
return &(_node->_val);
}

self& operator++()
{
// 如果 _node 为空，说明在 end() 位置，直接返回
if (_node == nullptr)
return *this;

// 如果该节点的 next 不为空，返回它的下一个节点
if (_node->_next)
{
_node = _node->_next;
return *this;
}

// 如果它是该链表的最后一个节点，找下一条链表的头
//  获取当前节点的映射位置 keyi
KOFT kot;
HASH hashfunc;
const K& key = kot(_node->_val);
int keyi = hashfunc(key) % _ht->_table.size();

// 向后查找哈希表中不为空的链表
while (++keyi < _ht->_table.size())
{
// 找到，_node 为当前链表的头，也就是 _table[keyi]
if (_ht->_table[keyi])
{
_node = _ht->_table[keyi];
break;
}
}
// 没找到，_node 返回空
if (keyi == _ht->_table.size())
_node = nullptr;
return *this;
}


node* _node;
HT* _ht;
};

template<class K, class T, class KOFT, class HASH>
class HashBucket
{
using node = HashNode<T>;
static const double rate;

public:
using iterator = __HashIterator<K, T, KOFT, HASH>;
friend iterator;

HashBucket(int n = 0)
{
_table.resize(n, nullptr);
}

// 设计前面的 iterator 可以帮助 运算符[], 拿到迭代器
std::pair<iterator, bool> Insert(const T& val)
{
// 拿到 key 值
KOFT kot;
const K& key = kot(val);

// 通过Find判断是否存在对应的 key
iterator it = Find(key);
if (it != end())
return std::make_pair(it, false);

int n = _table.size();
if (_size >= n * rate)
{
// 如果 size 为空，设置初始容量为 4，否则新容量为原来的 2 倍
int newcapacity = _size == 0 ? 4 : 2 * n;

// 设置临时对象
HashBucket temp(newcapacity);
for (node* head : _table)
{
// 因为容量发生变化，所以所有数据的映射位置发生变化
// 将所有数据重新插入 temp
while (head)
{
temp.Insert(head->_val);
head = head->_next;
}
}

// 将 temp 中的资源换出来
_table.swap(temp._table);
_size = temp._size;
n = newcapacity;
}

// 得到对应下标 keyi
HASH hashfunc;
int keyi = hashfunc(key) % n;

// 创建新节点
node* newnode = new node(val);

// 头插
newnode->_next = _table[keyi];
_table[keyi] = newnode;

// ++size
++_size;

return std::make_pair(iterator(newnode, this), true);
}

iterator begin()
{
// 找到第一个非空单链表的头
for (auto head : _table)
{
if (head)
return iterator(head, this);
}

return iterator(nullptr, this);
}

iterator end()
{
// 为空代表走到了结尾
return iterator(nullptr, this);
}

iterator Find(const K& key)
{
if (_table.size() == 0)
return end();
// 得到对应下标 keyi
HASH hashfunc;
int keyi = hashfunc(key) % _table.size();

KOFT kot;

// 从单链表中查找值
node* head = _table[keyi];
while (head)
{
// 找到返回
if (kot(head->_val) == key)
{
return iterator(head, this);
}
head = head->_next;
}
// 没找到返回 end()
return end();
}

bool Erase(const K& key)
{
// 先进行查找，没找到直接返回
iterator iter = Find(key);
if (iter == end())
return false;

// 通过 key 得到下标
HASH hashfunc;
int keyi = hashfunc(key) % _table.size();

KOFT kot;

node* prev = nullptr;
node* cur = _table[keyi];
while (cur)
{
if (kot(cur->_val) == key)
{
if (prev == nullptr)
_table[keyi] = cur->_next;
else
prev->_next = cur->_next;

delete cur;
break;
}
prev = cur;
cur = cur->_next;
}
return true;
}

~HashBucket()
{
// 释放所有单链表的节点
for (node* head : _table)
{
while (head)
{
node* next = head->_next;
delete head;
head = next;
}
}
}

private:
std::vector<node*> _table;
size_t _size;
};

template<class K, class T, class KOFT, class HASH>
const double HashBucket<K, T, KOFT, HASH>::rate = 0.7;
}

五、通过哈希桶封装 unordered_map 和 unordered_set

1、封装 unordered_set

// 设置哈希函数
template<class K>
class HashFunc
{
public:
int operator()(const K& val)
{
return val;
}
};
// 特化，string
template<>
int HashFunc<std::string>::operator()(const std::string& str)
{
int key = 0;
for (char ch : str)
{
key += ch;
}

return key;
}

// 通过 值 找 key
// 对于 unordered_set 关键字和值都是 key
template<class K>
class KOfT
{
public:
const K& operator()(const K& key)
{
return key;
}
};

// 哈希函数给了默认的，也可以外面传
// unordered_set<int> 第一个模版参数是 key
template<class K, class HASH= HashFunc<K>>
class unordered_set
{
public:
// typedef
using iterator = typename bucket::HashBucket<K, K, KOfT<K>, HASH>::iterator;

// 插入、修改、查找等函数直接调用 哈希桶的接口即可
std::pair<iterator, bool> Insert(const K& val)
{
return _ht.Insert(val);
}

bool Erase(const K& key)
{
return _ht.Erase(key);
}

iterator Find(const K& key)
{
return _ht.Find(key);
}

iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}


private:
// 关键字为 K, 值为 k
bucket::HashBucket<K, K, KOfT<K>, HASH> _ht;
};

2、封装 unordered_map

哈希桶的 T 为值，在 unordered_set 中为 K，在 unordered_map 中为 pair<K, T>

unordered_map 中的 T 为第二个类型，如 unordered_map<string, int> 中，代表的是 int

// 设置的默认哈希函数
template<class K>
class HashFunc
{
public:
int operator()(const K& val)
{
return val;
}
};

// 特化
template<>
int HashFunc<std::string>::operator()(const std::string& str)
{
int key = 0;
for (char ch : str)
{
key += ch;
}

return key;
}

// 对于 unordered_map 关键字为 K, 值为 pair<K, T>
// 通过 KOfT 就可以实现 unordered_map 和 unordered_set 使用同一个类封装
template<class K, class T>
class KOfT
{
public:
const K& operator()(const T& val)
{
return val.first;
}
};

// unordered_map<string, int>
// K 为key，类型为string 
// T 类型为int
template<class K, class T, class HASH = HashFunc<K>>
class unordered_map
{
public:
using iterator = typename bucket::HashBucket<K, std::pair<K, T>, KOfT<K, std::pair<K, T>>, HASH>::iterator;

std::pair<iterator, bool> Insert(const std::pair<K, T>& val)
{
return _ht.Insert(val);
}

bool Erase(const K& key)
{
return _ht.Erase(key);
}

iterator Find(const K& key)
{
return _ht.Find(key);
}

T& operator[](const K& key)
{
// 运算符[] 就是如果存在，返回值引用；如果不存在，插入{key, 0}，并返回值引用
// 因此，我们只要插入{key, 0} 即可
std::pair<iterator, bool> ret = Insert(std::make_pair(key, 0));

return ret.first->second;
}

iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
private:
// 调用哈希桶时，key 为 K，值为pair<K, T>
bucket::HashBucket<K, std::pair<K, T>, KOfT<K, std::pair<K, T>>, HASH> _ht;
};

感谢观看♪(･ω･)ﾉ

原文地址：https://blog.csdn.net/m0_74626010/article/details/144330516

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【集群划分】含分布式光伏的配电网集群电压控制【33节点】
下一篇：B4X编程语言：B4A控件事件汇总

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14