散列函数五种设计方法
1.直接地址法
2.除留余数法
3.数字分析法
4.平方取中法
5，折叠法
同理：在处理不同情况时，如果有更优解的散列函数，我们也可以自己进行设计
处理冲突的方法
1.开放定址法
（1）线性探测法
（2）二次探测法
(3) 随机探测法
总结：这上面三种方法都是在同一个数组中进行处理，没有超过数组的范畴，改变的都是d的取值方式
2. 拉链法
如何理解拉链法，下面举一个例子：
3.再散列函数法
公共溢出区法
在查找时，对给定值，通过散列函数计算得出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功，如果不相等，则到溢出区进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对于查找性能来说还是非常高的 有冲突的关键字存储到溢出表的时候，是按照顺序存储的，而不是通过散列函数计算得出散列地址再进行存储，并且查找的时候也是按顺序查找
哈希表查找算法实现
代码语言：javascript复制#include<iostream>
using namespace std;
//哈希表类
#define HASHSIZE 12 //默认哈希表长度为12
#define NULLKEY -32768//没插入关键字之前，默认空关键字的大小
class HashTable
{
private:
int* elem;//动态分配哈希表数组大小
int count;//哈希表非空元素个数
int len;//哈希表长度
//散列函数----这里选择除留余数法
int Hash(int key)
{
return key % len;
}
public:
HashTable() :len(HASHSIZE), count(0)
{
elem = new int[len];//动态分配len长度大小的int数组
//初始化哈希表数组大小
for (int i = 0; i < len; i )
{
elem[i] = NULLKEY;
}
}
HashTable(int l) :len(l), count(0)
{
elem = new int[len];//动态分配len长度大小的int数组
//初始化哈希表数组大小
for (int i = 0; i < len; i )
{
elem[i] = NULLKEY;
}
}
//哈希表的插入
bool insert(int key)
{
//先判断当前哈希表数组是否已经插满
if (count == key)
return false;
//插入
//先获取散列地址
int addr = Hash(key);
//如果插入的位置不为空，则发生冲突
while (elem[addr] != NULLKEY)
{
//发生冲突后，这里选择开放定址法的线性探测
addr = (addr 1) % len;
}
//找到空位后，插入关键字
elem[addr] = key;
//元素个数加一
count ;
return true;
}
//查找关键字,查找成功返回关键字的散列地址
int searchHash(int key)
{
int addr = Hash(key);//获取查找关键字的散列地址
//如果与哈希数组中对应的散列地址存储的关键字不一样，说明需要通过线性探测法往后查找
//这里用的线性探测法要与插入时用的方法一致
while (elem[addr] != key)
{
addr = (addr 1) % len;
//如果线性探测法，发现下一个位置为空，则表示该元素不存在，因为插入的时候用的也是线性探测法，如果插入时这个位置为空，必定会在此位置插入
//第二个判断条件是因为从当前Hash(key)位置往右不断探测，当超过哈希数组本身长度后，会回到哈希数组起点开始遍历，一直重新再次回到Hash(key)位置时
//表示不存在该元素-----循环回到原点
if (elem[addr] == NULLKEY || elem[addr]==Hash(key))
{
return -1;//表示查不到
}
}
//返回对应的散列地址
return addr;
}
//释放堆区开辟的哈希数组
~HashTable()
{
delete[] elem;
}
//获取某个散列地址对应哈希数组中的元素值
int getKey(int addr)
{
return elem[addr];
}
//打印哈希数组
void display()
{
for (int i = 0; i < len; i )
cout << elem[i] << " ";
cout << endl;
}
};
//测试-------------------------
void test()
{
HashTable s(12);
s.insert(12);
s.insert(67);
s.insert(56);
s.insert(16);
s.insert(25);
s.insert(37);
s.insert(22);
s.insert(29);
s.insert(15);
s.insert(47);
s.insert(48);
s.insert(34);
cout << "哈希数组打印：" << endl;
s.display();
cout << "查找关键字47并打印输出：" << endl;
int addr=s.searchHash(47);
cout << s.getKey(addr) << endl;;
}
int main()
{
test();
system("pause");
return 0;
}
散列表性能分析
