Java - 集合

一、集合概述

• 集合是java中提供的一种容器，可以用来存储多个数据

• 集合和数组的区别

• • 数组的长度是固定的，集合的长度是可变的
  • 数组中可以存储基本数据类型值，集合中只能存储对象

• 集合主要分为两大系列：Collection和Map，Collection表示一组对象，Map表示一组映射关系或键值对

• 

二、Collection

1、Iterator迭代器

（1）Iterator接口

• JDK专门提供了一个接口java.util.Iterator，主要用于迭代访问（即遍历）Collection中的元素，因此Iterator对象也被称为迭代器

• • 迭代：即Collection集合元素的通用获取方式。在取元素之前先判断集合中是否有元素，如果有，则取出元素，然后继续判断，直到将集合中的元素全部取出

• 集合获取迭代器的方法：public Iterator iterator()

• Iterator接口的常用方法：

• • public E next()：返回迭代的下一个元素
  • public boolean hasNext()：如果仍有元素可以迭代，则返回 true
  • void remove()：删除元素

（2）迭代器的实现原理

• Iterator迭代器对象在遍历集合时，内部采用指针的方式来跟踪集合中的元素

• • 在调用Iterator的next方法之前，迭代器指向第一个元素
  • 当第一次调用迭代器的next方法时，返回第一个元素，然后迭代器的索引会向后移动一位，指向第二个元素
  • 当再次调用next方法时，返回第二个元素，然后迭代器的索引会再向后移动一位，指向第三个元素，依此类推
  • 直到hasNext方法返回false，表示到达了集合的末尾，终止对元素的遍历

（3）Iterator迭代器的快速失败（fail-fast）机制

• Iterator迭代器的快速失败（fail-fast）机制：面对并发的修改，迭代器很快就完全失败(如果在Iterator、ListIterator迭代器创建后的任意时间从结构上修改了集合（通过迭代器自身的 remove 或 add 方法之外的任何其他方式），则迭代器将抛出 ConcurrentModificationException)

• 快速失败（fail-fast）机制设计原因：迭代器代表集合中某个元素的位置，内部会存储某些能够代表该位置的信息。当集合发生改变时，该信息的含义可能会发生变化，这时操作迭代器就可能会造成不可预料的事情。因此，果断抛异常阻止，是最好的方法

• 实现快速失败（fail-fast）机制原理：

• • 在ArrayList等集合类中都有一个modCount变量，用来记录集合的结构被修改的次数
  • 当给集合添加和删除操作时，会导致modCount++
  • 当用Iterator迭代器遍历集合，创建集合迭代器的对象时，用一个变量记录当前集合的modCount，并且在迭代器每次next()迭代元素时，都要检查变量与modCount是否相等，如果不相等，那么说明调用了Iterator迭代器以外的Collection方法修改了集合的结构，使得modCount++，此时迭代器就会抛出ConcurrentModificationException异常

2、Collection接口

• Collection表示一组对象，这些对象也称为collection的元素

• • 有的collection允许有重复的元素，有的不允许
  • 有的collection是有序的，有的是无序的

• JDK不提供此接口的任何直接实现，它提供更具体的子接口实现。此接口通常用来传递collection，并在需要最大普遍性的地方操作这些collection

• Collection是所有单列集合的父接口，因此在Collection中定义了单列集合(List和Set)通用的方法，这些方法可用于操作所有的单列集合

3、List接口

（1）List接口

• List接口：java.util.List接口继承自Collection接口，是单列集合的一个重要分支，习惯性地会将实现了List接口的对象称为List集合

• List接口特点：

• • 线性存储：List集合所有的元素是以一种线性方式进行存储的
  • 元素有序：即元素的存入顺序和取出顺序有保证
  • 有索引：通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）
  • 可重复：集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。

• List作为Collection集合的子接口，不但继承了Collection接口中的全部方法，而且还增加了一些根据元素索引来操作集合的特有方法

（2）List接口的实现类

• List接口的实现类有很多，常见的有：

• • ArrayList：动态数组（线程不安全，效率高）
  • Vector：动态数组（线程安全，效率低）
  • LinkedList：双向链表

• 动态数组的特点

• • 逻辑结构：线性结构
  • 物理结构特点：连续的存储空间，一次申请一大段连续的空间，一旦申请到，内存就固定了
• • 存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。
  • ArrayList与Vector的区别

	ArrayList	Vector
扩容机制	1.5倍	2倍
初始化容量	JDK1.6及之前：默认10JDK1.7之后：默认0，添加后为10	默认10
迭代器	Iterator和ListIterator迭代器，支持快速失败	支持Enumeration迭代器，不支持快速失败

• 链表的特点

• • 逻辑结构：线性结构
  • 物理结构：不要求连续的存储空间
  • 存储特点：数据必须封装到“结点”中，结点包含多个数据项，数据值只是其中的一个数据项，其他的数据项用来记录与之有关的结点的地址

• 链表与动态数组的区别

• • 动态数组访问元素的效率高，操作元素效率低
  • 链表访问元素效率低，操作元素效率高

① Vector部分源码分析

    public Vector() {
        this(10);//指定初始容量initialCapacity为10
    }
	public Vector(int initialCapacity) {
        this(initialCapacity, 0);//指定capacityIncrement增量为0
    }
    public Vector(int initialCapacity, int capacityIncrement增量为0) {
        super();
        //判断了形参初始容量initialCapacity的合法性
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //创建了一个Object[]类型的数组
        this.elementData = new Object[initialCapacity];//默认是10
        //增量，默认是0，如果是0，后面就按照2倍增加，如果不是0，后面就按照你指定的增量进行增量
        this.capacityIncrement = capacityIncrement;
    }
