哈希表，是根據(jù)關(guān)鍵字（Key value）而直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來訪問記錄，這加快了查找速度。這個(gè)映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。（摘自維基百科）

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

 對(duì)不同的關(guān)鍵字可能得到同一散列地址，即k1!=k2，而f(k1)=f(k2)，這種現(xiàn)象稱為碰撞（英語：Collision）,也叫哈希沖突。

•  處理哈希沖突的方法有很多種：

1. 閉散列法

2. 開鏈法（哈希桶）

3. 素?cái)?shù)表

4. 字符串哈希算法

 在這里我們討論最簡(jiǎn)單的閉散列法的線性探測(cè)法，學(xué)會(huì)了這種方法，就可以在線性探測(cè)法的思想基礎(chǔ)上領(lǐng)會(huì)其他方法。

• 線性探測(cè)法

 定義：通過散列函數(shù)hash(key)，找到關(guān)鍵字key在線性序列中的位置，如果當(dāng)前位置已經(jīng)有了一個(gè)關(guān)鍵字，就長(zhǎng)生了哈希沖突，就往后探測(cè)i個(gè)位置（i小于線性序列的大小），直到當(dāng)前位置沒有關(guān)鍵字存在。

#pragma once
#include<iostream>
#include<string>
using namespace std;

enum State
{
	EMPTY,
	EXIST,
	DELETE
};
template<class T>
struct DefaultFunc
{
	size_t operator()(const T& data)
	{
		return (size_t)data;
	}
};

struct StringFunc
{
	size_t operator()(const string& str)
	{
		size_t sum = 0;
		for (size_t i = 0; i < str.size(); ++i)
		{
			sum += str[i];
		}
		return sum;
	}
};
template<class K,class FuncModel=DefaultFunc<K>>
class HashTable
{
public:
	HashTable();
	HashTable(const size_t size);
	bool Push(const K& data);//增
	bool Remove(const K& data);//刪
	size_t Find(const K& data);//查
	bool Alter(const K& data, const K& newdata);//改
	void Print();//打印哈希表
protected:
	size_t HashFunc(const K& data);//散列函數(shù)（哈希函數(shù)）
	void Swap(HashTable<K, FuncModel>& x);
protected:
	K* _table;//哈希表
	State* _state;//狀態(tài)表
	size_t _size;
	size_t _capacity;
	FuncModel _HF;//區(qū)分默認(rèn)類型的哈希函數(shù)和string類型的哈希函數(shù)
};

.cpp文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"HashTable.h"
template<class K, class FuncModel = DefaultFunc<K>>
HashTable<K, FuncModel>::HashTable()
	:_table(NULL)
	, _state(NULL)
	, _size(0)
	, _capacity(0)
{}

template<class K, class FuncModel = DefaultFunc<K>>
HashTable<K, FuncModel>::HashTable(const size_t size)
	:_table(new K[size])
	, _state(new State[size])
	, _size(0)
	, _capacity(size)
{
        //這里別用memset（）來初始化_state，對(duì)于枚舉類型的動(dòng)態(tài)內(nèi)存不能用memset初始化
        //老老實(shí)實(shí)一個(gè)一個(gè)初始化
	for (size_t i = 0; i < _capacity; i++)
	{
		_state[i] = EMPTY;
	}
}
template<class K, class FuncModel = DefaultFunc<K>>
size_t HashTable<K, FuncModel>::HashFunc(const K& data)
{
	return _HF(data)%_capacity;//Mod哈希表的容量，找到在哈希表中的位置，
	//其實(shí)在這里最好Mod一個(gè)素?cái)?shù)
}

template<class K, class FuncModel = DefaultFunc<K>>
void HashTable<K, FuncModel>::Swap(HashTable<K, FuncModel>& x)//交換兩個(gè)哈希表
{
	swap(_table, x._table);
	swap(_state, x._state);
	swap(_size, x._size);
	swap(_capacity, x._capacity);
}


