【自学笔记001】哈希表（一）-创新互联

印象

一个下标由整数、浮点数甚至字符串、结构体构成的“数组”。

专业网站建设公司网站可以采用ASP、PHP、.NET编程语言及配备的SQL SERVER、MYSQL、ACCESSS数据库存储来整体开发及设计各类型大中型网站（包括：公司、行业门户、医院门户、商城、政府门户、音乐、视频、交友、各行业网站等各种类型网站），我们可以提供从网站开发、网站设计、网站安全维护及网站托管和网络推广一条龙服务。打造高端企业网站设计公司，网站开发周期短，质量有保证，设计精美，价格合理。哈希函数——对应关系的产生

· 对每一个key，通过映射f得到f(key)作为键值对(key, value)的索引，即键值对存放在arr[f(key)]上。
例如：将长度为n的字符串s转换为：x = s₀· 127⁰+ s₁· 127¹+ ··· + s_n· 127ⁿ，x对2⁶⁴取模得到索引。

哈希冲突

即不同的键值转换后得到相同索引的情况。

解决方案一：开散列法

将同一个索引处的多个(key, value)用链表储存，查询时需要扫描整个链表。注意，每个存放数据的地方都会开一个链表。c++代码如下：

const int SIZE = 1000000;
const int M = 999997;
struct HashTable
{//数组模拟链表
	struct Node
	{int next, value, key;
	} data[SIZE];
// head[M] 存放 f(key)=M 的第一个节点在 data 数组里的下标，即头结点的下标
	int head[M], size;
//哈希函数
	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)
	{//判断键值对是否已经存储过
		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中存入键值对的个数
//哈希函数，用 (u % SZ + SZ) % SZ 是为了将结果转化为正数
	int hash(long long u) {return (u % SZ + SZ) % SZ; }
//查找，若找到则返回value，否则返回-1（不太懂这个函数的语法）
	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));
	}
};

解决方案二：闭散列法

把所有记录直接存储在散列表中，如果发生冲突则用某种方法（如线性探查法）继续探查。代码如下：

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];
		}
	};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

标题名称：【自学笔记001】哈希表（一）-创新互联
网址分享：http://shouzuofang.com/article/epede.html