//synchronized意味着线程安全的   
	public synchronized boolean add(E e) {
        modCount++;
    	//看是否需要扩容
        ensureCapacityHelper(elementCount + 1);
    	//把新的元素存入[elementCount]，存入后，elementCount元素的个数增1
        elementData[elementCount++] = e;
        return true;
    }

    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        //看是否超过了当前数组的容量
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//扩容
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//获取目前数组的长度
        //如果capacityIncrement增量是0，新容量 = oldCapacity的2倍
        //如果capacityIncrement增量是不是0，新容量 = oldCapacity + capacityIncrement增量;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        
        //如果按照上面计算的新容量还不够，就按照你指定的需要的最小容量来扩容minCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        
        //如果新容量超过了最大数组限制，那么单独处理
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        
        //把旧数组中的数据复制到新数组中，新数组的长度为newCapacity
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    public boolean remove(Object o) {
        return removeElement(o);
    }
    public synchronized boolean removeElement(Object obj) {
        modCount++;
        //查找obj在当前Vector中的下标
        int i = indexOf(obj);
        //如果i>=0，说明存在，删除[i]位置的元素
        if (i >= 0) {
            removeElementAt(i);
            return true;
        }
        return false;
    }
    public int indexOf(Object o) {
        return indexOf(o, 0);
    }
    public synchronized int indexOf(Object o, int index) {
        if (o == null) {//要查找的元素是null值
            for (int i = index ; i < elementCount ; i++)
                if (elementData[i]==null)//如果是null值，用==null判断
                    return i;
        } else {//要查找的元素是非null值
            for (int i = index ; i < elementCount ; i++)
                if (o.equals(elementData[i]))//如果是非null值，用equals判断
                    return i;
        }
        return -1;
    }
    public synchronized void removeElementAt(int index) {
        modCount++;
        //判断下标的合法性
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        
        //j是要移动的元素的个数
        int j = elementCount - index - 1;
        //如果需要移动元素，就调用System.arraycopy进行移动
        if (j > 0) {
            //把index+1位置以及后面的元素往前移动
            //index+1的位置的元素移动到index位置，依次类推
            //一共移动j个
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        //元素的总个数减少
        elementCount--;
        //将elementData[elementCount]这个位置置空，用来添加新元素，位置的元素等着被GC回收
        elementData[elementCount] = null; /* to let gc do its work */
    }

② ArrayList部分源码分析

    public ArrayList() {
		this(10);//指定初始容量为10
    }
    public ArrayList(int initialCapacity) {
		super();
        //检查初始容量的合法性
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //数组初始化为长度为initialCapacity的数组
		this.elementData = new Object[initialCapacity];
    }
    private static final int DEFAULT_CAPACITY = 10;//默认初始容量10
	private static final Object[] EMPTY_ELEMENTDATA = {};
	public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;//数组初始化为一个空数组
    }
    public boolean add(E e) {
        //查看当前数组是否够多存一个元素
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {//如果当前数组还是空数组
            //minCapacity按照 默认初始容量和minCapacity中的的最大值处理
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
		//看是否需要扩容处理
        ensureExplicitCapacity(minCapacity);
    }
	//...
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//初始化为空数组
    }
    public boolean add(E e) {
        //查看当前数组是否够多存一个元素
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        
        //存入新元素到[size]位置，然后size自增1
        elementData[size++] = e;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        //如果当前数组还是空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //那么minCapacity取DEFAULT_CAPACITY与minCapacity的最大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
		//查看是否需要扩容
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//修改次数加1

        // 如果需要的最小容量  比  当前数组的长度  大，即当前数组不够存，就扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//当前数组容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新数组容量是旧数组容量的1.5倍
        //看旧数组的1.5倍是否够
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //看旧数组的1.5倍是否超过最大数组限制
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        
        //复制一个新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    public boolean remove(Object o) {
        //先找到o在当前ArrayList的数组中的下标
        //分o是否为空两种情况讨论
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {//null值用==比较
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {//非null值用equals比较
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    private void fastRemove(int index) {
        modCount++;//修改次数加1
        //需要移动的元素个数
        int numMoved = size - index - 1;
        
        //如果需要移动元素，就用System.arraycopy移动元素
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        
        //将elementData[size-1]位置置空，让GC回收空间，元素个数减少
        elementData[--size] = null; // clear to let GC do its work
    }
    public E remove(int index) {
        rangeCheck(index);//检验index是否合法

        modCount++;//修改次数加1
        
        //取出[index]位置的元素，[index]位置的元素就是要被删除的元素，用于最后返回被删除的元素
        E oldValue = elementData(index);
        
		//需要移动的元素个数
        int numMoved = size - index - 1;
        
        //如果需要移动元素，就用System.arraycopy移动元素
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将elementData[size-1]位置置空，让GC回收空间，元素个数减少
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
    public E set(int index, E element) {
        rangeCheck(index);//检验index是否合法

        //取出[index]位置的元素，[index]位置的元素就是要被替换的元素，用于最后返回被替换的元素
        E oldValue = elementData(index);
        //用element替换[index]位置的元素
        elementData[index] = element;
        return oldValue;
    }
    public E get(int index) {
        rangeCheck(index);//检验index是否合法

        return elementData(index);//返回[index]位置的元素
    }
    public int indexOf(Object o) {
        //分为o是否为空两种情况
        if (o == null) {
            //从前往后找
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    public int lastIndexOf(Object o) {
         //分为o是否为空两种情况
        if (o == null) {
            //从后往前找
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

③ LinkedList源码分析

int size = 0;
Node<E> first;//记录第一个结点的位置
Node<E> last;//记录最后一个结点的位置

   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) {
       final Node<E> l = last;//用l 记录原来的最后一个结点
       
       //创建新结点
       final Node<E> newNode = new Node<>(l, e, null);
       //现在的新结点是最后一个结点了
       last = newNode;
       
       //如果l==null，说明原来的链表是空的
       if (l == null)
           //那么新结点同时也是第一个结点
           first = newNode;
       else
           //否则把新结点链接到原来的最后一个结点的next中
           l.next = newNode;
       //元素个数增加
       size++;
       //修改次数增加
       modCount++;
   }

   public void add(int index, E element) {
       checkPositionIndex(index);//检查index范围

       if (index == size)//如果index==size，连接到当前链表的尾部
           linkLast(element);
       else
           linkBefore(element, node(index));
   }

   Node<E> node(int index) {
       // assert isElementIndex(index);

       //如果index<size/2，就从前往后找目标结点
       if (index < (size >> 1)) {
           Node<E> x = first;
           for (int i = 0; i < index; i++)
               x = x.next;
           return x;
       } else {//否则从后往前找目标结点
           Node<E> x = last;
           for (int i = size - 1; i > index; i--)
               x = x.prev;
           return x;
       }
   }

//把新结点插入到[index]位置的结点succ前面
   void linkBefore(E e, Node<E> succ) {//succ是[index]位置对应的结点
       // assert succ != null;
       final Node<E> pred = succ.prev; //[index]位置的前一个结点
       
       //新结点的prev是原来[index]位置的前一个结点
       //新结点的next是原来[index]位置的结点
       final Node<E> newNode = new Node<>(pred, e, succ);
       
       //[index]位置对应的结点的prev指向新结点
       succ.prev = newNode;
       
       //如果原来[index]位置对应的结点是第一个结点，那么现在新结点是第一个结点
       if (pred == null)
           first = newNode;
       else
           pred.next = newNode;//原来[index]位置的前一个结点的next指向新结点
       size++;
       modCount++;
   }
   public boolean remove(Object o) {
       //分o是否为空两种情况
       if (o == null) {
           //找到o对应的结点x
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null) {
                   unlink(x);//删除x结点
                   return true;
               }
           }
       } else {
           //找到o对应的结点x
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item)) {
                   unlink(x);//删除x结点
                   return true;
               }
           }
       }
       return false;
   }
   E unlink(Node<E> x) {//x是要被删除的结点
       // assert x != null;
       final E element = x.item;//被删除结点的数据
       final Node<E> next = x.next;//被删除结点的下一个结点
       final Node<E> prev = x.prev;//被删除结点的上一个结点

       //如果被删除结点的前面没有结点，说明被删除结点是第一个结点
       if (prev == null) {
           //那么被删除结点的下一个结点变为第一个结点
           first = next;
       } else {//被删除结点不是第一个结点
           //被删除结点的上一个结点的next指向被删除结点的下一个结点
           prev.next = next;
           //断开被删除结点与上一个结点的链接
           x.prev = null;//使得GC回收
       }

       //如果被删除结点的后面没有结点，说明被删除结点是最后一个结点
       if (next == null) {
           //那么被删除结点的上一个结点变为最后一个结点
           last = prev;
       } else {//被删除结点不是最后一个结点
           //被删除结点的下一个结点的prev执行被删除结点的上一个结点
           next.prev = prev;
           //断开被删除结点与下一个结点的连接
           x.next = null;//使得GC回收
       }
	//把被删除结点的数据也置空，使得GC回收
       x.item = null;
       //元素个数减少
       size--;
       //修改次数增加
       modCount++;
       //返回被删除结点的数据
       return element;
   }

4、Set接口

（1）Set接口

• Set接口是Collection的子接口，set接口没有提供额外的方法，但是比Collection接口更加严格了

• Set接口特点：

• • 不可重复：如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败

（2）Set接口的实现类

• Set的常用实现类

• • HashSet：HashSet 是 Set 接口的典型实现
• • • 存储结构：哈希表（底层的实现是java.util.HashMap支持，HashMap的底层物理实现是一个哈希表）
    • HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取和查找性能
    • 存储到HashSet的元素要重写hashCode和equals方法（HashSet 集合判断两个元素相等的标准：两个对象通过 hashCode() 方法比较相等，并且两个对象的 equals() 方法返回值也相等）
• • LinkedHashSet：java.util.LinkedHashSet，是HashSet的子类，它在HashSet的基础上，在结点中增加before和after两个属性，维护了结点的前后添加顺序
• • • 存储结构：链表和哈希表组合
    • LinkedHashSet插入性能略低于 HashSet，但在迭代访问Set里的全部元素时有很好的性能
• • TreeSet
• • • TreeSet里面维护了一个TreeMap，底层是基于红黑树实现的
    • 特点
• • • • 不允许重复
      • 实现排序：
• • • • • 自然排序（实现Comparable接口，重写compareTo）
        • 定制排序（实现Comparator接口，重写compare）

• Set底层实现原理：Set的内部实现其实是一个Map。即HashSet的内部实现是一个HashMap，TreeSet的内部实现是一个TreeMap，LinkedHashSet的内部实现是一个LinkedHashMap。把添加到Set中的元素作为内部实现map的key，然后用一个常量对象PRESENT对象，作为value

① HashSet源码

   public HashSet() {
       map = new HashMap<>();
   }

   public HashSet(Collection<? extends E> c) {
       map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
       addAll(c);
   }

   public HashSet(int initialCapacity, float loadFactor) {
       map = new HashMap<>(initialCapacity, loadFactor);
   }

   public HashSet(int initialCapacity) {
       map = new HashMap<>(initialCapacity);
   }

//这个构造器是给子类LinkedHashSet调用的
   HashSet(int initialCapacity, float loadFactor, boolean dummy) {
       map = new LinkedHashMap<>(initialCapacity, loadFactor);
   }

② LinkedHashSet源码

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);//调用HashSet的某个构造器
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);//调用HashSet的某个构造器
}

