哈希地址

• 哈希地址是一个逻辑地址，不是实际存在的地址，通过哈希函数得到哈希地址

哈希函数

• 哈希函数由自己决定，选什么函数都可以，假设用数组存储哈希的数据，在数组中用下标去描述位置，通过数据去构造哈希地址，地址就是数组下标

• 图中哈希结构的最大容量为 7

• 一般通过哈希构造函数把数据和下标建立联系

• 取余法得到哈希地址：数据的哈希地址 == 数据 % p(最大容量)，通过 % 7得到哈希地址

• 通过哈希构造函数，得到哈希地址 88 % 7 == 4 ，余4把它放在数组下标是4的位置 (把当前元素放到以当前哈希地址为下标的容量的位置)

• 直接定址法：数据是多少，构建出来的哈希地址就是多少，元素是 88，构建出来的哈希地址就是 88，数据就是地址，地址就是数据，图中的元素最小需要的数组长度为 89，浪费空间

• 平方取中法：把原来的数据做平方，取中间一部分

• 折叠法：把字符串转为ASCII码，是一个很大的数字，把数字折叠

哈希冲突

• 通过1个哈希函数所得到的地址可能存在重复(相同的元素)

处理哈希冲突

• 开放地址法：如果要把具有哈希冲突的元素 4 存到哈希结构中，要去数组后面找空的位置，假设数组下标为6的位置有空缺，就把 4 放在这个位置，开放地址法就是把其他空的位置去存储具有哈希冲突的元素

• 邻接表法：图的方式存储采用的就是邻接表法，不开放后面的元素，以当前位置(存在冲突的位置)去创建一个链表出来，把具有冲突的元素放在当前链表中--->以当前元素当做链表的表头去存储元素

构建数据类型

• 如果要处理的是字符串类型的数据，构造一个键出来充当哈希结构的哈希地址的求解--->关联

• 存字符串，没有整型数据，构建一个整型数据处理充当哈希结构的哈希地址的求解

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct pair 
{
	int key;			//键
	char element[20];	//数据类型--->字符串类型
}DATA,*LPDATA;

 哈希表的创建--->采用取余法

• 得到的哈希地址是用取余法来做的--->数据%p

• 通过取余法所求的哈希地址，所产生的地址个数的范围： [0，p-1]

• divisior的作用：限定哈希地址的数目 & 存储哈希元素

• 如果用结构体数组充当哈希地址，不好判断空的情况

typedef struct hashTable 
{
	LPDATA* table;	   //数据用二级指针表示 便于初始化，以及判断当前hash地址是否存在冲突
	int divisor;       //H(key)=key%p -->就是限定hash地址的数目 数据要%p需要传入p
	int curSize;	   //当前元素个数
}HASH,*LPHASH;

 哈希结构的结构体描述--->用结构体指针表示哈希结构 

LPHASH createHashTable(int p) 
{
	LPHASH hash = (LPHASH)malloc(sizeof(HASH)); //动态内存申请
	assert(hash);
    //给数据做初始化
	hash->curSize = 0;
	hash->divisor = p;
	hash->table = (LPDATA*)malloc(sizeof(LPDATA)* hash->divisor); //容量由取余数决定
	assert(hash->table);
	for (int i = 0; i < hash->divisor; i++)    //多个一级指针
	{
		hash->table[i] = NULL;                 //二级指针申请内存后给每个一级指针做初始化
	}
	return hash;
}

 插入数据

• 注意先申请内存再插入元素

• 用的是二级指针，刚刚只申请了一级指针的内存

//要插入的表 要插入的数据
void insertData(LPHASH hash, DATA data) 
{
	//做插入前先求hash地址--->调用哈希函数                  //不存在哈希冲突
	int pos = search(hash, data.key);                    //找到要存储数据的哈希地址
	if (hash->table[pos] == NULL)                        //当前下标没有数据 直接插入
	{
		hash->table[pos] = (LPDATA)malloc(sizeof(DATA)); //注意先申请内存再拷贝元素
		memcpy(hash->table[pos], &data, sizeof(DATA));   //内存拷贝
		hash->curSize++;
	}
	else                                                 //存在哈希冲突
	{
		if (hash->table[pos]->key == data.key)           //键相同回到原来位置 
		{
			strcpy(hash->table[pos]->element, data.element); //用覆盖元素的方式
		}
		else                                             //键不同回到原来位置说明满了
		{
			printf("hash表满了,无法插入!\n");             
			return;
		}
	}
}

 哈希函数 

