Java 배열부터 HashMap까지의 알고리즘에 대한 자세한 소개-java지도 시간-php.cn

1. 배열이란?

어떤 책에서 "모든 데이터 구조는 배열의 진화이다"라는 문장을 본 적이 있습니다. 컴퓨터의 메모리는 실제로 선형적인 저장 공간이기 때문에 생각해보면 실제로 의미가 있습니다.

Java 샘플 코드:

int[] array = new int[5]

로그인 후 복사

object 헤더 정보와 배열 길이 정보를 무시합니다. JVM은 실행 시 힙에 20바이트의 메모리 공간을 할당합니다. like 이렇습니다:

이러한 데이터 구조는 배열 첨자를 통해 쉽게 데이터에 액세스할 수 있지만 검색 시 평균적으로 배열을 순회해야 합니다. 시간 복잡도는 O(n/2)입니다.

데이터의 양이 많거나 검색 작업이 빈번한 경우 이러한 순회 작업은 거의 허용되지 않습니다. 그렇다면 어떻게 하면 더 짧은 시간에 빠르게 데이터를 찾을 수 있을까요?

2. 이진 검색

배열의 요소가 정렬되어 있으면 자연스러운 방법은 이진 검색을 사용하는 것입니다.

예를 들어 길이가 1000인 정수형 배열이 있고 그 배열의 정수가 작은 것부터 큰 것 순으로 배열되어 있다면 여기에 6000이 있는지 알고 싶다면 정렬. 그런 다음 먼저 배열[500]의 숫자가 6000인지 확인할 수 있습니다. 배열[500]의 숫자가 6000보다 작은 경우 배열[750]의 위치에 있는 숫자를 확인하고... 그런 다음 계속합니다. 최대 10회까지 결과를 확인할 수 있습니다.

이 알고리즘의 시간 복잡도는 O(logN)입니다.

그러나 대부분의 경우 배열 요소는 순서가 지정되지 않으며 정렬에 필요한 시간 복잡도 O(NlogN)는 일반적으로 순회에 필요한 시간을 훨씬 초과합니다.

그래서 문제는 다시 원점으로 돌아간 것입니다. 무질서한 데이터에서 데이터를 빠르게 찾는 방법은 무엇입니까?

3.무식한 생각

처음 프로그래밍을 배웠던 때가 아직도 기억난다. 얼마 전 <프로그래밍 펄스>를 봤는데 거기에 설명이 있었다. 1970년대 Mike Lesk는 전화기였습니다. 회사에서는 전화번호 검색 기능을 구현했습니다. 예를 들어 LESK*M*에 해당하는 숫자키 5375*6*을 입력하면 올바른 전화번호 또는 옵션 목록이 반환될 수 있으며, 일치율이 잘못되었습니다. 0.2%에 불과하다.

어떻게 할 수 있나요?

그때 저는 데이터 구조나 알고리즘을 전혀 이해하지 못했거든요.

1. 더하기

모든 숫자를 더하면(*키는 11), 5375*6*의 합은 48이 됩니다. 대부분의 입력값의 합이 100을 넘지 않는데, 이는 배열의 처음 100개 위치에 수만 개의 전화번호가 군집된다는 것을 의미하므로 실현 가능하지 않습니다.

2. 곱셈

모든 숫자를 곱하면 381150이 됩니다. 이는 가능해 보이지만 문제가 있습니다. lesk, lsek, slke...의 곱이 동일하고 각 숫자 키도 3글자에 해당하므로 반복 확률이 매우 높다는 것입니다.

3. 향상된 곱셈

①문자열은 문자는 동일하지만 알파벳 순서가 다르면 이러한 방식으로 충돌을 피할 수 있습니다. 각 숫자에 먼저 곱한 다음 순서 번호는 다음과 같습니다. 다른 값을 곱합니다.

