二次探測是避免哈希沖突的一種常見手段，思想是：

為渭南等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及渭南網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都網(wǎng)站設(shè)計、成都網(wǎng)站制作、渭南網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

    插入：

    找到哈希位置（serch）->如果不沖突就插入，沖突就進(jìn)行第一次探測

    第1次探測：

    哈希位置變?yōu)樵泄Ｎ恢眉由?*1的偏移->進(jìn)行插入

    ....

    ....

    第i次探測：

    哈希位置變?yōu)樵泄Ｎ恢眉由蟟*i的偏移->進(jìn)行插入

    知道插入完成為止。

如圖所示：

    哈希類代碼如下：

#pragma once
#include<vector>
#include<string>
enum Status
{
	DELETE,
	EMPTY,
	EXIST,
};
template<class K, class V>
struct KV
{
	KV()
	{}
	KV(K _key, V _value)
	:key(_key)
	, value(_value)
	{}
	Status s;
	K key;
	V value;
};
template<class K>
struct DefaultHash
{
	size_t operator()(const K& k)
	{
		return k;
	}
};
template<>
struct DefaultHash<string>
{
	size_t operator()(const string&k)
	{
		size_t ret = 0;
		for (size_t i = 0; i < k.size(); ++i)
		{
			ret *= 10;
			ret += k[i];
		}
		return ret;
	}
};
template<class K,class V,
class Hash = DefaultHash<K> >
class HashTable
{
public:
	HashTable(size_t capacity)
		:tables(new KV<K,V>[capacity])
		,_size(0)
		, _capacity(capacity)
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			tables[i].s = EMPTY;
		}
	}
	HashTable()
		:_size(0)
		, _capacity(0)
	{}
	void Push(const KV<K,V> &x)
	{
		size_t index = search(x.key);
		tables[index].s = EXIST;
		tables[index].key = x.key;
		tables[index].value = x.value;
		++_size;
	}
	void Print()
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			cout << i << ":";
			if (tables[i].s == EXIST)
				cout <<"["<<tables[i].key<<","<< tables[i].value<<"]";
			else
				cout << "NULL";
			cout << endl;
		}
		cout << endl;
	}
	int Find(const K& key)
	{
		Hash Search;
		int index = Search(key) % _capacity;
		size_t i = 0;
		while (tables[index].s != EMPTY)
		{
			if (tables[index].key == key&&tables[index].s == EXIST)
				return index;
			i++;
			index += 2*i-1;
			if (index >= _capacity)
				index %= _capacity;
		}
		return -1;
	}
	void Pop(const K& key)
	{
		int index = Find(key);
		if (index > 0)
		{
			tables[index].s = DELETE;
			_size--;
		}
	}
	~HashTable()
	{
		if (tables)
			delete[]tables;
		_size = 0;
		_capacity = 0;
	}
protected:
	size_t search(K key)
	{
		if (_size * 2 >= _capacity)
		{
			HashTable tmp(_capacity * 2 + 10);
			for (size_t i = 0; i < _capacity; ++i)
			{
				if (tables[i].s == EXIST)
					tmp.Push(tables[i]);
			}
			std::swap(tables, tmp.tables);
			std::swap(_size, tmp._size);
			std::swap(_capacity, tmp._capacity);
		}
		Hash Search;
		size_t index = Search(key)%_capacity;
		size_t i = 0;
		while (tables[index].s == EXIST)
		{
			i++;
			index += i*i;
			if (index >= _capacity)
				index %= _capacity;
		}
		return index;
	}
protected:
	KV<K,V>* tables;
	size_t _size;
	size_t _capacity;
};

    如有疑問希望提出，有不足也希望指正

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)頁名稱：【代碼】key-value模式下的哈希二次探測與簡單的哈希類的實(shí)現(xiàn)-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://www.rwnh.cn/article40/copdeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、軟件開發(fā)、外貿(mào)建站、商城網(wǎng)站、App開發(fā)、微信公眾號

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)