• 可能会存在哈希冲突，需要找合适的位置去存放元素，不一定是直接取余，直接取余得到的地址不一定能用

• 传入键，通过键去找：因为是通过键去生成哈希地址

• 找完一圈后回到原来的位置(通过取余法)，说明没有合适的位置

• 如果 curPos + 1中没有元素，把元素放在当前位置即可

//要找的表 传入键
int search(LPHASH hash, int key) 
{
	int pos = key % hash->divisor;  //不存在冲突的hash地址 正常情况
	int curPos = pos;               //存在冲突 开放地址法做哈希地址的查找
	do 
	{
		//key相同，采用覆盖的数据方式 不当做哈希冲突来做
		if (hash->table[curPos] == NULL||hash->table[curPos]->key==key)
			return curPos;          //判断当前位置能不能用 ==NUll说明可以用
		curPos=(curPos + 1)%hash->divisor; //不为NULL往后走 如果后面为NULL就插到当前位置
	} while (curPos != pos);        //当前Pos不等于原来Pos就一直去做查找
	return curPos;                  
}
//!= 原来地址一直做查找 
//== 原来地址:找完一圈后回到原来的位置说明它没有合适的位置 直接返回

打印哈希表--->打印数组

void printHash(LPHASH hash) 
{
	for (int i = 0; i < hash->divisor; i++) //用最大容量长度做打印
	{
		if (hash->table[i] == NULL) 
		{
			printf("NULL\n");
		}
		else                                //不为空打印元素
		{
			printf("%d:%s\n", hash->table[i]->key, hash->table[i]->element);
		}
	}
}

 测试代码

int main() 
{
	LPHASH hash = createHashTable(10);     //创建哈希表
	DATA array[5] = { 1,"雷电",11,"春天",23,"四月",44,"baby",56,"virtual" };
	for (int i = 0; i < 5; i++) 
	{
		insertData(hash, array[i]);        //把数据插到哈希表中
	}
	printHash(hash);                       //打印哈希表
	return 0;
}
//测试代码

NULL
1:雷电
11:春天
23:四月
44:baby
NULL
56:virtual
NULL
NULL
NULL

哈希结构

哈希概念

常见的K-V结构，实现了元素关键码与元素值的映射关系，但没有实现元素关键值与元素存储位置的映射关系，在遍历过程中，一般的顺序表或搜索二叉树要进行关键值的多次比较，其中顺序表的时间复杂度为O(n),二叉搜索树的时间复杂度O(lgn)

对此希望找到一种理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

哈希函数

常见哈希函数
1. 直接定制法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况 
2. 除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

哈希操作

• 插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

• 搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

• 删除元素

根据待删除元素的关键码，以此函数计算出该元素的存储位置并按此位置进行删除

• 哈希冲突解决

• 闭散列（线性探测法）

哈希表结构：在闭散列中，将哈希表底层结构设置为vector容器，容器中每一个元素为一个hashNode结构体，包括kv键值对和状态标志位

初始化将其hashNode的状态设置为空

template <class k,class v>
struct HashNode
{
	pair<k, v> kv;
	STATE state = EMPTY;
};

template <class k, class v>
class HashTable
{
public:
	typedef HashNode<k, v> Node;
	HashTable(size_t n = 10)
		:HSTable(n)
		,_size(0)
	{
	}
private:
	vector<Node> HSTable;
	size_t _size;
};

上述插入操作，可能会产生哈希冲突，通过线性探测法，从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，插入一个新元素

在查找过程值，要想找到发生冲突元素，就必须给标志位

删除也类似，采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

enum STATE{
	EXIST  //已存在
	,DELETE  //删除过
	,EMPTY   //空位置
};

通过定义一个枚举类型，包括已存在不可插入状态（EXIST），空位置可插入状态(EMPTY)，删除过的位置状态(DELETE)

