HashMap结构及算法详解

澳门新葡亰手机版 3

三、懵懂的思考

还记得刚学编程不久时看《编程珠玑》,其中有一段描述:20世纪70年代,Mike
Lesk为电话公司做了电话号码查找功能,譬如输入LESK*M*对应的数字键5375*6*,可以返回正确的电话号码或可选列表,错误匹配率仅0.2%。

怎么才能做到?

当时我还完全不了解数据结构和算法,还原下当时天马行空思考的过程,现在看起来仍然是很有意思的。

如果该位置为空,生成一个新的链表节点并保存到该数组。

四、HashMap结构及算法详解

HashMap的本质依然是数组,而且是一个不定长的多维数组,近似于下图这样的结构:

澳门新葡亰手机版 1

1、简单介绍

5、数组太大

澳门新葡亰手机版,唯一的问题是,按照上述思路建立的数组实在是太大了。一个姓名有10个字母,假如每一个字母对应的数字都是9,最后得到的积约是9的17次方。这意味着要建立9^17大小的数组,这是完全不可行的。

如果该位置非空,循环比对链表的每一个节点:已经存在key相同的节点,覆盖旧节点;不存在key相同的节点,将新节点作为链表的尾节点(注:查看JDK1.8中的源码,新节点总是加入到链表末尾,而不是如JDK1.6一般作为链表头节点)

4、位置冲突

即使用改进后的乘法,不同的姓名字母计算得出的积依然还是可能会发生重复,那么当发生冲突后应该怎么办?

顺序保存到下一个空白位置?仔细想想这是行不通的。如果下一个空白位置刚好又是另外的字母集合的积,那就产生了二次冲突。

幸好,还有质数。

质数只能被1和自身整除,那么上述乘法得出的任何积都不可能是质数,所以质数位置是没有保存电话号码的。

因此,以当前积为起点向右搜索下一个质数,如果该质数位置依然被使用,那么就继续查找下一个最近的质数……

至此,问题似乎是解决了。

用户输入一串数字,根据公式计算得到积,返回该下标位置的电话号码。如果不正确,再顺序查找后面的质数,直到某个质数下标的数组元素为空为止,最后返回所有查找到的电话号码。大部分情况下,只需要O(1)的时间复杂度就可以找到电话号码。

HashMap中的数组保存链表的头节点。

2、乘法

所有数字相乘,积为381150。这似乎是可行的,但出现了这样的问题:lesk、lsek、slke……的积是一样的,每一个数字键还对应着3个字母,意味着重复的概率会很高。

计算key的hashCode,再与数组长度进行求余运算得到数组下标(链表头节点)。

1、简单介绍

HashMap中的数组保存链表的头节点。

保存数据:

计算key的hashCode,再与数组长度进行求余运算得到数组下标(链表头节点)。

如果该位置为空,生成一个新的链表节点并保存到该数组。

如果该位置非空,循环比对链表的每一个节点:已经存在key相同的节点,覆盖旧节点;不存在key相同的节点,将新节点作为链表的尾节点(注:查看JDK1.8中的源码,新节点总是加入到链表末尾,而不是如JDK1.6一般作为链表头节点)

查找数据:

计算key的hashCode,再与数组长度进行求余运算得到数组下标(链表头节点)。如果链表不为空,先比对首节点,如果首节点key相同(hashCode相同且equals为true),直接返回首节点的value;首节点key不同则顺序遍历比对链表其它节点,返回key相同的节点的value(未找到key相同的节点则返回null)。

HashMap引入链表的目的就是为了解决上一节讨论过的重复冲突问题。

注意事项:

如果所有key的hashcode相同,假定均为0,则0%4 =
0,所有元素就会都保存到链表0,保存和查找每一个数据都需要遍历链表0。那么,此时的HashMap实质上已经退化成了链表,时间复杂度也从设计的O(1)上升到了O(n/2)。

为了尽可能地让HashMap的查找和保存的时间复杂度保持在O(1),就需要让元素均匀地分布在每一个链表,也就是每一个链表只保存一个元素。

那么影响因素有哪些?

一是key的hashcode不能重复,如果重复就肯定会有链表保存至少2个元素;
二是哈希函数设计,如果只是简单的求余,那么余数会有大量重复;
三是链表的大小,如果100个元素要分布在长度为10的数组,无论怎么计算都会导致其中有链表保存多个元素,最好的情况是每个链表保存10个;

下面分别详细介绍这三个因素的算法设计。

二是哈希函数设计,如果只是简单的求余,那么余数会有大量重复;

二、二分查找

假如数组内的元素是已经排序的,那么很自然的方式就是使用二分查找。

譬如有一个整形数组的长度为1000,数组内的整数从小到大排列,如果我想要知道6000是否在此数组中。那么我可以先查看array[500]的数字是否为6000,array[500]的数字比6000小,那么就查看array[750]位置的数字……依次类推,那么最多经过10次,就可以确定结果。

此算法的时间复杂度为O(logN)。

然而,大部分情况下数组元素都是无序的,而排序所需要的时间复杂度O(NlogN)通常都远远超过遍历所需要的时间。

那么,问题又回到了原点。该如何在无序的数据中快速找到数据呢?

保存数据:

一、数组是什么?

忘了在哪本书里曾看到过类似这样的一句话“所有的数据结构都是数组的演化”,想想其实是有道理的,因为计算机的内存其实就是线性的存储空间。

Java示例代码:

int[] array = new int[5]

忽略对象头信息和数组长度信息,JVM执行时会在堆中分配20个字节的内存空间,看起来就是这样的:

澳门新葡亰手机版 2

这样的数据结构可以很方便地通过数组下标存取数据,但在查找时需要遍历数组,平均时间复杂度为O(n/2)。

当数据量很大或者查找操作频繁的时候,这样的遍历操作几乎是不可接受的。那么,如何才能够在更短的时间内快速找到数据呢?

一是key的hashcode不能重复,如果重复就肯定会有链表保存至少2个元素;

3、改进后的乘法

①字母相同但字母序不同的字符串,可以通过这样的方式来避免冲突:每一个数字先乘以序号,然后再与其它值相乘。

澳门新葡亰手机版 3

②每一个数字键对应了3个英文字母,如果用户没有输入字母在数字键中的序号,是没办法再进一步精确计算的。能考虑的方向只能是根据给定的单词表来做概率统计,所以不予考虑。

为了尽可能地让HashMap的查找和保存的时间复杂度保持在O(1),就需要让元素均匀地分布在每一个链表,也就是每一个链表只保存一个元素。