Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
hashmap时间和空间复杂度_java中contains怎么用,希望能够帮助你!!!。

1. 分析hashMap.containsKey

hashMap.containsKey(value)的时间复杂度为什么是O(1)呢？这个就要来看一下源码了

 /** * Returns <tt>true</tt> if this map contains a mapping for the * specified key. * * @param key The key whose presence in this map is to be tested * @return <tt>true</tt> if this map contains a mapping for the specified * key. */ public boolean containsKey(Object key) { 
    return getNode(hash(key), key) != null; } 

调用了getNode(hash(key), key)方法，参数分别为key的hash值，key。再来看下这个方法的实现

 /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ 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 = first.next) != 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; } 

可以看到返回的是first(默认check first node)，算法中带n的可能影响时间复杂度的便是：

first = tab[(n - 1) & hash]) != null 

为了探究为什么是O(1)，这里就要理解

• Node<K,V> first是什么
• Node<K,V>[] tab是什么

Node<K,V> first：是一个单向链表结点，包含了hash，key，value和指向下个结点的指针

 /** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ static class Node<K,V> implements Map.Entry<K,V> { 
    final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { 
    this.hash = hash; this.key = key; this.value = value; this.next = next; } ... get and set method ... } 

Node<K,V>[] tab：是一个数组，值得注意的是，数组长度为2的倍数

 /** * The table, initialized on first use, and resized as * 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; 

所以tab[(n - 1) & hash]执行了如下操作：

1. 指针first指向那一行数组的引用（那一行数组是通过table下标范围n-1和key的hash值计算出来的），若命中，则通过下标访问数组，时间复杂度为O(1)
2. 如果没有直接命中（key进行hash时，产生相同的位运算值），存储方式变为红黑树，那么遍历树的时间复杂度为O(lgn)

2. 总结

综上，hashMap.containsKey(value)最好情况便是O(1)，最坏情况是O(lgn)

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。