插入代码如下：

	bool insert(const pair<k, v>& kv)
	{
		checkcapacity();
		//计算hash位置
		int idx = kv.first%HSTable.size();
		//搜索
		while (HSTable[idx].state != EMPTY)//其余两种状态都需要继续查找
		{
			//当前位置已经有数据，且与要插入新数据相同，则插入失败
			if (HSTable[idx].state ==EXIST&& kv.first == HSTable[idx].kv.first)
				return false;
			++idx;
			if (idx == HSTable.size() - 1)//向后查找过程到结尾 从头再开始找空位
				idx = 0;
		}
		//此时找到空位置,插入新元素，状态置为已存在，hash表大小+1
		HSTable[idx].kv = kv;
		HSTable[idx].state = EXIST;
		_size++;
		return true;
		//插满扩容
		
	}

由于插入过程实际上是在vector容器基础上完成，如果需要插入元素足够多，可能导致当前所创造的哈希表插满，此时就需要检查容量，进行扩充操作

扩容判断条件是：负载因子>0.7,此时认为产生冲突的可能性大，需要进行扩容

扩容并非在原表基础上增大size，而是开辟新表，将原表已存在状态位置元素进行逐一存放，代码如下：

void checkcapacity()
	{
		//负载因子控制是否增容
		//负载因子越小，冲突越小，但空间浪费越大
		if (HSTable.size()==0&&_size * 10 / HSTable.size() > 7)
		{
			//开新表
			int newcap = HSTable.size() == 0 ? 10 : 2 * HSTable.size();
			HashTable<k, v> newHST(newcap);
			//直接拷贝会导致hash值计算前后不一致
			//需要重新计算hash位置
			for (int i = 0; i < HSTable.size(); i++)
			{
				if (HSTable[i].state == EXIST)
				{
					newHST.insert(HSTable[i].kv);
				}
			}
			swap(newHST);
		}
	}
	void swap(HashTable<k, v>& HT)
	{
		swap(HSTable,HT.HSTable);
		swap(_size, HT._size);
	}

查找：由于hash冲突，直接通过索引查找难以找到发生hash冲突而通过线性探测法存放的元素，非空位置逐一查找，如果索引超过了表大小，需要循环从头开始

Node* find(const k& key)
	{
		//计算hash位置
		int idx = key%HSTable.size();
		//搜索
		while (HSTable[idx].state != EMPTY)
		{
			if (HSTable[idx].state == EXIST && key == HSTable[idx].first)
				return &HSTable[idx];
			++idx;
			if (idx == HSTable.size() - 1)
				idx = 0;
		}
		return nullptr;
	}

删除：删除并非真删除，释放元素，而是改变对应元素位置状态信息

bool erase(const k& key)
	{
		Node* node = find(key);
		if (node)
		{
			node->state = DELETE;
			_size--;
			return true;
		}
		return false;
	}

• 开散列（哈希桶）

首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

bool insert(const V& val)
	{
		checkcapacity();
		KeyofValue kov;
		int idx = kov(val) % _hst.size();

		//查找
		Node* cur = _hst[idx];
		while (cur)
		{
			if (kov(cur->_val) == kov(val))
			{
				//key重复
				return false;
			}
			cur = cur->_next;
		}
		//插入  头插
		cur = new Node(val);
		cur->_next = _hst[idx];
		_hst[idx] = cur;
		_size++;
		return true;
	}

哈希桶通过建立新连接进行扩容操作：

void checkcapacity()
	{
		if (_size == _hst.size())
		{
			int newcap = _size == 0 ? 10 : 2 * _size;
			vector<Node*> newhst(newcap);
			KeyofValue kov;
			for (int i = 0; i < _hst.size(); i++)
			{
				Node* cur = _hst[i];
				while (cur)
				{
					Node* next = cur->_next;
					int idx = kov(cur->_val) % newhst.size();
					//新表头插
					cur->_next = newhst[idx];
					newhst[idx] = cur;

					cur = next;
				}
				//原表断开 置空
				_hst[i] = nullptr;
			}
			swap(_hst,newhst);
		}
	}

• 迭代器操作：