public LinkedHashSet() {
    super(16, .75f, true);
}

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);//调用HashSet的某个构造器
    addAll(c);
}

③ TreeSet源码

public TreeSet() {
    this(new TreeMap<E,Object>());
}

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

三、Map

1、Map接口

• Java提供了专门的集合类用来存放映射对象关系的对象，即java.util.Map<K,V>接口

• Collection中的集合称为单列集合，Map中的集合称为双列集合

• Map中的集合不能包含重复的键，值可以重复；每个键只能对应一个值

2、Map集合的遍历

（1）分开遍历

• 单独遍历所有key
• 单独遍历所有value

（2）成对遍历

• 遍历的是映射关系Map.Entry类型的对象，Map.Entry是Map接口的内部接口。每一种Map内部有自己的Map.Entry的实现类。在Map中存储数据，实际上是将Key—->value的数据存储在Map.Entry接口的实例中，再在Map集合中插入Map.Entry的实例化对象

3、Map的实现类

• Map接口的常用实现类

• • HashMap：使用频率最高的实现类
• • • 底层原理：哈希表
    • 存储到HashSet的元素要重写hashCode和equals方法（判断两个 key 相等的标准：两个key的hashCode值相等，并且equals() 方法也返回true）
• • Hashtable：同HashMap（线程安全，且不允许使用null值和null键）
  • LinkedHashMap：HashMap的子类，与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）
  • TreeMap：基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法

