一、基本概念

1.1线性链表

对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)

1.2数组

采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

1.3哈希表

哈希表（hash table）也叫散列表，相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。

1
数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构

由于数组根据下标一次就可以查找到，因此hash表的主干就是数组。我们只需要将对象的关键字（hash值）映射（哈希函数）到数组中就可以了，然后通过数组一次就可以查找到元素。

例如：对A和B的存储，通过A的哈希int ah=f(A),int bh=f(B),那么，A和B在哈希表中的存储位置就只 ah、bh位置。

1.4hash冲突
1
如果计算两个值的hash值相同怎么办呢？这种情况就是Hash冲突

答案是通过链表解决，最先存入的放入链表的尾部，后来的放入链表的头部；

二、实现原理

1
通过对第一节的学习，我们知道hashMap其实底层是数组加链表实现的，那么具体怎么实现的

hashMap中维护了一个2的n次方自动扩展的数组，数组的每一项是一个链表。

2.1原理

1、利用key的hashcode从新计算hash，得出当前对象元素在数组中的位置；

2、存储时如果出现hash相同的key，此时有两种情况：如果key的值相同，则覆盖原来的值，如果不同就放到链表的头部；

1
如果是jdk1.8,当链表的长度>8个后，链表就会转化为红黑树

3、获取时也是先计算key的hash，然后找到数组下标，在进一步判断值是否相同，从而取到值；

2.2小结
  • 扩容：按2的N次方扩展，当达到数组长度的0.75倍的时候就要扩容；
  • 重置（resize）：数组扩大后需要从新计算已有数据的位置，对性能有影响；
  • 默认数组大小=16

三、总结

在创建hashMap时，在知道长度的情况下，建议设置默认长度，这样可以提高性能。

如你知道Map的长度=1000，根据hashMap长度达到75%就要扩容的，既是1000/0.75=1334,那么至少map的长度要设置为1334，又根据map的长度是根据2的N次方幂计算的，因此长度设置为1024最合适。