ArrayList:
public boolean add(E e) { // 确保数组的容量，保证可以添加该元素 ensureCapacityInternal(size + 1); // Increments modCount!! // 将该元素放入数组中 elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { // 如果数组是空的，那么会初始化该数组 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // DEFAULT_CAPACITY 为 10,所以调用无参默认 ArrayList 构造方法初始化的话，默认的数组容量为 10 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 确保数组的容量，如果不够的话，调用 grow 方法扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } //扩容具体的方法 private void grow(int minCapacity) { // 当前数组的容量 int oldCapacity = elementData.length; // 新数组扩容为原来容量的 1.5 倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果新数组扩容容量还是比最少需要的容量还要小的话，就设置扩充容量为最小需要的容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //判断新数组容量是否已经超出最大数组范围，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: // 复制元素到新的数组中 elementData = Arrays.copyOf(elementData, newCapacity); }当然也可以插入指定位置，还有一个重载的方法 add(int index, E element)
public void add(int index, E element) { // 判断 index 有没有超出索引的范围 rangeCheckForAdd(index); // 和之前的操作是一样的，都是保证数组的容量足够 ensureCapacityInternal(size + 1); // Increments modCount!! // 将指定位置及其后面数据向后移动一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 将该元素添加到指定的数组位置 elementData[index] = element; // ArrayList 的大小改变 size++; }可以看到每次插入指定位置都要移动元素，效率较低。
再来看 LinkedList 的插入，也有插入末尾，插入指定位置两种，由于基于链表，肯定得先有个 Node
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } public boolean add(E e) { // 直接往队尾加元素 linkLast(e); return true; } void linkLast(E e) { // 保存原来链表尾部节点，last 是全局变量，用来表示队尾元素 final Node<E> l = last; // 为该元素 e 新建一个节点 final Node<E> newNode = new Node<>(l, e, null); // 将新节点设为队尾 last = newNode; // 如果原来的队尾元素为空，那么说明原来的整个列表是空的，就把新节点赋值给头结点 if (l == null) first = newNode; else // 原来尾结点的后面为新生成的结点 l.next = newNode; // 节点数 +1 size++; modCount++; } public void add(int index, E element) { // 检查 index 有没有超出索引范围 checkPositionIndex(index); // 如果追加到尾部，那么就跟 add(E e) 一样了 if (index == size) linkLast(element); else // 否则就是插在其他位置 linkBefore(element, node(index)); } //linkBefore方法中调用了这个node方法，类似二分查找的优化 Node<E> node(int index) { // assert isElementIndex(index); // 如果 index 在前半段，从前往后遍历获取 node if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 如果 index 在后半段，从后往前遍历获取 node Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } void linkBefore(E e, Node<E> succ) { // assert succ != null; // 保存 index 节点的前节点 final Node<E> pred = succ.prev; // 新建一个目标节点 final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; // 如果是在开头处插入的话 if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } 获取ArrayList 的 get() 方法很简单，就是在数组中返回指定位置的元素即可，所以效率很高
public E get(int index) { // 检查 index 有没有超出索引的范围 rangeCheck(index); // 返回指定位置的元素 return elementData(index); }LinkedList 的 get() 方法，就是在内部调用了上边看到的 node() 方法，判断在前半段还是在后半段，然后遍历得到即可。
public E get(int index) { checkElementIndex(index); return node(index).item; } HashMap的底层实现什么时候会使用HashMap？他有什么特点？
你知道HashMap的工作原理吗？
你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
你知道hash的实现吗？为什么要这样实现？
如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
HashMap 在 JDK 7 和 JDK8 中的实现方式略有不同。分开记录。
深入 HahsMap 之前，先要了解的概念