哈希开散列（哈希桶）的实现

开闭散列的对比

闭散列（Closed Hashing）和开散列（Open Hashing）是哈希表中处理哈希冲突的两种主要方法。

闭散列（Closed Hashing）

闭散列也称为开放寻址法（Open Addressing），在这种方法中，所有的元素都存储在哈希表本身中。当发生哈希冲突时，即两个键散列到同一个位置时，闭散列会寻找表中的下一个空位置，并将键值对存储在那里。以下是闭散列的几种常见策略：

1. 线性探测（Linear Probing）：当发生冲突时，从发生冲突的位置开始，依次探测下一个位置，直到找到一个空位置为止。
2. 二次探测（Quadratic Probing）：当发生冲突时，以二次方的方式探测下一个位置，即探测的位置是 h(k) + i^2h(k)+i2，其中 h(k)h(k) 是原始散列位置，ii 是探测次数。
3. 双重散列（Double Hashing）：使用第二个散列函数来决定探测的步长，即探测的位置是 h(k) + i \cdot h2(k)h(k)+i⋅h2(k)，其中 h2(k)h2(k) 是第二个散列函数。

闭散列的优点：

• 不需要额外的空间来存储指针，空间利用率较高。

闭散列的缺点：

• 删除操作较为复杂，因为直接删除元素可能会导致后续元素的查找失败。
• 当表中元素较多时，探测的效率会降低，可能会导致大量冲突。

开散列（Open Hashing）

开散列也称为分离链接法（Separate Chaining），在这种方法中，哈希表的每个槽位维护一个链表。当发生哈希冲突时，冲突的元素会被添加到对应槽位的链表中。以下是开散列的基本原理：

1. 每个槽位对应一个链表。
2. 散列到同一位置的元素都存储在同一个链表中。
3. 查找、插入和删除操作都需要先通过散列函数找到对应的槽位，然后在链表中执行相应的操作。

开散列的优点：

• 处理冲突简单，只需将元素插入链表即可。
• 删除操作相对简单，只需从链表中删除元素。
• 平均情况下，链表长度不会很长，因此查找效率较高。

开散列的缺点：

• 需要额外的空间来存储链表的指针。
• 当哈希表中的元素分布非常不均匀时，某些链表可能会非常长，导致性能下降。

总的来说，闭散列和开散列各有优缺点，实际应用中应根据具体需求和场景选择合适的哈希冲突解决方法。

开散列的实现

namespace hash_bucket {


//HashFunc<int>
template<class K>//是一个独立的类，K只是类型的代称
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};


//HashFunc<string>
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}

return hash;
}
};


template<class T>//不一定非得插入K/V结构
struct HashNode
{
HashNode<T>* _next;//HashNode是模板，HashNode<T>是具体类型
T _data;

HashNode(const T& data)
: _next(nullptr)
, _data(data) 
{}
};


// 前置声明：方便迭代器向上找到声明（迭代器与哈希表类是相互依赖，两者内部都有相互使用）
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;

template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct __HTIterator
{
typedef __HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HashNode<T> Node;

Node* _node;//还是对节点的封装
const HashTable<K, T, KeyOfT, HashFunc>* _pht;//迭代器与哈希表类是相互依赖，两者内部都有相互使用
size_t _hashi;

__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht, size_t hashi)//构造函数：对需要使用的成员变量进行初始化
: _node(node)
, _pht(pht)
, _hashi(hashi)
{}
__HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht, size_t hashi)//当const哈希表去使用迭代器时，防止权限的放大，所以用这个构造函数
: _node(node)
, _pht(pht)
, _hashi(hashi)
{}

Self& operator++()//前置自增运算符
{
if (_node->_next)
_node = _node->_next;
else
{
++_hashi;
while (hashi < pht->_table.size())
{
if (pht->_table[_hashi])//去找一个不为空的节点
{
_node = pht->_table[_hashi];
break;
}
++_hashi;
}

if (_hashi == pht->_table.size())//等于size说明已经遍历完了所有节点
_node = nullptr;

}


return *this;
}
       

Ref operator*()
{
return _node->_data;
}

Ptr operator->()
{
return &_node->_data;
}

bool operator!=(const Self& s)
{
return _node != s._node;
}
};



template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
typedef HashNode<T> Node;
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>//友元声明
friend struct __HTIterator;//在这里声明，是为了让迭代器可以访问哈希表的私有成员
public:
typedef __HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef __HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;

iterator begin()//寻找第一个非空节点
{
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
return iterator(_table[i], this, i);
}
return end();
}

iterator end()
{
return iterator(nullptr, this, -1);
}

const_iterator begin() const//const对象调用const迭代器
{
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
return const_iterator(_table[i], this, i);//这里的this时const修饰过的，只能调用迭代器类的const重载过的构造函数
}
return end();
}

const_iterator end() const
{
return const_iterator(nullptr, this, -1);
}

HashTable()
{
_table.resize(10);
}

~HashTable()
{
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];

while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}

