首页 > 代码库 > 哈希表

哈希表

         哈希表

 

         我们储存数据有没有面临1~1亿 随机存有1W (不等)个数的时候呢?

         这时候如果直接储存就有可能造成大量内存的浪费。

         这时就需要一个算法将地址压缩至1W 的范围。

         平时如果直接储存的话可能觉得直接用个什么 index 依次++ 不就好了吗。

         是啊,但是这里还面临查找的问题。

         所以就需要利用hash函数来查找记录的地址了。

 

         Hash 函数的一种方法是对哈希表长度进行取模,那么这时有会有所得数字相等的情况,但你一个地址不能存放两个值啊,这就被称为冲突。

           这种情况是一种理想情况。

 

         构造哈希函数有不同的构造方法:

一 :直接定值法

         如果本身数据是基本连续的,那么可以用  这样的形式来寻求地址。但如果数据有大量的不连续分布就将造成内存的浪费。

二 :除留余数法

         取关键字 k 处以哈希表长度m 来计算地址。即  。

         这是一种较简单、常用的方式。关键是选好长度m 尽量避免冲突的产生,研究表明m 取值为素数时,冲突较少。

三 :平方取中法

         即取关键字平方后的中间几位数作为哈希表的地址(可取模)

         例如

四 :折叠法

         将关键字分隔成位数相同的几部分,用这几部分的和作为哈希表的地址。适用于位数较多的情况,如身份证号。

五 :数值分析法

         顾名思义,找规律,发现数据之间的玄学奥秘。(厉害的不行)

         如:观察得数据的某几位取值较为集中,取不集中的几位组成数字作为地址。

        

 

         以上就是几种构造哈希函数的方法。

         那么之前有提到有冲突产生,怎样解决呢?

         处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。即通过一个新的哈希函数得到一个新的哈希地址。如果仍然发生冲突,则再求下一个,依次类推。直至新的哈希地址不再发生冲突为止。

常用的处理冲突的方法有开放地址法、链地址法两大类。

 

一 :开放地址法

          

 

         其中又有

(1)    线性探测 :    (最坏为(1+m)* m / 2)

(2)    平方探查 :  

二 :链地址法

         把所有关键字为同义词的记录存储在一个线性链表中,这个链表称为同义词链表。并将这些链表的表头指针放在数组中(下标从0到m-1)。这类似于图中的邻接表和树中孩子链表的结构。

        

哈希表