迭代器的++步骤：

#include<iostream>
#include<vector>
using namespace std;

template <class V>
struct HashNode
{
	V _val;
	HashNode<V>* _next;

	HashNode(const V& val)
		:_val(val)
		,_next(nullptr)
	{

	}
};

//hash表的前置声明
template<class K, class V, class KeyofValue>
class HSTable;


//hash表迭代器  封装单链表节点
template<class K, class V, class KeyofValue>
struct HashIterator{
	typedef HashNode<V> Node;
	typedef HSTable<K, V, KeyofValue> ht;
	typedef HashIterator<K, V, KeyofValue> Self;
	//成员：节点指针，哈希表指针
	Node* _node;
	ht* _hptr;

	HashIterator(Node* node,ht* hptr)
		:_node(node)
		,_hptr(hptr)
	{

	}

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		//找下一个非空链表头结点
		else
		{
			//计算当前节点在hash表中位置
			KeyofValue kov;
			int idx = kov(_node->_val) % _hptr->_hst.size();
			//从下一位置开始查找
			++idx;
			for (int; idx < _hptr->_hst.size(); idx++)
			{
				if (_hptr->_hst[idx])
				{
					_node = _hptr->_hst[idx];//找到非空链表头结点给node记录
					break;
				}
			}
			if (idx = _hptr->_hst.size())//此时走到end位置  将node节点置为空
			{
				_node = nullptr;
			}
		}
		return *this;
	}
};



template<class K,class V,class KeyofValue>
class HSTable
{
public:
	typedef HashNode<V> Node;
	typedef HashIterator<K, V, KeyofValue> iterator;

	//由于迭代器需要访问其私有成员_hst  声明为友元类
	friend HashIterator<K, V, KeyofValue>;
	HSTable(int n=10)
		:_hst(n)
		,_size(0)
	{

	}

	iterator begin()
	{
		for (int i = 0; i < _hst.size(); i++)
		{
			if (_hst[i])
			{
				return iterator(_hst[i], this);
			}
			else
				return iterator(nullptr,this);

		}
	}
	iterator end()
	{
		return iterator(nullptr, this);
	}


private:
	vector<Node*> _hst;
	int _size;
};

哈希表的应用

• 位图

位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

比如Tencent的一道面试题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中

此题解法较多，一般容易想到的就是暴力求解，直接遍历查询，但海量数据导致时间复杂度过大，无法实际中应用；稍微进阶一些的会想到采用二分查找，虽然相比较于直接遍历，把时间复杂度从O(n)提升到O(lgn)，但对于40亿数据还是难以实现

而通过位图可以实现：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

代码实现如下：

#include<iostream>
#include<vector>
using namespace std;

/*
位图应用：
（1）存放不重复数据简单信息，不需要存放数据本身   优点：节省空间，查找效率高

*/
class bitset
{
public:
	//位图内存大小与数据范围有关
	bitset(size_t range)
		:_bit(range/32+1)
	{

	}
	//存储信息
	void set(size_t num)
	{
		//计算整数位置
		int idx = num / 32;
		//计算比特位置
		int bitidx = num % 32;
		//对应比特位置1  按位或运算
		_bit[idx] |= (1 << bitidx);  //把1向左移动bixidx位置  或运算之后  将其置为1
	}
	//查找信息
	bool test(size_t num)
	{
		//计算整数位置
		int idx = num / 32;
		//计算比特位置
		int bitidx = num % 32;
		//对应比特位右移bitidx后 与1 与运算  如果为1 则为1  否则为0
		return (_bit[idx] >> bitidx)&1;		
	}

	//删除信息
	void reset(size_t num)
	{
		//计算整数位置
		int idx = num / 32;
		//计算比特位置
		int bitidx = num % 32;
		//对应比特位置10
		_bit[idx] &= ~(1 << bitidx);
	}
private:
	//数组
	vector<int> _bit;
	//默认bit位个数为 32 位
};

• 布隆过滤器

布隆过滤器是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

布隆过滤器的实现依然需要借助位图的实现来完成，依然依靠0-1进行标记数据是否存在

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

• 查找：

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

• 删除：

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

代码如下：

