HashMap原理以及如何解决冲突问题

面试时最经典也是最喜欢问的集合是HashMap了

1：先说一下HashMap的数据结构：

     HashMap是一个哈希表，其底层可以说是数组加链表结构：看图直观明了

   

 

HashMap的默认容量是16，当到达16时，HashMap会根据负载因子（默认0.75）和扩容规则，增加容量的  具体请看

https://www.cnblogs.com/chengxiao/p/6059914.html

---------------------------------------------------------------------------这是一条分割线----------------------------------------------------------------------

在说一下ArrayList底层数数组结构，如何根据索引来查找数组的时间复杂度为O(1)，但是操作如果需要遍历的话，时间复杂度为O(n)，

而且增删对于数组结构的消耗很大，也就是性能比较次，因为ArrayList每次新增或者删除都相当于新开辟一个数组内存，然后再copy原来的，再加上新增的，删除也是相同的，需要先copy到新的数组中，这样操作时间和消耗都是很大的。所以查询快

但是LinkedList不是的，LinkeList是查询相比较ArrayList慢一点，但是新增和删除快效率高，之所以查询慢，是因为LinkedList是链表结构，获取某个元素都是需要遍历的。但是查询的时间复杂度是O(n) ，

看下图对比：时间复杂度，需要遍历的操作则复杂度为O(1)