附录1：二叉树

1、二叉树的基本概念

• 二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要

2、二叉树的遍历

• 前序遍历：中左右（根左右）ABDHIECFG
• 中序遍历：左中右（左根右）HDIBEAFCG
• 后序遍历：左右中（左右根）HIDEBFGCA

3、经典二叉树

1、满二叉树： 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。 第n层的结点数是2的n-1次方，总的结点个数是2的n次方-1

2、完全二叉树： 叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧

3、平衡二叉树：平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，但不要求非叶节点都有两个子结点 。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等

例如红黑树的要求：

• 节点是红色或者黑色
• 根节点是黑色
• 每个叶子的节点都是黑色的空节点（NULL）
• 每个红色节点的两个子节点都是黑色的
• 从任意节点到其每个叶子的所有路径都包含相同的黑色节点数量。

当我们插入或删除节点时，可能会破坏已有的红黑树，使得它不满足以上5个要求，那么此时就需要进行处理：

• recolor ：将某个节点变红或变黑
• rotation ：将红黑树某些结点分支进行旋转（左旋或右旋）

4、二叉树的实现

public class BinaryTree<E>{
    private Node root; //二叉树的根结点
    private int total;//结点总个数

    private class Node{
        Node parent;
        Node left;
        E data;
        Node right;

        public Node(Node parent, Node left, E data, Node right) {
            this.parent = parent;
            this.left = left;
            this.data = data;
            this.right = right;
        }
    }
}
public class TreeMap<K,V> {
    private transient Entry<K,V> root;
    private transient int size = 0;

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;