//布隆过滤器
// 假设布隆过滤器中元素类型为K，每个元素对应3个哈希函数
template<class T, class KToInt1, class KToInt2,class KToInt3>
class BloomFilter
{
public:
	BloomFilter(size_t size) // 布隆过滤器中元素个数
		: _bmp(3 * size), _bitcount(3 * size)
	{}

	//存储信息：使用多个bit位存储
	void set(const T& val)
	{
		KToInt1 k1;
		KToInt2 k2;
		KToInt3 k3;
		int idx1 = k1(val) % _bitcount;
		int idx2 = k2(val) % _bitcount;
		int idx3 = k3(val) % _bitcount;
		
		_bmp.set(idx1);
		_bmp.set(idx2);
		_bmp.set(idx3);
	}

	bool test(const T& val)
	{
		KToInt1 k1;
		KToInt2 k2;
		KToInt3 k3;
		int idx1 = k1(val) % _bitcount;
		int idx2 = k2(val) % _bitcount;
		int idx3 = k3(val) % _bitcount;

		if (!_bmp.test(idx1))
			return false;//三个有一个为0 肯定不存在  三个均为1  可能存在（不能说一定存在）
		if (!_bmp.test(idx2))
			return false;
		if (!_bmp.test(idx3))
			return false;
		if (_bmp.test(idx1) && _bmp.test(idx2) && _bmp.test(idx3))
			return true;
	}
private:
	bitset _bmp;
	size_t _bitcount; // bit位的个数
};

struct KToInt1
{
	//hash函数计算方式1  
};

struct KToInt2
{
	//hash函数计算方式2 
};

struct KToInt3
{
	//hash函数计算方式3 
};
void test()
{
	BloomFilter<string, KToInt1, KToInt2, KToInt3> bf(10);
}

 

是时候说说哈希结构了。记得以前被人问过哈希结构，问题是：哈希结构最差效率是发生在什么时候？这个问题其实没太多意义，一般只有大学论文喜欢研究这种问题，因为在现实工程中，除非故意或者写错代码才有可能发生最差的效率情况。这篇文章将把哈希结构（我所理解的）来个大起底，照遍哈希结构的各个角落，最后，给出自己的哈希结构类。

 

一步步开始吧。

l  为什么要有哈希结构？

大学老师最喜欢的事情就是照本宣科，很少老师（甚至程序员）会问为什么有这种数据结构。知道为什么有哈希结构有助于知识连贯性和理解。

那么为什么会有哈希结构呢？在学哈希结构的之前，基本都会先接触树，二叉树，平衡二叉树最后到红黑树，这些数据结构时而为了排序用，时而用来查找用。就我所知，红黑树就主要用于存储结构，方便快速查询存储中的数据。那么作为后续的哈希结构，其主要是更强更快的查询，设计哈希的目的，是为了能尽量逼近O(1)时间的查询。

 

l  哈希的思想

为了尽量逼近O(1)时间查询，设想查询数据时如同取数组元素一样直接使用数组下标取到数组元素：

Value = Array[key];

这个时候就是O(1)时间。因此哈希的主要思想就是：将查找值转为数组下标值，一般来说就是整型int。这个转化过程就是哈希函数，哈希函数是哈希结构效率的核心，越是能将转化后得到的数组下标值均匀的分散在数组各个地方的哈希函数，查找时间越是逼近O(1)。

为什么只是逼近O(1)而不是O(1)呢？理论上是可以做到O(1)的，但说查找，研究查找，只有超大型数据才有意义，但在有限的数组大小情况下，按O(1)标准存储完所有数据几乎不可能，比如设计一个哈希函数将英文单词转为数组下标int型，若设计一个26（26个字母嘛）进制的数据类型，10个字母长度的单词经过哈希函数转化后得到的整型数据已经是很大的数据了，已经放不下了。

因此，哈希允许有冲突。所谓冲突，就是两个不同的查询数据，经过哈希函数转化后，其数组下标值是一样的，也就是说他们都想放到数组的同一个位置上。

解决冲突的方法一般有两种：

1.        链表法；这个是最最常用的方法，简单也最实用。当发生冲突时，就用一个链表连在发生冲突的位置上，后续冲突的数据都挂在链表上。