②각 숫자키는 영문 3글자에 해당합니다. 사용자가 숫자키에 있는 문자의 일련번호를 입력하지 않으면 더 이상 정확하게 계산할 수 없습니다. 고려할 수 있는 유일한 방향은 주어진 단어 목록을 기반으로 확률 통계를 작성하는 것이므로 고려하지 않을 것입니다.

4. 위치 충돌

향상된 곱셈을 사용하더라도 다른 이름 문자로 계산된 결과가 계속 반복될 수 있습니다. 그렇다면 충돌이 발생하면 어떻게 해야 할까요?

다음 빈 위치에 순차적으로 저장하시겠습니까? 생각해보면 이건 안 된다. 다음 공백 위치가 다른 문자 집합의 결과인 경우 2차 충돌이 발생합니다.

다행히 소수가 있습니다.

소수는 1과 자기 자신으로만 나누어질 수 있으므로 위의 곱셈으로 얻은 모든 곱은 소수가 될 수 없으므로 소수 위치에 전화번호가 저장되지 않습니다.

따라서 현재 제품부터 시작하여 다음 소수를 오른쪽으로 검색하세요. 소수 위치가 여전히 사용되는 경우 계속해서 가장 가까운 다음 소수를 검색하세요. ..

이쯤 되면 문제가 해결된 것 같습니다.

사용자가 일련의 숫자를 입력하면 수식에 따라 제품이 계산되고 아래 첨자 위치의 전화번호가 반환됩니다. 틀리면 특정 소수가 붙은 배열 요소가 비어 있을 때까지 후속 소수를 순차적으로 검색하여 최종적으로 찾은 모든 전화번호를 반환합니다. 대부분의 경우 전화번호는 O(1) 시간 복잡도에서 찾을 수 있습니다.

5、数组太大

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

6、后来

即使不考虑数组过大因素，以我当时初学编程的水平，这样的程序也是没有能力写出来的。

我之所以还原这个思考的过程，是觉得独立思考的过程非常有趣也很有价值。想想，其实现有的算法都是当年那些大牛在实际工程中一步一步寻求解决方案而最终推导得到的。

因此，当在工程中碰到一些棘手的难题时，只要乐于思考分解问题并寻求每一个小问题解决方案，那么很多所谓的难题都是可以解决的。

后来看了《数据结构与算法分析.Java语言描述》，我才知道原来我的思路其实就是开放寻址法（Open Addressing）。

JDK的HashMap使用的则是分离链接法(separate chaining)。不同：增加了桶的概念来保存冲突的数据；进行求余运算来降低数组大小。

那么，就谈谈Java中的HashMap吧。

四、HashMap结构及算法详解

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

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个；

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

2、hashcode生成

这是String类的hashCode生成代码。

　　public int hashCode() {
　　　　int h = hash;
　　　　if (h == 0 && value.length > 0) {
　　　　　　char val[] = value;
　　　　　　for (int i = 0; i < value.length; i++) {
　　　　　　　　h = 31 * h + val[i];
　　　　　　}
　　　　　　hash = h;
　　　　}
　　　　return h;
　　}

로그인 후 복사

String类的value是char[]，char可以转换成UTF-8编码。譬如，’a’、’b’、’c’的UTF-8编码分别是97,98,99；“abc”根据上面的代码转换成公式就是：

h = 31 * 0 + 97 = 97；
h = 31 * 97 + 98 = 3105；
h = 31 * 3105 + 99 = 96354；

로그인 후 복사

使用31作为乘数因子是因为它是一个比较合适大小的质数：如值过小，当参与计算hashcode的项数较少时会导致积过小；如为偶数，则相当于是左位移，当乘法溢出时会造成有规律的位信息丢失。而这两者都会导致重复率增加。

如果使用32作为乘数因子(相当于 << 5)，以字符串“abcabcabcabcabc”为例，它的hashcode的每一步计算结果如下图：

