印象

一個(gè)下標(biāo)由整數(shù)、浮點(diǎn)數(shù)甚至字符串、結(jié)構(gòu)體構(gòu)成的“數(shù)組”。

專(zhuān)業(yè)網(wǎng)站建設(shè)公司網(wǎng)站可以采用ASP、PHP、.NET編程語(yǔ)言及配備的SQL SERVER、MYSQL、ACCESSS數(shù)據(jù)庫(kù)存儲(chǔ)來(lái)整體開(kāi)發(fā)及設(shè)計(jì)各類(lèi)型大中型網(wǎng)站（包括：公司、行業(yè)門(mén)戶、醫(yī)院門(mén)戶、商城、政府門(mén)戶、音樂(lè)、視頻、交友、各行業(yè)網(wǎng)站等各種類(lèi)型網(wǎng)站），我們可以提供從網(wǎng)站開(kāi)發(fā)、網(wǎng)站設(shè)計(jì)、網(wǎng)站安全維護(hù)及網(wǎng)站托管和網(wǎng)絡(luò)推廣一條龍服務(wù)。打造高端企業(yè)網(wǎng)站設(shè)計(jì)公司，網(wǎng)站開(kāi)發(fā)周期短，質(zhì)量有保證，設(shè)計(jì)精美，價(jià)格合理。哈希函數(shù)——對(duì)應(yīng)關(guān)系的產(chǎn)生

· 對(duì)每一個(gè)key，通過(guò)映射f得到f(key)作為鍵值對(duì)(key, value)的索引，即鍵值對(duì)存放在arr[f(key)]上。
例如：將長(zhǎng)度為n的字符串s轉(zhuǎn)換為：x = s₀· 127⁰+ s₁· 127¹+ ··· + s_n· 127ⁿ，x對(duì)2⁶⁴取模得到索引。

哈希沖突

即不同的鍵值轉(zhuǎn)換后得到相同索引的情況。

解決方案一：開(kāi)散列法

將同一個(gè)索引處的多個(gè)(key, value)用鏈表儲(chǔ)存，查詢時(shí)需要掃描整個(gè)鏈表。注意，每個(gè)存放數(shù)據(jù)的地方都會(huì)開(kāi)一個(gè)鏈表。c++代碼如下：

const int SIZE = 1000000;
const int M = 999997;
struct HashTable
{//數(shù)組模擬鏈表
	struct Node
	{int next, value, key;
	} data[SIZE];
// head[M] 存放 f(key)=M 的第一個(gè)節(jié)點(diǎn)在 data 數(shù)組里的下標(biāo)，即頭結(jié)點(diǎn)的下標(biāo)
	int head[M], size;
//哈希函數(shù)
	int f(int key) {return key % M; }
//查找
	int get(int key)
	{for (int p = head[f(key)]; p; p = data[p]next)
			if (data[p].key == key) return data[p].value;
			return -1;
	}
//修改
	int modify(int key, int value)
	{for (int p = head[f(key)]; p; p = data[p]next)
			if (data[p].key == key) return data[p].value = value;
	}
//添加
	int add(int key, int value)
	{//判斷鍵值對(duì)是否已經(jīng)存儲(chǔ)過(guò)
		if (get(key) != -1) return -1;
		data[++size] = (Node){head[f(key), value, key};
		head[f(key)] = size;
		return value;
	}
};

另一種封裝好的模板代碼如下：

struct hash_map
{//前向星結(jié)構(gòu)
	struct data
	{long long u;
		int v, nex;
	};
	data e[SZ<< 1];  // SZ 是 const int，表示大小
	int h[SZ], cnt;  //cnt記錄當(dāng)前e中存入鍵值對(duì)的個(gè)數(shù)
//哈希函數(shù)，用 (u % SZ + SZ) % SZ 是為了將結(jié)果轉(zhuǎn)化為正數(shù)
	int hash(long long u) {return (u % SZ + SZ) % SZ; }
//查找，若找到則返回value，否則返回-1（不太懂這個(gè)函數(shù)的語(yǔ)法）
	int& operator[](long long u)
	{int hu = hash(u);  
		for (int i = h[hu]; i; i = e[i].nex)
			if (e[i].u == u) return e[i].v;
		return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
}
	hash_map()
	{cnt = 0;
		memset(h, 0, sizeof(h));
	}
};

解決方案二：閉散列法

把所有記錄直接存儲(chǔ)在散列表中，如果發(fā)生沖突則用某種方法（如線性探查法）繼續(xù)探查。代碼如下：

const int N = 360007;

class Hash
{private:
		int keys[N];
		int values[N];
	public:
		Hash() {memset(values, 0, sizeof(values)); }
		int& operator[](int n)
		{	int idx = (n % N + N) % N, cnt = 1;
			while (keys[idx] != n && values[idx] != 0)
			{		idx = (idx + cnt * cnt) % N;
				++cnt;
			}
			keys[idx] = n;
			return values[idx];
		}
	};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)標(biāo)題：【自學(xué)筆記001】哈希表（一）-創(chuàng)新互聯(lián)
當(dāng)前地址：http://weahome.cn/article/epede.html