2.        线性探测法；当发生冲突时把冲突元素放到下一个相邻位置，若仍然冲突（即下一个位置已经被霸占），则继续找下一个位置。这种方法实现复杂，最重要的是相比第一种，效率比较低，因为发生随着发生冲突的次数增多，数组最终被填满，这个时候必须重新申请一个更大的数组，一般其情况下，为了保证效率，当填入的数据个数达到数组大小的一半时，就要重新生成更大的数组了。

其实还有第三种处理冲突的方法，就是二次哈希，也就是说，发生冲突的时候就用另一个哈希函数算出数组下标值，放到另一个哈希结构中。

说到这，开篇的问题已经有答案了，若哈希函数完全无法将查找数据区分成均匀的数组下标，全部统统冲突在同一个位置，这个时候，哈希结构就会退化为一根链表（或简单的数组），查询的时间就会变成O(N)。

 

l  如何设计哈希函数

哈希函数必须保证生成的数组下标能均匀分散，一般采取的方法是取模法。取模的原理很简单，就是把查询值转成整型后对某个整数取模。这个整数，就是哈希结构里面的数组大小。根据一些学术论文的统计，这个整数最好是素数，这个时候区分度更好，并且，其越大，区分度也越好。

 

现在，就开始写一个自己的哈希结构。这个结构是基于链表法解决冲突的，这个方法是最简单也是最实用的。

template <class Key, class Value, class F>
class CListHash

Key就是查询关键字，Value就是对应需要查找的值，F是哈希函数类。F这个类应该提供operator()()函数，在CListHash类里面使用这个函数类对象计算哈希值：

class CGetHashCode{
public:
	int operator()(const int M, const std::string& strWord){
		int iSum = 0;
		for (std::string::const_iterator iter = strWord.begin(); iter != strWord.end(); ++iter){
			char c;
			if (*iter >= 'A' && *iter <= 'Z'){
				c = *iter - 'A' + 'a';
			}else{
				c = *iter;
			}
			iSum |= 1 << (c - 'a');
		}

		return iSum % MODE;
	}
};

这个只是对F模板的一个具体演示，CGetHashCode这个类中operator()()函数接受M和一个string类，其目的是为了将一个单词转为数组下标，即索引值。这个算法是我自己想出来的，和一般的技术书籍方法不一样，其思想就是按字母表的顺序将一个int（32位）中相应的位设为1，例如b是字母表的第二个字母，则对int的第二位设置为1，最后对M取模。这个时候，当M足够大时，冲突只会发生在字母集一样顺序不一样的单词中（包含重复字母），例如：read，dear和dare。不知道这样的冲突率算不算高，我没进行统计。这里只是演示哈希结构。

在CListHash中我自己写了一个链表的节点类，并实现了自己的链表，这个当然不打算使用STL的东西：

struct ValueNode{
		Value* valueArray;
		Key k;
		int N;
		int current;
		ValueNode* pNext;

		ValueNode():valueArray(NULL), pNext(NULL), N(0), current(-1){

		}
		~ValueNode(){
			delete[] valueArray;
		}

		void put(const Value& v){
			if (0 == N){
				N = 1;
				current = 0;
				valueArray = new Value[N];
				valueArray[current] = v;
			}else{
				if (current + 1 == N){
					N *= 2;
					Value* newValueArray = new Value[N];
					for (int i = 0; i <= current; ++i){
						newValueArray[i] = valueArray[i];
					}
					delete[] valueArray;
					++current;
					newValueArray[current] = v;
					valueArray = newValueArray;
				}else{
					++current;
					valueArray[current] = v;
				}
			}
		}

		void remove(const Value& v){
			for (int i = 0; i <= current; ){
				if (v == valueArray[i]) {
					for (int j = i; j < current; ++j){
						valueArray[j] = valueArray[j + 1];
					}
					--current;
				}else{
					++i;
				}
			}
		}
	};

这个节点类，和vector类似，当往里面存值时，会按2的倍数增长（vector不是按2的倍数增长，但肯定会增长很多）。