如上图所示，字符串末尾每3个字母就会产生一个重复的hashcode。这并不是一个巧合，即使换成其它的英文字母，也有很容易产生重复，而使用质数则会大大地减少重复可能性。有兴趣的可以参照上图去作一下左位移运算，会发现这并不是偶然。

《Effective Java》一书中详细描述了hashcode的生成规则和注意事项，有兴趣的可以去看看。

从源代码的hashCode()方法可知，String类对象保存了已经计算好的hashCode，如果已经调用过hashCode()方法，那么第二次调用时不会再重新生成，而是直接返回已经计算好的hashCode。

String对象总是会存放到String类私有维护的常量池中，不显式使用new关键字时，如果常量池中已经有value相同的对象，那么总是会返回已有对象的引用。因此，很多情况下生成hashCode这种比较昂贵的操作实际上并不需要执行。

3、哈希函数设计

现在，已经得到了重复率很低的hashCode，还有什么美中不足的地方吗？

扰动函数

　　static final int hash(Object key) {
　　　　　　int h;
　　　　　　return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
　　}

로그인 후 복사

下图还是以字符串“abcabcabcabcabc”为例，使用上面方法得到的运算过程和结果。

为什么要先无符号右位移16位，然后再执行异或运算？看看下图的二进制的与运算，你就会明白。

你会发现只要二进制数后4位不变，前面的二进制位无论如何变化都会出现相同的结果。为了防止出现这种高位变化而低位不变导致的运算结果相同的情况，因此需要将高位的变化也加入进来，而将整数的二进制位上半部与下半部进行异或操作就可以得到这个效果。

为什么要使用与运算？

因为哈希函数的计算公式就是hashCode % tableSize，当tableSize是2的n次方(n≥1)的时候，等价于hashCode & (tableSize – 1)。

扰动函数优化前：1954974080 % 16 = 1954974080 & (16 – 1) = 0
扰动函数优化后：1955003654 % 16 = 1955003654 & (16 – 1) = 6

这就是为什么需要增加扰动函数的原因。

源代码详解

代码解释之前需要补充说明一下，jdk1.8引入了红黑树来解决大量冲突时的查找效率，所以当一个链表中的数据大到一定规模的时候，链表会转换成红黑树。因此在jdk1.8中，HashMap的查找和保存数据的最大时间复杂度实际上就是红黑树的时间复杂度O(logN)。

以下是HashMap中的保存数据的方法源代码，相信经过以上的描述，已经非常容易看懂这一段代码。

　　final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
　　　　Node<K,V>[] tab;　　　　//HashMap数组
　　　　Node<K,V> p;　　　　　　//初始化需要保存的数据
　　　　int n;　　　　　　　　　//数组容量
　　　　int i;　　　　　　　　　//数组下标

　　　　/* 如果数组为空或0，初始化容量为16 */
　　　　if ((tab = table) == null || (n = tab.length) == 0){
　　　　　　n = (tab = resize()).length;
　　　　}

　　　　/* 使用哈希函数获取数组位置(如果为空，保存新节点到数组) */
　　　　if ((p = tab[i = (n - 1) & hash]) == null){
　　　　　　tab[i] = newNode(hash, key, value, null);
　　　　}

　　　　/* 如果数组位置已经有值，则使用下列方式保存数据 */
　　　　else {
　　　　　　Node<K,V> e;　　　　//临时节点保存新值
　　　　　　K k;　　　　　　　　//临时变量用于比较key

　　　　　　//如果头节点与新节点的key的hash值相同 且 key的值相等，e赋值为旧节点
　　　　　　if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
　　　　　　　　e = p;
　　　　　　}

　　　　　　//如果头节点是一个红黑树节点，那么e将保存为树节点
　　　　　　else if (p instanceof TreeNode){
　　　　　　	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
　　　　　　}

