通过一个哈希函数建立值与存储位置的一个对应关系，在寻找该值时，可以直接通过该函数计算得出其存储位置，而不需要像其它数据结构一样通过比较来查找。理想情况下查找的时间复杂度为o(1)。
哈希函数的构造方法有很多种，一个好的哈希函数应该让数据地址平均分布，并且避免冲突。此处通过除留余数法来构造哈希函数：
key = value % p （p不大于哈希表长度）
一个简单的哈希表构造如下：
//测试数据
const int INT_ARRAY[] = 
{43,42,45,41,46,48,47,49,40,44};
//哈希表长度
const unsigned int TABLE_LEN = 17;
//哈希函数，值除以哈希表长度的余数作为key
unsigned int Hash(int value)
{
return value % TABLE_LEN;
}
void main()
{
int len = sizeof(INT_ARRAY)/sizeof(int);
//初始化哈希表内存
int *pHash = new int[TABLE_LEN];
memset(pHash, 0, TABLE_LEN*4);
//通过哈希函数计算出每个值的key，放入哈希表中
for(int i=0; i<len; ++i)
{
unsigned int key = Hash(INT_ARRAY[i]);
if(0 == pHash[key])
pHash[key] = INT_ARRAY[i];
else
printf("collision");
}
//输出哈希表数据
for(int i=0; i<TABLE_LEN; ++i)
{
cout<<pHash[i]<<endl;
}
delete[] pHash;
}上述测试数据是连续的10个整数，它们连续的分布在长度为17的哈希表中，且无冲突。
如果选择将哈希表长度定义为10，且哈希函数中的除数为10，则更节约空间，且无冲突。
若测试的数据是随机的，则有可能出现冲突，即不同的值通过哈希函数得出的key是一样的。
解决冲突的方法有以下几种：
1、开放定址法：
若某个值在放入哈希表时发现此位置已经有数值了，则自增1，在通过哈希函数计算位置，直至没有冲突。
//测试数据
const int INT_ARRAY[] = {34,3,54,32,78,455,87,5,733,65};
//哈希表长度
const unsigned int TABLE_LEN = 17;
//哈希函数，值除以哈希表长度的余数作为key
unsigned int Hash(int value)
{
return value % TABLE_LEN;
}
void main()
{
int len = sizeof(INT_ARRAY)/sizeof(int);
//初始化哈希表内存
int *pHash = new int[TABLE_LEN];
memset(pHash, 0, TABLE_LEN*4);
//通过哈希函数计算出每个值的key，放入哈希表中
for(int i=0; i<len; ++i)
{
unsigned int key = Hash(INT_ARRAY[i]);
if(0 == pHash[key])
pHash[key] = INT_ARRAY[i];
else
{
//如果有冲突的话，将值加1，在通过哈希函数计算key，直至没有冲突
printf("conllision：%d can't be put in %u\n", INT_ARRAY[i], key);
int d = 0;
while(0 != pHash[key])
{
key = Hash(INT_ARRAY[i] + (++d));
}
pHash[key] = INT_ARRAY[i];
printf("conllision soluted：%d is put in %u\n", INT_ARRAY[i], key);
}
}
//输出哈希表数据
for(int i=0; i<TABLE_LEN; ++i)
{
cout<<pHash[i]<<endl;
}
delete[] pHash;
}2、再哈希法
当通过一个哈希函数计算的key有冲突时，再换令一个哈希函数。
3、链地址法
每个元素包含自身的value还有指向下一个value的指针，默认为NULL,当有冲突的值时，同样key的value通过该指针关联起来，且同样key的value在保存时排序。每个Key对应的链表的第一项是一个元素结构体指针（不是元素结构体，节约空间）。
//测试数据
const int INT_ARRAY[] = {34,3,54,32,78,455,87,5,733,65};
//哈希表长度
const unsigned int TABLE_LEN = 17;
//哈希表元素，
struct Element
{
int value; //值
Element* next; //指向下一个元素
};
//哈希函数，值除以哈希表长度的余数作为key
unsigned int Hash(int value)
{
return value % TABLE_LEN;
}
void main()
{
int len = sizeof(INT_ARRAY)/sizeof(int);
//初始化哈希表索引内存
int *pHash = new int[TABLE_LEN];
memset(pHash, 0, TABLE_LEN*4);
//将内存每个元素解释为Element*
Element** ppHash = (Element**)pHash;
//通过哈希函数计算出每个值的key，放入哈希表中
for(int i=0; i<len; ++i)
{
unsigned int key = Hash(INT_ARRAY[i]);
//new一个element
Element* p = new Element;
p->value = INT_ARRAY[i];
p->next = NULL;
//插入在对应的key的链表中
if(NULL == ppHash[key])
ppHash[key] = p;
else
{
//插入链表，无序
Element* pNext = ppHash[key];
while(NULL !=pNext->next)
{
pNext = pNext->next;
}
pNext->next = p;
}
}
//输出哈希表数据
for(int i=0; i<TABLE_LEN; ++i)
{
Element* p = ppHash[i];
while(NULL != p)
{
cout<<p->value<<", ";
p = p->next;
}
cout<<endl;
}
//释放每个Element
for(int i=0; i<TABLE_LEN; ++i)
{
if(NULL != ppHash[i])
{
Element* p = ppHash[i];
Element* pNext = p->next;
while(NULL != p)
{
delete p;
p = pNext;
if(NULL != pNext)
pNext = pNext->next;
}
}
}
//释放哈希表索引
delete[] pHash;
}
4、公共溢出区
将冲突的值都放入一个公共数组里。