HashMap分析 + 哈希表

时间:2021-12-06 22:30:00

http://www.cnblogs.com/hzmark/archive/2012/12/24/HashMap.html

http://www.cnblogs.com/xqzt/archive/2012/12/28/5637128.html

数据结构---->哈希表

一、哈希表

哈希表又称散列表。哈希表存储的基本思想是:以数据表中的每个记录的关键字k为自变量,通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间(即数组空间)的单元地址(即下标),将该记录存储到这个单元中。在此称该函数H为哈希函数或散列函数。按这种方法建立的表称为哈希表或散列表。

例如,要将关键字值序列(3,15,22,24),存储到编号为0到4的表长为5的哈希表中。 计算存储地址的哈希函数可取除5的取余数算法H(k)=k% 5。则构造好的哈希表如图所示。

HashMap分析 + 哈希表

理想情况下,哈希函数在关键字和地址之间建立了一个一一对应关系,从而使得查找只需一次计算即可完成。由于关键字值的某种随机性,使得这种一一对应关系难以发现或构造。因而可能会出现不同的关键字对应一个存储地址。即k1≠k2,但H(k1)=H(k2),这种现象称为冲突。把这种具有不同关键字值而具有相同哈希地址的对象称“同义词”。

在大多数情况下,冲突是不能完全避免的。这是因为所有可能的关键字的集合可能比较大,而对应的地址数则可能比较少。

对于哈希技术,主要研究两个问题:

(1)如何设计哈希函数以使冲突尽可能少地发生。

(2)发生冲突后如何解决。