　　　　　　//如果头节点与新节点不同，且头节点不是红黑树节点，循环比对链表的所有节点
　　　　　　else {
　　　　　　　　for (int binCount = 0; ; ++binCount) {
　　　　　　　　　　if ((e = p.next) == null) {
　　　　　　　　　　　　//如果直到链表尾未找到相同key的节点，将新结点作为最后一个节点加入到链表
　　　　　　　　　　　　p.next = newNode(hash, key, value, null);

　　　　　　　　　　　　//如果链表节点数大于等于8-1，转换成红黑树；转换成红黑树的最小节点数是8
　　　　　　　　　　　　if (binCount >= TREEIFY_THRESHOLD - 1){
　　　　　　　　　　　　　　treeifyBin(tab, hash);
　　　　　　　　　　　　}
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　　　//如果循环过程中发现新旧key的值相同，跳转：是否覆盖旧值
　　　　　　　　　　if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　　　p = e;
　　　　　　　　}
　　　　　　}

　　　　　　//是否覆盖旧值
　　　　　　if (e != null) {
　　　　　　　　V oldValue = e.value;
　　　　　　　　//如果新值不为空且（允许修改旧值 或 旧值为空），覆盖旧节点的值
　　　　　　　　if (!onlyIfAbsent || oldValue == null){
　　　　　　　　　　e.value = value; 	
　　　　　　　　}
　　　　　　　　afterNodeAccess(e);　　//回调函数，这里是空函数，但在linkedHashMap中实现了此方法
　　　　　　　　return oldValue;　　　　//返回旧值
　　　　　　}
　　　　}

　　　　//用于比较判断是否在遍历集合过程中有其它线程修改集合，详情请网上搜索fail-fast快速失败机制
　　　　++modCount;

　　　　//当key数量大于允许容量时进行扩容。允许容量在HashMap中是数组长度 * 装填因子(默认0.75)
　　　　if (++size > threshold){
　　　　	resize();
　　　　}

　　　　//回调函数，这里是空函数，但在linkedHashMap中实现了此方法
　　　　afterNodeInsertion(evict);
　　　　return null;
　　}

로그인 후 복사

简化后的伪代码

　　putval(key, value){
　　　　index = key.hashcode % tablesize;
　　　　if(null == table[index]){
　　　　　　table[index] = new node(key, value);
　　　　}else{
　　　　　　firstNode = table[index];
　　　　　　nextNode = firstNode.next;
　　　　　　while(nextNode.hasNextNode()){
　　　　　　　　//如果找到相同key的旧节点，覆盖旧节点
　　　　　　　　if(key == nextNode.key){
　　　　　　　　　　nextNode = new node(key, value);　　
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　//如果到队列末尾依然没有找到相同key的旧节点，将新结点加入到最后一个节点的末尾
　　　　　　　　if(nextNode.next == null){
　　　　　　　　　　nextNode.next = new node(key, value);
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　nextNode = nextNode.next;
　　　　　　}
　　　　}
　　}

로그인 후 복사

链表大小设计

代码注释中已经稍有提及，这里再分别展开讨论。

①容量选择

HashMap的初始容量是 1 << 4，也就是16。以后每次扩容都是size << 1，也就是扩容成原来容量的2倍。如此设计是因为 2^n-1(n≥1)的二进制表示总是为重复的1，方便进行求余运算。

《数据结构与算法分析.Java语言描述》一书中的建议是容量最好是质数，有助于降低冲突，但没有给出证明或实验数据。

质数虽然是神奇的数字，但个人感觉在这里并没有特别的用处。

根据公式index = hashCode % size可知，无论size是质数还是非质数，index的值区间都是0至(size-1)之间，似乎真正起决定作用的是hashCode的随机性要好。

这里先不下结论，待以后再写一个随机函数比较下质数和非质数重复率。

②装填因子

装填因子默认是0.75，也就是说如果数组容量为16，那么当key的数量大于12时，HashMap会进行扩容。

装填因子设计成0.75的目的是为了平衡时间和空间性能。过小会导致数组太过于稀疏，空间利用率不高；过大会导致冲突增大，时间复杂度会上升。