        /**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    }
}

附录2：哈希表(了解)

1、hashCode值

• hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法，它将任意大小的数据映射到一个固定大小的序列上，这个序列被称为hash code、数据摘要或者指纹。
• 比较出名的hash算法有MD5、SHA。hash是具有唯一性且不可逆的，唯一性是指相同的“对象”产生的hash code永远是一样的

2、哈希表的物理结构

HashMap和Hashtable是散列表，其中维护了一个长度为2的幂次方的Entry类型的数组table，数组的每一个元素被称为一个桶(bucket)，你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象，放到了某个table[index]桶中。使用数组的目的是查询和添加的效率高，可以根据索引直接定位到某个table[index]

（1）数组元素类型：Map.Entry

JDK1.7：

• 映射关系被封装为HashMap.Entry类型，而这个类型实现了Map.Entry接口
• 观察HashMap.Entry类型是个结点类型，即table[index]下的映射关系可能串起来一个链表。因此我们把table[index]称为“桶bucket”

public class HashMap<K,V>{
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;
            int hash;
            //...省略
    }
    //...
}

JDK1.8：

• 映射关系被封装为HashMap.Node类型或HashMap.TreeNode类型，它俩都直接或间接的实现了Map.Entry接口
• 存储到table数组的可能是Node结点对象，也可能是TreeNode结点对象，即table[index]下的映射关系可能串起来一个链表或一棵红黑树

public class HashMap<K,V>{
    transient Node<K,V>[] table;
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
            //...省略
    }
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;
        boolean red;//是红结点还是黑结点
        //...省略
    }
    //....
}
public class LinkedHashMap<K,V>{
	static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    //...
}

（2）HashMap决定某个映射关系存在的桶

因为hash值是一个整数，而数组的长度也是一个整数，有两种思路：

① hash 值 % table.length会得到一个[0,table.length-1]范围的值，正好是下标范围，但是用%运算效率没有位运算符&高

② hash 值 & (table.length-1)，任何数 & (table.length-1)的结果也一定在[0, table.length-1]范围

hashCode值是   ？
table.length是10
table.length-1是9

？   ????????
9	 00001001
&_____________
	 00000000	[0]
	 00000001	[1]
	 00001000	[8]
	 00001001	[9]
	 一定[0]~[9]
hashCode值是   ？
table.length是16
table.length-1是15

？   ????????
15	 00001111
&_____________
	 00000000	[0]
	 00000001	[1]
	 00000010	[2]
	 00000011	[3]
	 ...
	 00001111    [15]
	 范围是[0,15]，一定在[0,table.length-1]范围内

JDK1.7：

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1); //此处h就是hash
}

JDK1.8：

    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)  // i = (n - 1) & hash
            tab[i] = newNode(hash, key, value, null);
        //....省略大量代码
}

（3）数组的长度始终是2的n次幂

• table数组的默认初始化长度：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

• 如果手动指定的table长度不是2的n次幂，会通过如下方法纠正为2的n次幂

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

• 如果数组不够，扩容了还是2的n次幂，因为每次数组扩容为原来的2倍

   void addEntry(int hash, K key, V value, int bucketIndex) {
       if ((size >= threshold) && (null != table[bucketIndex])) {
           resize(2 * table.length);//扩容为原来的2倍
           hash = (null != key) ? hash(key) : 0;
           bucketIndex = indexFor(hash, table.length);
       }
       createEntry(hash, key, value, bucketIndex);
   }
   final Node<K,V>[] resize() {
       Node<K,V>[] oldTab = table;
       int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldCap原来的容量
       int oldThr = threshold;
       int newCap, newThr = 0;
       if (oldCap > 0) {
           if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
               return oldTab;
           }//newCap = oldCap << 1  新容量=旧容量扩容为原来的2倍
           else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
               newThr = oldThr << 1; // double threshold
       	}
  		//......此处省略其他代码
}

• 保持2的n次幂原因：如果数组的长度为2的n次幂，那么table.length-1的二进制就是一个高位全是0，低位全是1的数字，这样才能保证每一个下标位置都有机会被用到

hashCode值是   ？
table.length是10
table.length-1是9

？   ????????
9	 00001001
&_____________
	 00000000	[0]
	 00000001	[1]
	 00001000	[8]
	 00001001	[9]
	 一定[0]~[9]
hashCode值是   ？
table.length是16
table.length-1是15

？   ????????
15	 00001111
&_____________
	 00000000	[0]
	 00000001	[1]
	 00000010	[2]
	 00000011	[3]
	 ...
	 00001111    [15]
	 范围是[0,15]，一定在[0,table.length-1]范围内

（4）hash是hashCode的再运算

• 不管是JDK1.7还是JDK1.8中，都不是直接用key的hashCode值直接与table.length-1计算求下标的，而是先对key的hashCode值进行了一个运算，JDK1.7和JDK1.8关于hash()的实现代码不一样，但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果，尽量的均匀分布。虽然算法不同，但是思路都是将hashCode值的高位二进制与低位二进制值进行了异或，然高位二进制参与到index的计算中

   final int hash(Object k) {
       int h = hashSeed;
       if (0 != h && k instanceof String) {
           return sun.misc.Hashing.stringHash32((String) k);
       }

       h ^= k.hashCode();
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
   }
static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

• 将hashCode值的二进制的高位参与到index计算的原因：因为一个HashMap的table数组一般不会特别大，至少在不断扩容之前，那么table.length-1的大部分高位都是0，直接用hashCode和table.length-1进行&运算的话，就会导致总是只有最低的几位是有效的，那么就算hashCode()实现的再好也难以避免发生碰撞，这时让高位参与进来的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征，显著减少了碰撞冲突的发生

（5）解决[index]冲突问题

• 虽然从设计hashCode()到上面HashMap的hash()函数，都尽量减少冲突，但是仍然存在两个不同的对象返回的hashCode值相同，或者hashCode值就算不同，通过hash()函数计算后，得到的index也会存在大量的相同，因此key分布完全均匀的情况是不存在的

• 解决碰撞冲突

• • JDK1.8之前使用：数组+链表的结构
  • JDK1.8之后使用：数组+链表/红黑树的结构
  • 即hash相同或hash&(table.lengt-1)的值相同，那么就存入同一个“桶”table[index]中，使用链表或红黑树连接起来

• JDK1.8红黑树和链表共存原因

• • 当冲突比较严重时，table[index]下面的链表就会很长，那么会导致查找效率大大降低，而如果此时选用二叉树可以大大提高查询效率
  • 但是二叉树的结构又过于复杂，如果结点个数比较少的时候，那么选择链表反而更简单

（6）树化和反树化

static final int TREEIFY_THRESHOLD = 8;//树化阈值
static final int UNTREEIFY_THRESHOLD = 6;//反树化阈值
static final int MIN_TREEIFY_CAPACITY = 64;//最小树化容量

• 当某table[index]下的链表的结点个数达到8，并且table.length>=64，那么如果新Entry对象还添加到该table[index]中，那么就会将table[index]的链表进行树化

• 当某table[index]下的红黑树结点个数少于6个，此时，

• • 当继续删除table[index]下的树结点，最后这个根结点的左右结点有null，或根结点的左结点的左结点为null，会反树化
  • 当重新添加新的映射关系到map中，导致了map重新扩容了，这个时候如果table[index]下面还是小于等于6的个数，那么会反树化

package com.atguigu.map;

public class MyKey{
    int num;

    public MyKey(int num) {
        super();
        this.num = num;
    }

    @Override
    public int hashCode() {
        if(num<=20){
            return 1;
        }else{
            final int prime = 31;
            int result = 1;
            result = prime * result + num;
            return result;
        }
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        MyKey other = (MyKey) obj;
        if (num != other.num)
            return false;
        return true;
    }

}
package com.atguigu.map;

import org.junit.Test;

import java.util.HashMap;

public class TestHashMapMyKey {
    @Test
    public void test1(){
        //这里为了演示的效果，我们造一个特殊的类，这个类的hashCode（）方法返回固定值1
        //因为这样就可以造成冲突问题，使得它们都存到table[1]中
        HashMap<MyKey, String> map = new HashMap<>();
        for (int i = 1; i <= 11; i++) {
            map.put(new MyKey(i), "value"+i);//树化演示
        }
    }
    @Test
    public void test2(){
        HashMap<MyKey, String> map = new HashMap<>();
        for (int i = 1; i <= 11; i++) {
            map.put(new MyKey(i), "value"+i);
        }
        for (int i = 1; i <=11; i++) {
            map.remove(new MyKey(i));//反树化演示
        }
    }
    @Test
    public void test3(){
        HashMap<MyKey, String> map = new HashMap<>();
        for (int i = 1; i <= 11; i++) {
            map.put(new MyKey(i), "value"+i);
        }

        for (int i = 1; i <=5; i++) {
            map.remove(new MyKey(i));
        }//table[1]下剩余6个结点

        for (int i = 21; i <= 100; i++) {
            map.put(new MyKey(i), "value"+i);//添加到扩容时，反树化
        }
    }
}

3、JDK1.7的put方法源码分析

（1）关键常量和变量

int DEFAULT_INITIAL_CAPACITY = 1 << 4;//16  目的是体现2的n次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;
int threshold;
threshold = table.length * loadFactor;
final float loadFactor;

• 负载因子的值

• • 如果太大，threshold就会很大，那么如果冲突比较严重的话，就会导致table[index]下面的结点个数很多，影响效率
  • 如果太小，threshold就会很小，那么数组扩容的频率就会提高，数组的使用率也会降低，那么会造成空间的浪费

    public HashMap() {
    	//DEFAULT_INITIAL_CAPACITY：默认初始容量16
    	//DEFAULT_LOAD_FACTOR：默认加载因子0.75
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    public HashMap(int initialCapacity, float loadFactor) {
        //校验initialCapacity合法性
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
        //校验initialCapacity合法性                                       initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //校验loadFactor合法性
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
		//加载因子，初始化为0.75
        this.loadFactor = loadFactor;
        // threshold 初始为初始容量                                  
        threshold = initialCapacity;
        init();
    }
public V put(K key, V value) {
        //如果table数组是空的，那么先创建数组
        if (table == EMPTY_TABLE) {
            //threshold一开始是初始容量的值
            inflateTable(threshold);
        }
        //如果key是null，单独处理，存储到table[0]中，如果有另一个key为null，value覆盖
        if (key == null)
            return putForNullKey(value);
        
        //对key的hashCode进行干扰，算出一个hash值
    /*
    hashCode值      xxxxxxxxxx
   table.length-1   000001111
   
   hashCode值 xxxxxxxxxx  无符号右移几位和原来的hashCode值做^运算，使得hashCode高位二进制值参与计算，也发挥作用，降低index冲突的概率。
    */
        int hash = hash(key);
        
