已下代码已在gitee上开源厂库地址https://gitee.com/tgwTTT/c-lreant/blob/master/Hashbucket/hashbucket.h

本文是基于上一篇文章哈希表http://www.tgwttt.xyz/?p=150的基础上改动

哈希桶是哈希表解决hash冲突的一种方法，他是利用链表去存储数据，当遇到hash冲突时就需要往下查询，以解决hash冲突。下面是实现

首先就是定义节点，与普通hash表不同是在数据节点的定义。另外，我们引入c++里面unordered_map底层的质素数表每当扩容时就换质数表中的数

质数表的实现： inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last – 1) : *pos;
}

下面是节点定义

template
struct HashNode {
	pair_kv;
	HashNode* _next;
	HashNode(const pair&kv)
		:_kv(kv)
		,_next(nullptr)
	{ }
};
//节点定义与前面hash表一致，但是多了一个节点指针，指向下一个节点

其中最核心和函数就是插入函数Insert:

bool Insert(const pair& kv) {
	if (Find(kv.first))return false;
	//负载因子==1时扩容
	if (_n == _tables.size()) {
		//Hash newht;
		vectornewTable(__stl_next_prime(_tables.size() + 1));
		for (size_t i = 0; i < _tables.size(); i++) {
			Node* cur = _tables[i];
			while (cur) {
				//头插到新表
				Node* next = cur->_next;
				size_t hashi = cur->_kv.first % newTable.size();
				cur->_next = newTable[hashi];
				newTable[hashi] = cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newTable);
	}
	size_t hashi = kv.first % _tables.size();
	//头插
	Node* newnode = new Node(kv);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
};
在插入时必须先检查函数的负载因子当负载因子等于1时就必须要扩容了，扩容数量为上面质数表中的下一个数据，但是当扩容时就不和哈希表一样拷贝过去，再用swap交换，这里可以直接将旧表的数据插入新表。
Find函数就不赘述了，看代码很容易明白
Node* Find(const K& key) {
	size_t hashi = key % _tables.size();
	Node* cur = _tables[hashi];
	while (cur) {
		if (cur->_kv.first == key) {
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr;
}
删除函数必须分两种情况，删除的节点是vector中的节点，或是中间节点，如果是vector里面的节点就必须先将cur的下一个节点放入里面。
bool Erase(const K& key) {
	size_t hashi = key % _tables.size();
	Node* prev = nullptr;
	Node* cur = _tables[hashi];
	if (cur) {
		if (cur->_kv.first == key) {
			//删除
			if (prev == nullptr) {//删除的是头结点
				_tables[hashi] = cur->_next;
			}
			else {
				prev->_next = cur->_next;
			}
			delete cur;
			return true;
		}
		else {
			prev = cur;
			cur = cur->_next;
		}
	}
	return false;
}
完整代码在gitee里面自取
今天的更新就到这里了，如有错误欢迎指出