本文首发于cdream的个人博客
欢迎转载，转载请注明出处。
本文是我在学习 java集合过程中，针对HashMap的一篇总结文章。由于博主是非科班出身程序员，在学习HashMap原理时遇到了很多困难，所以如果你和博主一样，数据结构基础也不扎实甚至是没有基础，这篇文章可能也非常适合你！
注：本文基于jdk1.8,不包括红黑树部分分析
以下是本文的结构，可根据需要跳转到相应位置，不必按顺序阅读！
时间复杂度用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着输入 n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。渐进时间复杂度用大写O来表示，所以也被称为大 O表示法。
常用的时间复杂度比较:
O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)
从左到右，算法执行效率逐渐下降,
了解更多：
十分钟搞定时间复杂度（算法的时间复杂度）
一套图 彻底明白了“时间复杂度”
基本数据结构HashMap主干是哈希表，这之前先了解一下其他几种数据结构的性能。
数组采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为 O(1)；通过给定值进行查找（顺序查找），需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为 O(n)；对于有序数组，可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为 O(logn)；对于指定位置的插入删除操作，涉及到数组元素的移动，其平均复杂度为 O(n)；另外修改和查找实现复杂度相同。
链表不是按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为 O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为 O(n)。
数组与链表的根据指定值查询时间复杂度都是O(1),但数组更快
1. 链表需要在遍历时，需要比数组更多的寻址操作 2. CPU缓存会把一片连续的内存空间读入，因为数组结构是连续的内存地址，所以数组全部或者部分元素被连续存在CPU缓存里面，而链表则不会