之所以不用STL，首先STL是一个通用库，为了兼顾各种用途，会损失效率，我想，简单代码一般会比兼顾各种情况的复杂代码效率会高点的，更重要的是，可以锻炼自己最基本的写代码能力。

这个类实际上是写在CListHash里面的，声明为private，外部无法访问。

const int m_iBufferSize;
ValueNode** m_Buffer;

其实就是一个动态的数组，数组大小正是之前所说的M，同样是private属性。数组存放每个索引的第一个链表节点。

外部遍历每个Key值对应的Value，这个就是遍历类：

public:
	class Iterator{
		Value* m_pValues;
		friend class CListHash;
	public:
		Iterator():m_pValues(NULL){

		}

		Iterator(const Iterator& iter):m_pValues(iter.m_pValues){

		}

		Iterator& operator++(){
			++m_pValues;
			return *this;
		}

		Value operator++(int){
			Iterator newIter(*this);
			++m_pValues;
			return newIter;
		}

		const Value& operator*(){
			return *m_pValues;
		}

		bool operator==(const Iterator& other){
			return m_pValues == other.m_pValues;
		}

		bool operator!=(const Iterator& other){
			return m_pValues != other.m_pValues;
		}
	};

接下来就是哈希结构的实现了：

public:
	CListHash(const int size):m_iBufferSize(size){
		m_Buffer = new ValueNode*[m_iBufferSize];
		for (int i = 0; i < m_iBufferSize; ++i){
			m_Buffer[i] = NULL;
		}
	}

	void put(const Key& k, const Value& v){
		int iIndex = F()(m_iBufferSize, k);
		if (NULL == m_Buffer[iIndex]){
			m_Buffer[iIndex] = new ValueNode();
			m_Buffer[iIndex]->put(v);
			m_Buffer[iIndex]->k = k;
		}else{
			ValueNode* p;
			ValueNode* pre;
			for (p = m_Buffer[iIndex], pre = m_Buffer[iIndex];
					NULL != p;
					pre = p, p = p->pNext){
				if (k == p->k){
					break;
				}
			}
			if (NULL != p){
				p->put(v);
			}else{
				pre->pNext = new ValueNode();
				pre->pNext->put(v);
				pre->pNext->k = k;
			}
		}
	}

	bool get(const Key& k, Iterator& begin, Iterator& end){
		int iIndex = F()(m_iBufferSize, k);

		for (ValueNode* p = m_Buffer[iIndex]; NULL != p; p = p->pNext){
			if (k == p->k){
				begin.m_pValues = p->valueArray;
				end.m_pValues = p->valueArray + p->current + 1;
				return true;
			}
		}

		return false;
	}

	void removeKey(const Key& k){
		int iIndex = F()(m_iBufferSize, k);
		ValueNode* pre = NULL;
		for (ValueNode* p = m_Buffer[iIndex]; NULL != p; pre = p, p = p->pNext){
			if (k == p->k){
				if (NULL == pre){
					m_Buffer[iIndex] = p->pNext;
					delete p;
					break;
				}else{
					pre->pNext = p->pNext;
					delete p;
					break;
				}
			}
		}
	}

	void removeValue(const Key& k, const Value& v){
		int iIndex = F()(m_iBufferSize, k);
		for (ValueNode* p = m_Buffer[iIndex]; NULL != p; p = p->pNext) {
			if (k == p->k){
				p->remove(v);
				break;
			}
		}
	}

实现还是很简单的，哈希的效率是体现在哈希函数的设计上，而不是具体数据结构上。

以下是测试代码：

#include "ListHash.h"
#include <iostream>
#include <string>
#include <Windows.h>
#include <set>
#include <assert.h>

bool isAlpha(const char c){
	if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')){
		return true;
	}
	return false;
}

// 0x2fffffff
const int MODE = 102131;//12287

struct Position{
	int iLine;
	int iIndex;
};

class CGetHashCode{
public:
	int operator()(const int M, const std::string& strWord){
		int iSum = 0;
		for (std::string::const_iterator iter = strWord.begin(); iter != strWord.end(); ++iter){
			char c;
			if (*iter >= 'A' && *iter <= 'Z'){
				c = *iter - 'A' + 'a';
			}else{
				c = *iter;
			}
			iSum |= 1 << (c - 'a');
		}

		return iSum % MODE;
	}
};

