0 前言

本专题将基于LeetCode的题目来剖析最佳解决方案背地的一些数据结构与算法原理。
本文将基于题目#1两数之和来剖析JAVA中HashMap原理及高性能起因。

1 题目形容

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你能够假如每种输出只会对应一个答案。然而，数组中同一个元素不能应用两遍。

你能够按任意程序返回答案。

示例 1：
输出：nums = [2,7,11,15], target = 9
输入：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输出：nums = [3,2,4], target = 6
输入：[1,2]

示例 3：
输出：nums = [3,3], target = 6
输入：[0,1]

提醒：

  • 2 <= nums.length <= 103
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个无效答案

2 最佳计划及疑难

最容易想到的解决方案是暴力枚举，循环嵌套，空间复杂度只有O(1)，但工夫复杂度是O(N ^2)。更优的计划是基于哈希表（如JAVA中HashMap）来放慢数据查问的效率，用空间来换工夫，使工夫和空间的复杂度均为O(N)。

具体形容及代码可见：https://leetcode-cn.com/probl...

此处的疑难是，为什么用哈希表就能够显著晋升查问效率呢？

3 哈希表原理剖析

1、为什么会有哈希表这种构造、它由什么组成？

咱们已知的构造有数组和链表，两者各有优缺点：

  • 数组：数组存储构造是间断的，空间复杂度大，但查问的工夫复杂度小。其寻址(通过下标搜寻)效率高，个别的插入和删除效率低。即，查问快，增删慢。
  • 链表：链表存储构造是离散的，空间复杂度小。其寻址(通过下标搜寻)效率低，个别的插入和删除效率高。即，查问慢，增删快。

哈希表是基于数组和链表构建的，目标是为了充分发挥这两个构造的劣势。

对于一个哈希表，其蕴含四个局部的内容：

  • key：即键值
  • value：即数值
  • hash：key对应的hash值，基于hash进行某种操作后失去的是表的index
  • next：当index抵触时，寄存抵触的数据，链表构造

2、为什么哈希表的查问效率会高于数组呢？

因为哈希表的构造也有点相似于字典。字典通过key能够疾速查问到value，哈希表一样能够通过key疾速查问到value，但其中间进行了散列变换（即hash计算），通过hash值来确定value所在的index，从而实现数据的获取。

一个确定的key能够计算失去惟一的hash值，而index是hash通过某种操作失去的，难以不免hash值的抵触，为了解决这个抵触才引入了链表，来高效的存储hash值雷同的值。

3、 hashMap.containsKey(value)的工夫复杂度是多少？

HashMap在不同版本的JDK之间有着如下的区别：

  • JDK 1.8以前 HashMap由数组和链表形成。
  • JDK 1.8之后 HashMap由数组、链表和红黑树形成。

红黑树的特点是查问快，增删慢。
红黑树 作为一种二叉查找树，但它在二叉查找树的根底上减少了着色和相干的性质使得红黑树绝对均衡，从而保障了红黑树的查找、插入、删除的工夫复杂度最坏为O(log n)。因为链表的查问工夫复杂度为O(n)，所以当链表很长时转换成红黑树将很好的提高效率！

红黑树的引入是为了解决，当抵触产生时，链表太长而带来的查问性能降落的问题。在JDK 1.8中规定，当链表长度大于8后，链表转为红黑树结构。转换之前最坏的工夫复杂度为O(N)，转换之后的最坏工夫复杂度为O(logn)。

HashMap的原理解说举荐视频（p6-p9）：https://www.bilibili.com/vide...
红黑树的原理举荐：https://www.cnblogs.com/yyxt/...

综上：
JDK 1.8以前，hashMap.containsKey(value)最好状况便是O(1)，最坏状况是O(n)
JDK 1.8当前，hashMap.containsKey(value)最好状况便是O(1)，最坏状况是O(lgn)

4 HashMap源码剖析

这篇文章解说的很清晰，不再赘述。
https://blog.csdn.net/qingtia...

如果该文章看不懂，能够先看看上文说到的视频。