HashMap的存储结构以及时间复杂度

我们知道HashMap是基于Hash表来设计的，他的底层是数组和链表的结合体，那么HashMap的最大的特点就是快，因为是由键找值。
（1）什么是HashMap以及HashMap的构成
HashMap是基于哈希表的Map接口实现，用来存储键值对，线程不安全因此也很快，
允许null值null键。HashMap实际上是一个数组和链表的结合体。
键值对Map.Entry存放在链表里面，数组里面存放的是链表的节点。
如下图：

如果感觉这张图不给力再看看这张：

（2）HashMap的基本存储原理以及存储内容的组成
基本原理，首先有一个下标范围较大的数组来存储元素，然后通过hashCode()方法来获得关键字的哈希值，这个哈希值实际上就是数组的数组的下标。数组存储的元素是一个Entry类，有3个数据域，key，value，next,next指针指向下一个Entry.例如，
第一个键值对A进来，通过hashCode()计算其key的hash得到index=0,那么Entry[0]=A, 第二个键值对B的index也等于0，那么B.next=A，Entry[0]=B;如果第三个键值对C的index=0，那么C.next=B,Entry[0]=C.对于不同的元素可能计算出了相同的函数值，这样就产生了冲突，所以解决冲突的方法实际上是“链地址法”。
（3）HashMap的存取过程
HashMap使用put方法来存储对象，使用get方法来获取对象。使用put方法时，先用hashCode()计算出bucket位置，然后看该位置有没有Entry,如果没有，直接把该Entry存储在这个位置，如果已经有Entry存在，说明出现冲突了，先将这个位置上的链表链接上，然后将该Entry存储到该位置。
获取键值对时，也要先使用hashCode计算出键值对的bucket位置，如果该位置为空，说明没找到，否则，因为链表中存放的键值对，所以调用equals()来与元素关键字比较去找正确的Entry。
（4）HashMap大小存在的问题
在多线程的环境下，存在条件竞争的问题，因为两个线程都发现HashMap要调整大小了，他们会同时试着调整大小，有可能会出现死锁。在调整大小的过程中，存储在LinkedList中的元素的次序会反过来。但是为什么要在多线程中使用HashMap呢，HashMap是线程不安全的。HashTable是线程安全的，但是ConcurrentHashMap同步性能更好，因为它仅仅因为同步级别对map的一部分进行上锁。
（5）HashMap的时间复杂度
说了一大堆，还有一个问题没有说，就是HashMap的时间复杂度。
不用说，存数据的时间复杂度是O(1),因为只需要首先根据Key计算哈希值，其实就是数组的下标，找到存放的位置，然后把key-value链表节点链接上去就OK了。
取数据的时间复杂度最好是O(1)，最差是O(n),为什么呢？因为如果根据key首先得到哈希地址，发现该下标处位置已经被占用，那么我们要找的节点到底在链表的哪个位置，如果该位置就只有一个节点或者要找的节点就在表头，那么就不用再往后遍历链表了，所以最好情况下时间复杂度是O(1)；如果要找到的节点在链表表尾，那么就需要一个一个遍历链表，所以此时最差情况下为O(n)。但是如果我们的链表长度都很短，那么时间效率就会很高，其实即使是O（n）这个级别的复杂度正常也还是可以接受的。所以来总结一下，map的put方法的时间复杂度为O（1），get方法的时间复杂度为O(1)~ O(n)。
那么containKey()方法的时间复杂度呢，其实和get方法的时间复杂度是一样的，也是O(1)~O(n)，首先我们也是要根据key计算出对应的哈希地址，如果该地址处没有占用，那么可以直接返回false，说明Map中没有这个key；如果已经被占用，那就开始在链表上遍历Entry，比较key,所以这和刚才的get方法是一样的，从原理上就是一样的，那么时间复杂度自然也是一样的。
containValue()的时间复杂度和containKey()的时间复杂度不是一个级别的，因为他要依赖于key,所以他的时间复杂度为O(n).