哈希表的实现_哈希查表算法 verilog

哈希表的几个概念：

映像：由哈希函数得到的哈希表是一个映像。

冲突：如果两个关键字的哈希函数值相等，这种现象称为冲突。

建立哈希表是为了消除通过遍历比较来搜索键带来的时间浪费。

如果想在一个表中直接地找到记录，记录的存储位置和它的关键字之间建立一个确定的对应关系f()，使每个关键字和结构中一个唯一的存储位置相对应。这便是哈希表的快速查找原理。

哈希表的构造方法(即寻找键和结构数组间的函数关系)有：ASCII转换直接相加法，取模法(表长为质数较优)，平方取中法，拆项法，折叠法，随机数法等。

处理冲突的几个方法：

1、开放地址法：用开放地址处理冲突就是当冲突发生时，形成一个地址序列，沿着这个序列逐个深测，直到找到一个“空”的开放地址，将发生冲突的关键字值存放到该地址中去。例如：hash(i)=(hash(key)+d(i)) MOD m (i=1,2,3,......,k(k<m-1)) d为增量函数，d(i)=d1,d2,d3,...,dn-1根据增量序列的取法不同，可以得到不同的开放地址处理冲突探测方法。有线性探测法、二次方探测法、伪随机探测法。

2、链地址法：把所有关键字为同义词的记录存储在一个线性链表中，这个链表成为同义词链表，即把具有相同哈希地址的关键字值存放在同义链表中。

3、再哈希表：费时间的一种方法。

由于哈希函数和哈希表冲突的处理方法是哈希表效率的关键，所以一定要根据不同应用场合慎重选择。 搜索哈希表的时间复杂度与记录数n无关，所以适合处理记录数量很大的数据。