        //计算新的映射关系应该存到table[i]位置，
        //i = hash & table.length-1，可以保证i在[0,table.length-1]范围内
        int i = indexFor(hash, table.length);
        
        //检查table[i]下面有没有key与我新的映射关系的key重复，如果重复替换value
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //添加新的映射关系
        addEntry(hash, key, value, i);
        return null;
    }
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);//容量是等于toSize值的最接近的2的n次方
		//计算阈值 = 容量 * 加载因子
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //创建Entry[]数组，长度为capacity
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }
	//如果key是null，直接存入[0]的位置
    private V putForNullKey(V value) {
        //判断是否有重复的key，如果有重复的，就替换value
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //把新的映射关系存入[0]的位置，而且key的hash值用0表示
        addEntry(0, null, value, 0);
        return null;
    }
    void addEntry(int hash, K key, V value, int bucketIndex) {
        //判断是否需要库容
        //扩容：（1）size达到阈值（2）table[i]正好非空
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //table扩容为原来的2倍，并且扩容后，会重新调整所有映射关系的存储位置
            resize(2 * table.length);
            //新的映射关系的hash和index也会重新计算
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
		//存入table中
        createEntry(hash, key, value, bucketIndex);
    }
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        //原来table[i]下面的映射关系作为新的映射关系next
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;//个数增加
    }

（2）put(key,value)实现步骤