pair<iteratior, bool> Insert(const T& data)
{
HashFunc hf;
KeyOfT kot;

iteratior it = Find(kot(data));//data可能是K/V，也可能是K，所以这里用KeyOfT(data)
if (it != end())//如果找到了，就不插入了
return make_pair(it, false);

//扩容，负载因子 == 1就扩容
if (_n >= _table.size())//不同于闭散列，没有复调insert
{
//建立一个新的vector，进行扩容
vector<Node*> newtable;
newtable.resize(_table.size() * 2);

//移动节点
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];

while (cur)
{
size_t hashi = hf(kot(cur->_data)) % newtable.size();//重新映射
Node* next = cur->_next;

cur->_next = newtable[hashi];
newtable[hashi] = cur;

cur = next;
}

_table[i] = nullptr;//原来的节点置空
}

_table.swap(newtable);//交换，原来的vector变成了新的vector
//出了作用域，newtable销毁
}


size_t hashi = hf(kot(data)) % _table.size();//除留余数法，不要忘记%_table.size()
Node* newnode = new Node(data);

//头插法
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;

return make_pair(iterator(newnode, this, hashi), true);
}

iterator Find(const K& key)
{
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];

while (cur)
{
if (kot(cur->_data) == key)
return iterator(cur, this, hashi);

cur = cur->_next;
}

return end();
}

bool Erase(const K& key)
{
if (Find(key) == end())
return false;

HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _table.size();

Node* cur = _table[hashi];
Node* prev = nullptr;
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)//头删
_table[hashi] = cur->_next;
else
prev->_next = cur->_next;

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

return false;

}


private:
size_t _n = 0;
vector<Node*> _table;
};

}

代码解读

这段代码实现了一个开散列（Open Hashing）的哈希表。下面我将详细解释这段代码的结构和功能。

命名空间 hash_bucket

所有相关的类和函数都定义在 hash_bucket 命名空间内。

HashFunc 模板类

这是一个模板类，用于定义哈希函数。它有两个特化版本，一个用于整数类型，另一个用于字符串类型。

template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key; // 直接将键转换为 size_t 类型。
    }
};

template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t hash = 0;
        for (auto e : key)
        {
            hash *= 31;
            hash += e;
        }
        return hash; // 使用 BKDR 哈希算法计算字符串的哈希值。
    }
};

HashNode 模板类

这个类定义了哈希表中的节点，每个节点包含数据和指向下一个节点的指针。

template<class T>
struct HashNode
{
    HashNode<T>* _next;
    T _data;

    HashNode(const T& data)
        : _next(nullptr)
        , _data(data)
    {}
};

__HTIterator 结构体

这是一个内部迭代器结构体，用于遍历哈希表中的元素。

template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct __HTIterator
{
    // ...（成员变量和构造函数）

    Self& operator++() // 前置自增运算符，用于移动到下一个节点。
    {
        // ...（实现细节）
    }

    Ref operator*() // 解引用运算符，返回当前节点的数据。
    {
        return _node->_data;
    }

    Ptr operator->() // 成员访问运算符，用于访问当前节点的成员。
    {
        return &_node->_data;
    }

    bool operator!=(const Self& s) // 不等于运算符，用于比较两个迭代器。
    {
        return _node != s._node;
    }
};

HashTable 类

这是主要的哈希表类，它使用了开散列的方法。

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
    // ...（友元声明、迭代器类型定义、成员变量）

public:
    // 构造函数和析构函数
    HashTable() { _table.resize(10); } // 构造函数初始化哈希表大小。
    ~HashTable() // 析构函数释放所有节点。
    {
        // ...（实现细节）
    }

    // 迭代器相关函数
    iterator begin() // 返回指向第一个非空节点的迭代器。
    {
        // ...（实现细节）
    }

    iterator end() // 返回一个空的迭代器，表示迭代结束。
    {
        return iterator(nullptr, this, -1);
    }

    // 插入操作
    pair<iterator, bool> Insert(const T& data)
    {
        // ...（实现细节）
    }

    // 查找操作
    iterator Find(const K& key)
    {
        // ...（实现细节）
    }

    // 删除操作
    bool Erase(const K& key)
    {
        // ...（实现细节）
    }

private:
    size_t _n = 0; // 哈希表中元素的数量。
    vector<Node*> _table; // 存储哈希表节点的指针数组。
};

插入操作 Insert

插入操作首先检查是否需要扩容，然后计算哈希值，创建新节点，并将其插入到对应链表的头部。

pair<iterator, bool> Insert(const T& data)
{
    // ...（计算哈希值、检查是否需要扩容）

    size_t hashi = hf(kot(data)) % _table.size(); // 计算哈希值。
    Node* newnode = new Node(data); // 创建新节点。

    // 头插法插入节点。
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    ++_n;

    return make_pair(iterator(newnode, this, hashi), true);
}

查找操作 Find

查找操作通过计算哈希值，然后在对应的链表中查找元素。

iterator Find(const K& key)
{
    size_t hashi = hf(key) % _table.size(); // 计算哈希值。
    Node* cur = _table[hashi]; //