容器的知识点

HashMap

基本原理

HashMap是Java中经常用到的数据结构。它的内部实现是一个hash表，每次put的节点都会先计算中hash值，然后放进桶里，当有数据的hashcode值冲突的时候，就会使用链表的形式来解决冲突，当链表长度超过8，且数组桶的长度超过64的时候，链表就会转化为红黑树进行数据的存储。当红黑树的节点小于6的时候，就会退化成链表。
HashMap的初始容量为16，它的负载因子默认为0.75。

HashMap的优势

HashMap最大的优势就是它的查询效率高，在最理想的情况下，HashMap的查找效率是O(1)。

put方法详解

以Java8中的put方法来说，他的整体流程比较简单。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

从之上的源码看来，可以总结如下它的流程如下：
1.如果发现桶数组是空的，则直接调用resize方法
2.经过hash的数组索引位置如果是空的，则直接添加节点。
3.如果不为空则处理冲突，处理冲突的方式有两种：

• 如果是红黑树，则直接在红黑树后面加上节点数据。
• 如果是链表，则在尾节点上添加数据，如果节点的数量大于8，则转化为红黑树。

4.如果数组的的容量到了负载因子规定的阈值，则进行扩容操作。

问题

1.为什么HashMap的hash表的大小要是2的幂？

• 方便按位&操作。
• 方便在扩容之后的数据移动索引位置。为旧桶的索引加上它原来的索引。

2.Java7到Java8的HashMap有什么改变？

• 变成了红黑树，增加了hash碰撞的处理效率
• 改变了扩容时候的插入顺序，降低了死锁发生的条件

3.红黑树是什么？
红黑树可以认为它是一个自平衡二叉树，当有节点插入的时候，如果破坏了平衡，就会发生自旋操作。

ArrayList

ArrayList也是我们经常使用的数据结构。它的底层是一个数组，默认的大小是10，也可以给他指定相应的大小。ArrayList每次扩容的大小是它本身的一半。在ArrayList中还有一种扩容策略是，当你第一次扩容完的容量不够的时候就会直接扩容至你需要的内存大小。

  private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }

源码中可以看到，第一次扩容完毕后会做一个比较，如果容量不够则直接newCapacity = minCapacity;，另外，在ArrayList中也做了内存限制，当大小超过了Integer的最大范围，则直接抛出异常。

使用for循环调用list的remove方法是个危险的操作，这样往往是删除不干净的。因为ArrayList中，某个元素被删除，后面的元素就会整体往前移动，当连续的某个元素要被删除，往往会漏删。要解决这种情况，可以使用Iterator进行迭代删除。另外也可以使用while(list.remove(elem));。