1. 当第一次添加映射关系时，数组初始化为一个长度为16的HashMap$Entry的数组，这个HashMap$Entry类型是实现了java.util.Map.Entry接口
2. 特殊考虑：如果key为null，index直接是[0],hash也是0
3. 如果key不为null，在计算index之前，会对key的hashCode()值，做一个hash(key)再次哈希的运算，这样可以使得Entry对象更加散列的存储到table中
4. 计算index = table.length-1 & hash;
5. 如果table[index]下面，已经有映射关系的key与我要添加的新的映射关系的key相同了，会用新的value替换旧的value
6. 如果没有相同的，会把新的映射关系添加到链表的头，原来table[index]下面的Entry对象连接到新的映射关系的next中
7. 添加之前先判断if(size >= threshold && table[index]!=null)如果该条件为true，会扩容

if(size >= threshold  &&  table[index]!=null){

	①会扩容

	②会重新计算key的hash

	③会重新计算index

}

1. size++

（3）get(key)实现步骤

1. 计算key的hash值，用这个方法hash(key)
2. 找index = table.length-1 & hash;
3. 如果table[index]不为空，那么就挨个比较哪个Entry的key与它相同，就返回它的value

（4）remove(key)实现步骤

1. 计算key的hash值，用这个方法hash(key)
2. 找index = table.length-1 & hash;
3. 如果table[index]不为空，那么就挨个比较哪个Entry的key与它相同，就删除它，把它前面的Entry的next的值修改为被删除Entry的next

4、JDK1.8的put方法源码分析

（1）关键常量和变量

几个常量和变量：
（1）DEFAULT_INITIAL_CAPACITY：默认的初始容量 16
（2）MAXIMUM_CAPACITY：最大容量  1 << 30
（3）DEFAULT_LOAD_FACTOR：默认加载因子 0.75
（4）TREEIFY_THRESHOLD：默认树化阈值8，当链表的长度达到这个值后，要考虑树化
（5）UNTREEIFY_THRESHOLD：默认反树化阈值6，当树中的结点的个数达到这个阈值后，要考虑变为链表
（6）MIN_TREEIFY_CAPACITY：最小树化容量64
		当单个的链表的结点个数达到8，并且table的长度达到64，才会树化。
		当单个的链表的结点个数达到8，但是table的长度未达到64，会先扩容
（7）Node<K,V>[] table：数组
（8）size：记录有效映射关系的对数，也是Entry对象的个数
（9）int threshold：阈值，当size达到阈值时，考虑扩容
（10）double loadFactor：加载因子，影响扩容的频率
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
        // all other fields defaulted，其他字段都是默认值
    }
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
	//目的：干扰hashCode值
    static final int hash(Object key) {
        int h;
		//如果key是null，hash是0
		//如果key非null，用key的hashCode值 与 key的hashCode值高16进行异或
		//		即就是用key的hashCode值高16位与低16位进行了异或的干扰运算
		
		/*
		index = hash & table.length-1
		如果用key的原始的hashCode值  与 table.length-1 进行按位与，那么基本上高16没机会用上。
		这样就会增加冲突的概率，为了降低冲突的概率，把高16位加入到hash信息中。
		*/
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; //数组
		Node<K,V> p; //一个结点
		int n, i;//n是数组的长度   i是下标
		
		//tab和table等价
		//如果table是空的
        if ((tab = table) == null || (n = tab.length) == 0){
            n = (tab = resize()).length;
            /*
			tab = resize();
			n = tab.length;*/
			/*
			如果table是空的，resize()完成了①创建了一个长度为16的数组②threshold = 12
			n = 16
			*/
        }
		//i = (n - 1) & hash ，下标 = 数组长度-1 & hash
		//p = tab[i] 第1个结点
		//if(p==null) 条件满足的话说明 table[i]还没有元素
		if ((p = tab[i = (n - 1) & hash]) == null){
			//把新的映射关系直接放入table[i]
            tab[i] = newNode(hash, key, value, null);
			//newNode（）方法就创建了一个Node类型的新结点，新结点的next是null
        }else {
            Node<K,V> e; 
			K k;
			//p是table[i]中第一个结点
			//if(table[i]的第一个结点与新的映射关系的key重复)
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))){
                e = p;//用e记录这个table[i]的第一个结点
			}else if (p instanceof TreeNode){//如果table[i]第一个结点是一个树结点
                //单独处理树结点
                //如果树结点中，有key重复的，就返回那个重复的结点用e接收，即e!=null
                //如果树结点中，没有key重复的，就把新结点放到树中，并且返回null，即e=null
				e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            }else {
				//table[i]的第一个结点不是树结点，也与新的映射关系的key不重复
				//binCount记录了table[i]下面的结点的个数
                for (int binCount = 0; ; ++binCount) {
					//如果p的下一个结点是空的，说明当前的p是最后一个结点
                    if ((e = p.next) == null) {
						//把新的结点连接到table[i]的最后
                        p.next = newNode(hash, key, value, null);
						
						//如果binCount>=8-1，达到7个时
                        if (binCount >= TREEIFY_THRESHOLD - 1){ // -1 for 1st
                            //要么扩容，要么树化
							treeifyBin(tab, hash);
						}
                        break;
                    }
					//如果key重复了，就跳出for循环，此时e结点记录的就是那个key重复的结点
            if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))){
                        break;
					}
                    p = e;//下一次循环，e=p.next，就类似于e=e.next，往链表下移动
                }
            }
			//如果这个e不是null，说明有key重复，就考虑替换原来的value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null){
                    e.value = value;
				}
                afterNodeAccess(e);//什么也没干
                return oldValue;
            }
        }
        ++modCount;
		
		//元素个数增加
		//size达到阈值
        if (++size > threshold){
            resize();//一旦扩容，重新调整所有映射关系的位置
		}
        afterNodeInsertion(evict);//什么也没干
        return null;
    }	
	
   final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//oldTab原来的table
		//oldCap：原来数组的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
		
		//oldThr：原来的阈值
        int oldThr = threshold;//最开始threshold是0
		
		//newCap，新容量
		//newThr：新阈值
        int newCap, newThr = 0;
        if (oldCap > 0) {//说明原来不是空数组
            if (oldCap >= MAXIMUM_CAPACITY) {//是否达到数组最大限制
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY){
				//newCap = 旧的容量*2 ，新容量<最大数组容量限制
				//新容量：32,64，...
				//oldCap >= 初始容量16
				//新阈值重新算 = 24，48 ....
                newThr = oldThr << 1; // double threshold
			}
        }else if (oldThr > 0){ // initial capacity was placed in threshold
            newCap = oldThr;
        }else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;//新容量是默认初始化容量16
			//新阈值= 默认的加载因子 * 默认的初始化容量 = 0.75*16 = 12
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;//阈值赋值为新阈值12，24.。。。
		
		//创建了一个新数组，长度为newCap，16，32,64.。。
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
		
		
        if (oldTab != null) {//原来不是空数组
			//把原来的table中映射关系，倒腾到新的table中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {//e是table下面的结点
                    oldTab[j] = null;//把旧的table[j]位置清空
                    if (e.next == null)//如果是最后一个结点
                        newTab[e.hash & (newCap - 1)] = e;//重新计算e的在新table中的存储位置，然后放入
                    else if (e instanceof TreeNode)//如果e是树结点
						//把原来的树拆解，放到新的table
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
						/*
						把原来table[i]下面的整个链表，重新挪到了新的table中
						*/
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }	
	
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
		//创建一个新结点
	   return new Node<>(hash, key, value, next);
    }

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; 
		Node<K,V> e;
		//MIN_TREEIFY_CAPACITY：最小树化容量64
		//如果table是空的，或者  table的长度没有达到64
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();//先扩容
        else if ((e = tab[index = (n - 1) & hash]) != null) {
			//用e记录table[index]的结点的地址
            TreeNode<K,V> hd = null, tl = null;
			/*
			do...while，把table[index]链表的Node结点变为TreeNode类型的结点
			*/
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;//hd记录根结点
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
			
            //如果table[index]下面不是空
            if ((tab[index] = hd) != null)
                hd.treeify(tab);//将table[index]下面的链表进行树化
        }
    }

