JAVA--HashMap查询的时间复杂度为什么是O（1）
写在前⾯
HashMap查询的时间复杂度是O(1)，这是众所周知的，但是你知道为什么是O(1)吗？
正⽂
要研究明⽩这个问题，我们需要从数组开始研究。
数组查询的时间复杂度是O(1)，为什么呢？因为在内存中，数组对象被创建时，是被分配了⼀块连续的内存地址，这块连续的内存地址上，存放着⼤⼩相等的引⽤类型，在默认情况下，如果虚拟机内存没有超过32GB，那么JVM使⽤的是32位的压缩指针，也就是说，在这块连续的内存地址上存放的是⼀个个的32位的压缩指针。现在假设我们的数组中存了10个对象，那么我们如果要第5个对象，只需要在数组初始位置偏移4*32位就可以了，这意味着数组中所有对象的内存地址我都可以根据数组的初始位置和对象的次序计算出来，知道了对象的内存地址，那么查询的时间复杂度可不就是O(1)嘛。
为了更明⽩，我拿单向链表来做对⽐说明。
我们知道单向链表查询的时间复杂度是O(n)，为什么是O(n)呢？因为链表的每个节点的内存地址仅存放
在前⼀个节点中（头节点除外），也就是说如果我要获取当前节点的内存地址，就必须先获取前⼀个节点的内存地址，如果要获取前⼀个节点的内存地址，就必须先获取前前⼀个节点的内存地址，依次类推，知道头节点。那么说如果我要获取这个单项链表中的第n个节点，我就必须从头节点开始，⼀个⼀个的查询下去，知道到这个节点。
单向链表和数组的区别在哪⼉呢？就是数组中对象的内存地址可以直接计算出来，⽽单向链表中对象的内存地址没法计算，只能是⼀个⼀个地查。
好，我们现在搞清楚了数组查询的时间复杂度为什么是O(1)了，是时候来看看HashMap了。
HashMap在内存中是怎么存的呢？换句话说，它的底层是什么样的呢？
看过源码的同学可能知道，它的底层是： 数组+链表+红⿊树。
其中最主要的是数组，因为只有数组才能实现查询的时间复杂度为O(1)。
现在先不要管链表和红⿊树，我们着重来看数组，探究下数组是怎么实现map的。
我们知道，map是key-value集合，跟数组不太⼀样唉。其实，你跳出来看，数组也是key-value集合，这句话是怎么说的呢？因为我们可以把数组的下标看成是key，数组中存储的对象是value。哎～这样
⼀想是不是有种豁然开朗的感觉？没错！HashMap的底层是数组，当根据key查询value是时候，它就是先根据key来来计算出数组的下标，然后根据从数组中获取对应的value！
这样HashMap就实现了查询的时间复杂度是O(1)!!
好了，看到这⾥，题⽬中的问题已经解答完了。
但是如果你想了解的更深⼀点，⽐如HashMap是如何根据key求出数组下标的，你可以接着往下看。
⾸先我们先来看看HashMap的部分源码：
/**
* The table, initialized on first use, and resized as
为什么使用bootstrap?* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
……
}
上⾯的源码中展⽰了HashMap中的底层数组，它是个Node<K,V>类型的数组，这个数组叫做table。
我们注意下注释⾥，它说这个数组的长度永远是2的多少次幂，也就是说数组的长度只能是2，4，8，16，32，，，这类的值，为什么呢？后边讲。
如果想要知道如何求数组下标的，我们只要看看get(Object key)⽅法的源码就好了。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = ) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
…
…
}
public class Object {
……
public native int hashCode();
……
}
我们前⾯提到过，table数组⾥存的是Node<K,V>，这⾥的V就是我们要查询的value，那么如果要查询value，我们只要拿到了Node<K,V>就可以了。在上⾯的get(Object key)⽅法中，e就是要查的Node<K,V>，它是这么查询的：e = getNode(hash(key), key)，我们⼀个⼀个地看，先看⾥边的hash(key)，这个⽅法的源码也在上边了，我们看到，它是Object类⾥的native⽅法，返回值是⼀个int，OK，记住这个int。再看外⾯的getNode(hash(key), key)⽅法，它的源码也在上⾯了，乍⼀看，好复杂，不急，再看看，，，还是好复杂，，，为什么复杂呢？因为我们忽略了HashMap的另外两个底
层结构--链表和红⿊树，这⾥呢我们还是先不管链表和红⿊树，我把上⾯的源码改⼀下，改成只⽤数组的伪代码。
// 以下是伪代码
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
……
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> e; int n;
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tab[(n - 1) & hash]) != null) {
return e;
}
return null;
}
……
}
这样⼀看是不是简单了好多？哈哈哈！我们仔细看它的if条件，第⼀个是(tab = table) != null，这个好理解，就是当前HashMap的table数组中得有值嘛；然后看第⼆个(n = tab.length) > 0，这个与第⼀个条件同理；接着最后⼀个(e = tab[(n - 1) & hash]) != null，这个是最重要的你看它是取了table数组中下标为(n - 1) & hash的Node<K,V>，那么这个(n - 1) & hash就是我们要的东西。其中hash我们前⾯提到了，就是⼀个int，n呢是数组table的长度，也就是说数组的下标是通过key的hashcode和table数组的长度减⼀做了个与操作获取到的，为什么这样取呢？因为它就是这么存的，，，为什么这么存呢？我们想下，如果数组的长度是10，那么数组的下标就是0～9之间的某个整数，同时key的hashcode是个int，如果我要根据key把这个Node存进去，那么我就需要把key的这个hashcode映射成0～9的某个值，怎么映射呢？答案是hashcode除以10，然后取余数。⽐如这个key的hashcode是19，那么它除以10取余得9，我就把这个key对应的node存放在数组下标为9的位置，是不是很完美？OK，那这个取余跟(n - 1) & hash有什么关系呢？我们这⾥需要知道些⼆进制的知识，我们先要知道n的默认值是16，n-
1就等于15，⽽15的⼆进制是1111，hashcode跟1111做与操作，结果是什么？结果是hashcde ⼆进制的后四位！同志们，⼆进制的后四位，恰好是0～15之间的某个值！恰好是数组下标的取值范围！！这也就是我们前⾯遗留的问题：为什么table数组的长度要设为2的多少次幂！理解了吗？
最后⼩结⼀下，key是怎么计算数组下标的。
取key的hashcode跟数组长度减⼀做与操作！
最后的最后，可能有同学还有疑惑：不同的hashcode除以数组长度取余数可能会得到同⼀个值啊，那取出的数组下标相同的时候，table数组中的对象是怎么存的呢？
这是个很好的问题，这⾥就⼜要提⼀下我们之前说到的东西：HashMap的底层结构是数组+链表+红⿊树。这⾥呢我下⼀篇⽂章再讲吧，因为⼀篇⽂章太长的话，就没有读者了。。。。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。