int main(){
	HANDLE hFile = CreateFileA("Alice.txt",
								GENERIC_READ,
								FILE_SHARE_READ,
								NULL,
								OPEN_EXISTING,
								FILE_ATTRIBUTE_NORMAL,
								NULL);
	if (INVALID_HANDLE_VALUE == hFile){
		std::cerr << "cannot get vailid file handle" << std::endl;
		return 1;
	}

	typedef CListHash<std::string, Position*, CGetHashCode> SearchHash;
	SearchHash hash(MODE);
	typedef std::set<std::string> SetTest;
	SetTest setTest;

	const DWORD dwMustRead = 4 * 1024;// 4k
	char cRead[dwMustRead];
	DWORD dwHasRead;
	BOOL bReadEnd;
	std::string strWord;
	int iLine = 0, iIndex = 0;
	bool bNewWord = false;
	while (TRUE){
		bReadEnd = ReadFile(hFile, (LPVOID)cRead, dwMustRead, &dwHasRead, NULL);
		if (0 == dwHasRead){
			break;
		}
		for (DWORD d = 0; d < dwHasRead; ++d){
			if (isAlpha(cRead[d])){
				bNewWord = true;
				strWord += cRead[d];
			}else{
				if (bNewWord){
					Position* p = new Position();
					p->iLine = iLine;
					p->iIndex = iIndex;
					hash.put(strWord, p);
					setTest.insert(strWord);
					strWord.clear();
					++iIndex;
					bNewWord =false;
				}
				if ('\n' == cRead[d]){
					++iLine;
				}
			}
		}
	}

	// dump
	hash.dump();

	for (SetTest::iterator iter = setTest.begin(); iter != setTest.end(); ++iter) {
		SearchHash::Iterator begin;
		SearchHash::Iterator end;
		if (hash.get(*iter, begin, end)){
			std::cout << *iter << "->";
			while (begin != end) {
				Position* position = *begin;
				std::cout << "(" << position->iLine << ", " << position->iIndex << ") ";
				delete position;
				++begin;
			}
			std::cout << std::endl;

			hash.removeKey(*iter);
		}

		assert(!hash.get(*iter, begin, end));
	}

	hash.dump();

	Position* position = new Position;
	position->iIndex = 1998;
	position->iLine = 2007;
	hash.put("test", position);

	position = new Position;
	position->iIndex = 30;
	position->iLine = 29;
	hash.put("jack", position);

	position = new Position;
	Position * pToBeDeleted = position;
	position->iIndex = 2013;
	position->iLine = 2015;
	hash.put("test", position);
	hash.put("test", position);

	position = new Position;
	position->iIndex = 8888;
	position->iLine = 3333;
	hash.put("test", position);

	hash.removeValue("test", pToBeDeleted);

	SearchHash::Iterator begin;
	SearchHash::Iterator end;
	if (hash.get("test", begin, end)) {
		std::cout << "********** test ****************" << std::endl;
		while (begin != end) {
			assert(pToBeDeleted != *begin);
			Position* p = *begin;
			std::cout << "(" << p->iLine << ", " << p->iIndex << ") ";
			++begin;
		}
		std::cout << std::endl;
	}

	CloseHandle(hFile);

	return 0;
}

测试是给一本名叫《爱丽丝梦游仙境》的小说中的所有单词建立索引，同时测试CListHash各个函数是否正常工作。可能有人问为什么没有遍历函数，仅仅提供遍历结果的函数，若想遍历当中的所有Key值呢？我是这么想的，哈希的存在不为排序，也不为存储，仅仅为快速查找，因此，我没有提供对Key值的遍历，仅提供了Key对应的Value值遍历函数，更不会有任何排序设计。哈希仅为查找而存在（实际上哈希结构还可以用来描述图，以后再说）。

我也没有实现operator[]这看上去直观的函数符重载，因为看上去直观，却有左右值的困惑。若operator[]返回临时对象，则无法用做左值，效率亦不高，operator[]若返回引用则内部需要new，这么做毫无意义。