Vector/ArrayList/LinkedList
Vector
ArrayList
自动扩容流程
当我们试图在ArrayList中添加一个元素的时候，首先会检查数组容量，源码中是调用的ensureCapacity 方法,容量不够才会进行扩容
扩容的时候会创建一一个新的数组,大小是原数组大小的1.5倍,也就是size + size》> 1.之后将原数组中的所有元素都copy到新创建的数组中
最后，将引用指向新数组,完成扩容
LinkedList
HashMap/HashTable
哈希碰撞产生的原因
为什么hashmap数组的长度为2的幂次方
计算hash值，通过取余操作，得到 index<br>
降低Hash冲突怎么做
在计算哈希值的 hash()方法中，得到 Object的hashcode之后，高16位和低16位做异或运算
HashMap避免内存泄露
HashMap如果使用自定义的对象作为key,那么- -定要重写equals和hashCode方法。<br>否则，假如我们new大量的对象给相同的参数，本意在map中这些对象key是会覆盖的，但是没有重写equals和hashCode的话，会无限死循环往里存,<br>又因为是强引用，垃圾回收不会处理。因此，造成了内存泄漏。
HashMap底层实现
jdk 1.7 数组+链表
jdk 1.8 数组+链表+红黑树
数组长度 > 64 且 链表长度>8会转换为红黑树
为什么是8, 12*0.75 柏松分布因子得到的
红黑树结点个数 < 6 时，会转回链表
为什么需要转换
红黑树保存较多信息，节点的值、指针、颜色
链表相对简单
HashMap查询的时间复杂度
数组+链表
没有Hash冲突，O（1）
有hash冲突 o1+ O（n）
数组、链表、红黑树
没Hash冲突 O（1）
有Hash冲突 O（1）+O（logn）
HashMap扩容
一些变量
capactiy，16
默认16，但初始容量是32
loadFactor，负载因子，0.75
threshold，阀值 = 容量 * 负载因子 ，超过阀值会扩容
什么时候触发扩容
当元素数量超过阀值会扩容，容量是扩容前的两倍
JDK 7
扩容机制
如果是空参，那么用默认的容量、负载因子和阈值，初始化数组，内部是空数组<br>如果不是空参，使用传入的参数<br>第一次put会初始化数组，容量变为不小于指定容量的2的幂，然后根据负载因子确定阈值<br>如果不是第一次扩容，则新容量=旧容量* 2
元素迁移
遍历每个桶，然后遍历每个元素，重新计算hash值，找到新数组的对应位置，头插法插入新的链表<br>因为是头插法，因此新旧链表元素位置会倒置<br>并且，多线程下，可能会出现死循环
JDK 8
扩容机制
如果是空参构造函数，默认内部数组是null,也就是没有实例化!<br>在第一次put的时候，会开始第一次初始化扩容<br>如果是有参构造函数。会指定不小于容量的2的幕数。<br>如果不是第一次扩容，则容量变为原来的2倍
元素迁移
扩容的时候，不需要重新计算hash,只需要判断最高位是1还是0<br>迁移元素的时候是正序的，不会出现链表专置
HashMap 和 HashTable 区别
为什么重写 equals 还要重写 hashcode方法
HashCode方法，native 方法，底层采用c语言编写。作用是根据对象的内存地址，转换为整数类型<br>
equals方法，默认情况下继承Object类，使用==判断对象的内存地址是否相等<br>
两个对象相等，equal- 定相等 ，hashCode也- 定相等。因此重写equals方法之后还需要重写hashCode方法<br>
阿里巴巴手册页规定了，只要使用自定义的对象作为Map的键，那么必须重写equals和hashCode
内存泄漏的问题
如果HashMap使用自定义的对象作为key,举个极端的例子，new多个不同的对象给相同的参数,但是对象内存地址不同。我们没有重写equals和HashCode,就可能发生这样一个问题: 无限死循环往HashMap中存，导致内存溢出。涉及到强引用的问题，垃圾回收不会处理