（2）添加实现步骤

1. 先计算key的hash值，如果key是null，hash值就是0，如果为null，使用(h = key.hashCode()) ^ (h >>> 16)得到hash值

2. 如果table是空的，先初始化table数组

3. 通过hash值计算存储的索引位置index = hash & (table.length-1)

4. 如果table[index]==null，那么直接创建一个Node结点存储到table[index]中即可

5. 如果table[index]!=null

6. 1. 判断table[index]的根结点的key是否与新的key“相同”（hash值相同并且(满足key的地址相同或key的equals返回true)），如果是那么用e记录这个根结点
   2. 如果table[index]的根结点的key与新的key“不相同”，而且table[index]是一个TreeNode结点，说明table[index]下是一棵红黑树，如果该树的某个结点的key与新的key“相同”（hash值相同并且(满足key的地址相同或key的equals返回true)），那么用e记录这个相同的结点，否则将(key,value)封装为一个TreeNode结点，连接到红黑树中
   3. 如果table[index]的根结点的key与新的key“不相同”，并且table[index]不是一个TreeNode结点，说明table[index]下是一个链表，如果该链表中的某个结点的key与新的key“相同”，那么用e记录这个相同的结点，否则将新的映射关系封装为一个Node结点直接链接到链表尾部，并且判断table[index]下结点个数达到TREEIFY_THRESHOLD(8)个，如果table[index]下结点个数已经达到，那么再判断table.length是否达到MIN_TREEIFY_CAPACITY(64)，如果没达到，那么先扩容，扩容会导致所有元素重新计算index，并调整位置，如果table[index]下结点个数已经达到TREEIFY_THRESHOLD(8)个并table.length也已经达到MIN_TREEIFY_CAPACITY(64)，那么会将该链表转成一棵自平衡的红黑树

7. 如果在table[index]下找到了新的key“相同”的结点，即e不为空，那么用新的value替换原来的value，并返回旧的value，结束put方法

8. 如果新增结点而不是替换，那么size++，并且还要重新判断size是否达到threshold阈值，如果达到，还要扩容

if(size > threshold ){
	①会扩容

	②会重新计算key的hash

	③会重新计算index

}

（3）remove(key)实现步骤

1. 计算key的hash值，用这个方法hash(key)
2. 找index = table.length-1 & hash;
3. 如果table[index]不为空，那么就挨个比较哪个Entry的key与它相同，就删除它，把它前面的Entry的next的值修改为被删除Entry的next
4. 如果table[index]下面原来是红黑树，结点删除后，个数小于等于6，会把红黑树变为链表

5、映射关系的key是否可以被修改

映射关系存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的映射关系，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上