Hash表的理解以及实现
1. 理解
为每个要被存储的对象给定一个关键字,用一个Hash函数,把这个关键字映射到一个存储单元的地址. 这样, 在查找这个对象的时候, 只需要知道该对象的关键字. 再通过Hash函数, 便可以直接到该地址下的内存单元中去寻找所需要的数据.
但是,这当中又存在一个问题.. 对于每个不同的关键字. 通过Hash函数得到的地址是不是绝对不一样 ? 我是不知道会不会绝对不一样.. 但是数学家们说不同的关键字通过Hash函数也会有可能得到一样内存地址(胡*总说的好, 数学家说什么你就得信什么).
于是又出现一个问题: 解决Hash冲突.?
解决Hash冲突的方法:1)拉链法;
? ? ? ?2)开放定址法;
? ? ? ?3)双Hash函数法;
......
ps:(1) 拉链法: 即不同对象的关键字通过Hash函数得到的内存地址的值如果是一样的的话, 就将这两个(或多个)对象存储在一条线性链表中
?
?
?如图:{dt1,dt8}, {dt4, dt7}, {dt3, dt6, dt10}, {dt2, dt9}通过Hash函数算得的地址值是一样的, 故它们分别用一条链接起来, 可以看出, 该表中的数组里的每个元素其实是一个链表的表头.
?
(2) 开放定址法: 就是通过Hash函数算得的地址如果是一样的话, 就往该地址之后的存储空间去寻找, 只要找到有空间可以存储, 就把该数据放到该空间里存储起来 (线性探查法; 平方探查法)
?
(3) 双Hash函数法: 即给定两个Hash函数, 当通过第一个Hash函数得到的地址与其他数据地址冲突时, 将得到的值通过另外一个Hash函数再得到一个地址值, 用来尽量避免冲突.(可以扩展到多Hash函数)
?
?不难看出, 一个Hash表的存储性能与其Hash函数有着很密切的联系
而Hash函数又有多种构造方法:1) 直接定址法;
? 2) 除留余数法;
? 3) 数字分析法
? ?........;
ps: (1) 直接定址法: 就是通过各个要被存储的数据的关键字本身或者加上某个常量值作为地址(个人觉得: 如果一个Hash表通过这样的方法来构造, 我还是直接显式的用数组算了).
?
? ? ??(2) 除留余数法: 以各个数据的关键字除以某个不大于Hash表长度的数, 得到的余数作为该数据的Hash地址.
? ? ?
? ? ??(3) 数字分析法: ... ?这个就是得看具体问题了.
?
2. 实现(1):
?
首先,是Hash函数. 开始我是采用的取余的方法; 当存储的数据总量达到Map的0.75的时候,就开始扩容,每次扩大为原来的两倍. 话不多说, 上代码:
?
?
?
? 存储一百万个数据, 最后输出的结果是:
?
存储时间:2242
查找时间:0 查找到的Value值:1000000
?
?
?
?
实现(2):
?
看了下Java中HashMap的源代码, 对于以下的hash函数和indexFor函数比较有兴致(各种位运算, 觉得没兴致才怪...?好吧, 其实..之所以会想到用系统给的方法, 是因为之前在用取余数法的时候碰到了一些小问题, 导致性能低下的不能再低下, 然后就写了这个实现):
?
?
这次的存储一百万个数据输出的结果:
??存储时间:2632
? 查找时间:0 查找到的Value值:1000000
?
