说⼀下ArrayList和LinkedList区别

1. ⾸先，他们的底层数据结构不同，ArrayList底层是基于数组实现的，LinkedList底层是基于链表实现
的
2. 由于底层数据结构不同，他们所适⽤的场景也不同，ArrayList更适合随机查找，LinkedList更适合删
除和添加，查询、添加、删除的时间复杂度不同
3. 另外ArrayList和LinkedList都实现了List接⼝，但是LinkedList还额外实现了Deque接⼝，所以
LinkedList还可以当做队列来使⽤
 

说⼀下HashMap的Put⽅法

先说HashMap的Put⽅法的⼤体流程：
1. 根据Key通过哈希算法与与运算得出数组下标
2. 如果数组下标位置元素为空，则将key和value封装为Entry对象（JDK1.7中是Entry对象，JDK1.8中是
Node对象）并放⼊该位置
3. 如果数组下标位置元素不为空，则要分情况讨论
a. 如果是JDK1.7，则先判断是否需要扩容，如果要扩容就进⾏扩容，如果不⽤扩容就⽣成Entry对
象，并使⽤头插法添加到当前位置的链表中
b. 如果是JDK1.8，则会先判断当前位置上的Node的类型，看是红⿊树Node，还是链表Node
i. 如果是红⿊树Node，则将key和value封装为⼀个红⿊树节点并添加到红⿊树中去，在这个过
程中会判断红⿊树中是否存在当前key，如果存在则更新value
ii. 如果此位置上的Node对象是链表节点，则将key和value封装为⼀个链表Node并通过尾插法插
⼊到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历链表的过程中会判断是否
作者图灵学院：周瑜
阿⾥⼀⾯
说⼀下ArrayList和LinkedList区别
说⼀下HashMap的Put⽅法
4
存在当前key，如果存在则更新value，当遍历完链表后，将新链表Node插⼊到链表中，插⼊
到链表后，会看当前链表的节点个数，如果⼤于等于8，那么则会将该链表转成红⿊树
iii. 将key和value封装为Node插⼊到链表或红⿊树中后，再判断是否需要进⾏扩容，如果需要就
扩容，如果不需要就结束PUT⽅法