蚂蚁花呗：阿里巴巴面试：Java 集合知识点（附图文解析）( 四 ) 支付宝|第三方支付

ps：不会囊括所有方法，只是为了学习，记录思想。
ArrayList 和 LinkedList 两者都实现了 List 接口
构造器ArrayList 提供了 3 个构造器， ①无参构造器 ②带初始容量构造器 ③参数为集合构造器
LinkedList 提供了 2 个构造器，因为基于链表，所以也就没有初始化大小，也没有扩容的机制，就是一直在前面或者后面插插插~~
插入ArrayList 的 add() 方法
当然也可以插入指定位置，还有一个重载的方法 add(int index E element)
可以看到每次插入指定位置都要移动元素，效率较低。
再来看 LinkedList 的插入，也有插入末尾，插入指定位置两种，由于基于链表，肯定得先有个 Node
获取ArrayList 的 get() 方法很简单，就是在数组中返回指定位置的元素即可，所以效率很高
LinkedList 的 get() 方法，就是在内部调用了上边看到的 node() 方法，判断在前半段还是在后半段，然后遍历得到即可。
HashMap的底层实现

什么时候会使用HashMap？他有什么特点？
你知道HashMap的工作原理吗？
你知道 get 和 put 的原理吗？equals() 和 hashCode() 的都有什么作用？
你知道hash的实现吗？为什么要这样实现？
如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

HashMap 在 JDK 7 和 JDK8 中的实现方式略有不同。分开记录。
JDK1.7 实现深入 HahsMap 之前，先要了解的概念

initialCapacity：初始容量。指的是 HashMap 集合初始化的时候自身的容量。可以在构造方法中指定；如果不指定的话，总容量默认值是 16。需要注意的是初始容量必须是 2 的幂次方。（1.7中，已知HashMap中将要存放的 KV 个数的时候，设置一个合理的初始化容量可以有效的提高性能）static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
size：当前 HashMap 中已经存储着的键值对数量，即 HashMap.size()
loadFactor：加载因子。所谓的加载因子就是 HashMap (当前的容量/总容量) 到达一定值的时候， HashMap 会实施扩容。加载因子也可以通过构造方法中指定，默认的值是 0.75。举个例子，假设有一个 HashMap 的初始容量为 16，那么扩容的阀值就是 0.75 * 16 = 12。也就是说，在你打算存入第 13 个值的时候， HashMap 会先执行扩容。
threshold：扩容阀值。即扩容阀值 = HashMap 总容量 * 加载因子。当前 HashMap 的容量大于或等于扩容阀值的时候就会去执行扩容。扩容的容量为当前 HashMap 总容量的两倍。比如，当前 HashMap 的总容量为 16，那么扩容之后为 32。
table：Entry 数组。我们都知道 HashMap 内部存储 key/value 是通过 Entry 这个介质来实现的。而 table 就是 Entry 数组。

JDK1.7 中 HashMap 由数组+链表组成（“链表散列” 即数组和链表的结合体），数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（HashMap 采用 “拉链法也就是链地址法” 解决冲突），如果定位到的数组位置不含链表（当前 entry 的 next 指向 null ）那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为 O(1) ，因为最新的 Entry 会插入链表头部，即需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过 key 对象的 equals 方法逐一比对查找。