印象

一個下標由整數(shù)、浮點數(shù)甚至字符串、結構體構成的“數(shù)組”。

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

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

哈希沖突

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

解決方案一：開散列法

將同一個索引處的多個(key, value)用鏈表儲存，查詢時需要掃描整個鏈表。注意，每個存放數(shù)據(jù)的地方都會開一個鏈表。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 的第一個節(jié)點在 data 數(shù)組里的下標，即頭結點的下標
	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)
	{//判斷鍵值對是否已經(jīng)存儲過
		if (get(key) != -1) return -1;
		data[++size] = (Node){head[f(key), value, key};
		head[f(key)] = size;
		return value;
	}
};

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

struct hash_map
{//前向星結構
	struct data
	{long long u;
		int v, nex;
	};
	data e[SZ<< 1];  // SZ 是 const int，表示大小
	int h[SZ], cnt;  //cnt記錄當前e中存入鍵值對的個數(shù)
//哈希函數(shù)，用 (u % SZ + SZ) % SZ 是為了將結果轉(zhuǎn)化為正數(shù)
	int hash(long long u) {return (u % SZ + SZ) % SZ; }
//查找，若找到則返回value，否則返回-1（不太懂這個函數(shù)的語法）
	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));
	}
};

解決方案二：閉散列法

把所有記錄直接存儲在散列表中，如果發(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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：【自學筆記001】哈希表（一）-創(chuàng)新互聯(lián)
當前網(wǎng)址：http://chinadenli.net/article14/epede.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供服務器托管、做網(wǎng)站、網(wǎng)站建設、品牌網(wǎng)站建設、網(wǎng)站策劃、建站公司

廣告

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