template<class K, class FuncModel = DefaultFunc<K>>
bool HashTable<K, FuncModel>::Push(const K& data)
{
	if if (_size *10 >= _capacity* 8)//載荷因子不超過0.8
	{
		HashTable<K, FuncModel> tmp(2 * _capacity + 2);
		for (size_t i = 0; i < _capacity; ++i)
		{
			if (_state[i] == EXIST)
			{
				size_t index = HashFunc(_table[i]);
				while (tmp._state[index] == EXIST)
				{
					index++;
				}
				tmp._table[index] = _table[i];
				tmp._state[index] = EXIST;
			}
		}
		Swap(tmp);
	}
	size_t index = HashFunc(data);
	while (_state[index] == EXIST)
	{
		index++;
	}
	_table[index] = data;
	_state[index] = EXIST;
	_size++;
	return true;
}


template<class K, class FuncModel = DefaultFunc<K>>
void HashTable<K, FuncModel>::Print()
{
	for (size_t i = 0; i < _capacity; ++i)
	{
		if (_state[i] == EXIST)
		{
			printf("_table[%d]:", i);
			cout << _table[i] << "->存在";
		}
		else if (_state[i] == DELETE)
		{
			printf("_table[%d]:", i);
			cout << _table[i] << "->刪除";
		}
		else
		{
			printf("_table[%d]:空", i);
		}
		cout << endl;
	}
}
template<class K, class FuncModel = DefaultFunc<K>>
bool HashTable<K, FuncModel>::Remove(const K& data)
{
	if (_size > 0)
	{
		size_t index = Find(data);
		if (index > 0)
		{
			_state[index] = DELETE;
			_size--;
			return true;
		}
		else
			return false;
	}
	return false;
}
template<class K, class FuncModel = DefaultFunc<K>>
size_t HashTable<K, FuncModel>::Find(const K& data)
{
	size_t index = HashFunc(data);
	size_t time = _capacity;
	while (time--)
	{
		if (_table[index++] == data)
		{
			return --index;
		}
		if (index == _capacity)
		{
			index = 0;
		}
	}
	return -1;
}

template<class K, class FuncModel = DefaultFunc<K>>
bool HashTable<K, FuncModel>::Alter(const K& data, const K& newdata)
{
	size_t index = Find(data);
	if (index > 0)
	{
		_state[index] = DELETE;
		if (Push(newdata))
			return true;
		else
			return false;
	}
	return false;
}

 在實(shí)現(xiàn)過程中要注意的問題有以下幾點(diǎn)：

1. 對(duì)于線性探測(cè)來說，有時(shí)候會(huì)遇到一開始探測(cè)的位置就在哈希table的最后的部分，但是因?yàn)楣_突key值被沖突到了哈希table的最前部分，所以探測(cè)到了table尾后將index置為0，簡(jiǎn)單又粗暴。

   

2. 對(duì)于對(duì)哈希表中的數(shù)據(jù)的刪除是屬于弱刪除，也就是說刪除并沒有刪除數(shù)據(jù)，只是把數(shù)據(jù)的狀態(tài)_state置為DELETE。

3. 當(dāng)載荷因子超過0.8時(shí)就得增容，載荷因子越高哈希沖突越多，不命中率越高。CPU緩存會(huì)大大升高。載荷因子a=填入表中元素的個(gè)數(shù)/散列表長(zhǎng)度。

 對(duì)代碼的兩點(diǎn)說明：

•  在這里我將模板聲明與定義分開，涉及了模板的分離編譯，對(duì)模板分離編譯還不太清楚的可以查看博主博客http://helloleex.blog.51cto.com/10728491/1769994

•  并且為了增強(qiáng)代碼的復(fù)用性，我使用了仿函數(shù)來區(qū)別調(diào)用默認(rèn)類型（基本類型，自定義類型）和string類型，使調(diào)用更加靈活

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

標(biāo)題名稱：處理哈希沖突的線性探測(cè)法-創(chuàng)新互聯(lián)
本文URL：http://aaarwkj.com/article40/pijeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、網(wǎng)站內(nèi)鏈、外貿(mào)建站、軟件開發(fā)、定制網(wǎng)站、App設(shè)計(jì)

廣告

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