关于java:面试补习-Java集合知识梳理

50次阅读

共计 32588 个字符，预计需要花费 82 分钟才能阅读完成。

一、ArrayList

ArrayList 底层数据结构为 动静数组，所以咱们能够将之称为数组队列。
ArrayList 的依赖关系：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

从依赖关系能够看出，ArrayList 首先是一个列表，其次，他具备列表的相干性能，反对疾速（固定工夫）定位资源地位。能够进行拷贝操作，同时反对序列化。这里咱们须要重点关注的是 AbstractLit 以及 RandomAccess。这个类，一个是定义了列表的根本属性，以及确定咱们列表中的惯例动作。而 RandomAccess 次要是提供了疾速定位资源地位的性能。

1.1、ArrayList 成员变量

  /**
     * Default initial capacity. 数组默认大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     空队列
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
        如果应用默认构造方法，则默认对象内容是该值
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
        用于存储数据
     */
    transient Object[] elementData; 

     // 以后队列无效数据长度
      private int size;

     // 数组最大值
     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

在 ArrayList 的源码中，次要有上述的几个成员变量：

  • elementData：动静数组，也就是咱们存储数据的外围数组
  • DEFAULT_CAPACITY：数组默认长度，在调用默认结构器的时候会有介绍
  • size：记录无效数据长度，size（）办法间接返回该值
  • MAX_ARRAY_SIZE：数组最大长度，如果扩容超过该值，则设置长度为 Integer.MAX_VALUE

拓展思考：
EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是两个空的数组对象，他们到底有什么区别呢？咱们在下一节解说构造方法的时候，会做具体比照。

1.2、构造方法

ArrayList 中提供了三种构造方法：

  • ArrayList()
  • ArrayList(int initialCapacity)
  • ArrayList（Collection<T> c）

依据结构器的不同，构造方法会有所区别。咱们在平时开发中，可能会呈现在默认结构器外部调用了 ArrayList（int capacity）这种形式，然而 ArrayList 中对于 不同的结构器的外部实现都有所区别，次要跟上述提到的成员变量无关。

1.2.1 ArrayList（）

在源码给出的正文中这样形容：结构一个初始容量为十的空列表

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

从源码能够看到，它只是将 elementData 指向了 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的存储地址，而 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 其实是一个空的数组对象，那么它为什么说创立一个默认大小为 10 的列表呢？

或者咱们从别的角度思考一下，如果这个空的数组，须要增加元素，会怎么样？

    public boolean add(E e) {ensureCapacityInternal(size + 1);  // 确认外部容量
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        // 如果 elementData 指向的是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            设置默认大小 为 DEFAULT_CAPACITY
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 确定理论容量
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果超出了容量，进行扩大
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    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);
    }

上述代码块比拟长，这里做个简略的总结：

1、add（E e）：增加元素，首先会判断 elementData 数组的长度，而后设置值

2、ensureCapacityInternal（int minCapacity）：判断 element 是否为空，如果是，则设置默认数组长度

3、ensureExplicitCapacity（int minCapacity）：判断预期增长数组长度是否超过以后容量，如果过超过，则调用 grow（）

4、grow(int minCapacity)：对数组进行扩大

回到方才的问题：为什么说创立一个默认大小为 10 的列表呢？或者你曾经找到答案了～

1.2.2 ArrayList(int initialCapacity)

依据指定大小初始化 ArrayList 中的数组大小，如果默认值大于 0，依据参数进行初始化，如果等于 0，指向 EMPTY_ELEMENTDATA 内存地址（与上述默认结构器用法类似）。如果小于 0，则抛出 IllegalArgumentException 异样。

public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {
            throw new IllegalArgumentException("Illegal Capacity:"+
                                               initialCapacity);
        }
    }

拓展思考：为什么这里是用 EMPTY_ELEMENTDATA 而不是跟默认结构器一样应用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA？有趣味的童鞋能够本人县思考，通过思考的常识，才是你的～

1.2.3 ArrayList（Collection<T> c）

将 Collection\<T> c 中保留的数据，首先转换成数组模式（toArray（）办法），而后判断以后数组长度是否为 0，为 0 则只想默认数组（EMPTY_ELEMENTDATA）；否则进行数据拷贝。

    public ArrayList(Collection<? extends E> c) {elementData = c.toArray();
        if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

1.2.4 总结

上述的三个构造方法能够看出，其实每个结构器外部做的事件都不一样，特地是默认结构器与 ArrayList(int initialCapacity) 这两个结构器间接的区别，咱们是须要做一些区别的。

  • ArrayList（）：指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当列表应用的时候，才会进行初始化，会通过判断是不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个对象而设置数组默认大小。
  • ArrayList(int initialCapacity)：当 initialCapacity >0 的时候，设置该长度。如果 initialCapacity =0，则指向 EMPTY_ELEMENTDATA 在应用的时候，并不会设置默认数组长度。

因而 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 与 EMPTY_ELEMENTDATA 的本质区别就在于，会不会设置默认的数组长度。

1.3、增加办法（Add）

ArrayList 增加了四种增加办法：

  • add(E element)
  • add(int i , E element)
  • addAll(Collection<? extends E> c)
  • addAll(int index, Collection<? extends E> c)

1.3.1 add(E element)

首先看 add（T t）的源码：

  public boolean add(E e) {ensureCapacityInternal(size + 1);  // 元素个数加一，并且确认数组长度是否足够 
        elementData[size++] = e;        // 在列表最初一个元素后增加数据。return true;
    }

联合默认结构器或其余结构器中，如果默认数组为空，则会在 ensureCapacityInternal（）办法调用的时候进行数组初始化。这就是为什么默认结构器调用的时候，咱们创立的是一个空数组，然而在正文里却介绍为 长度为 10 的数组。

1.3.2 add（int i , T t）

   public void add(int index, E element) {
    // 判断 index 是否无效
        rangeCheckForAdd(index);
    // 计数 +1，并确认以后数组长度是否足够
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index); // 将 index 前面的数据都往后移一位
        elementData[index] = element; // 设置指标数据
        size++;
    }

这个办法其实和下面的 add 相似，该办法能够依照元素的地位，指定地位插入元素，具体的执行逻辑如下：

1）确保数插入的地位小于等于以后数组长度，并且不小于 0，否则抛出异样

2）确保数组已应用长度（size）加 1 之后足够存下 下一个数据

3）批改次数（modCount）标识自增 1，如果以后数组已应用长度（size）加 1 后的大于以后的数组长度，则调用 grow 办法，增长数组

4）grow 办法会将以后数组的长度变为原来容量的 1.5 倍。

5）确保有足够的容量之后，应用 System.arraycopy 将须要插入的地位（index）前面的元素通通往后挪动一位。

6）将新的数据内容寄存到数组的指定地位（index）上

1.3.3 addAll(Collection<? extends E> c)

    public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

addAll() 办法，通过将 collection 中的数据转换成 Array[] 而后增加到 elementData 数组，从而实现整个汇合数据的增加。在整体上没有什么特地之初，这里的 collection 可能会抛出管制异样 NullPointerException 须要留神一下。

1.3.4 addAll(int index，Collection<? extends E> c)

 public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

与上述办法相比，这里次要多了两个步骤，判断增加数据的地位是不是在开端，如果在两头，则须要先将数据向后挪动 collection 长度 的地位。

1.4、删除办法（Remove）

ArrayList 中提供了 五种删除数据的形式：

  • remove（int i）
  • remove（E element）
  • removeRange（int start,int end）
  • clear（）
  • removeAll（Collection<T> c）

1.4.1、remove（int i）:

删除数据并不会更改数组的长度，只会将数据重数组种移除，如果指标没有其余无效援用，则在 GC 时会进行回收。

public E remove(int index) {rangeCheck(index); // 判断索引是否无效
        modCount++;
        E oldValue = elementData(index);  // 获取对应数据
        int numMoved = size - index - 1;  // 判断删除数据地位
        if (numMoved > 0) // 如果删除数据不是最初一位，则须要挪动数组
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // 让指针最初指向空，进行垃圾回收
        return oldValue;
    }

1.4.2、remove（E element）:

这种形式，会在外部进行 AccessRandom 形式遍历数组，当匹配到数据跟 Object 相等，则调用 fastRemove（）进行删除

public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)
                if (elementData[index] == null) {fastRemove(index);
                    return true;
                }
        } else {for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {fastRemove(index);
                    return true;
                }
        }
        return false;
    }

fastRemove():
fastRemove 操作与上述的依据下标进行删除其实是统一的。

   private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

1.4.3、removeRange（int fromIndex, int toIndex）

该办法次要删除了在范畴内的数据，通过 System.arraycopy 对整局部的数据进行笼罩即可。

    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {elementData[i] = null;
        }
        size = newSize;
    }

1.4.4、clear（）

间接将整个数组设置为 null，这里不做细述。

1.4.5、removeAll（Collection<T> c）

次要通过调用：

    private boolean batchRemove(Collection<?> c, boolean complement) {
        // 获取数组指针
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {for (; r < size; r++)
                // 依据 complement 进行判断删除或留下
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // 进行数据整顿
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

在 retainAll（Collection<T> c）也有调用，次要作用别离为，删除这个汇合中所蕴含的元素和留下这个汇合中所蕴含的元素。

拓展思考

分明 ArrayList 的删除办法后，再联合咱们罕用的删除形式，进行思考，到底哪些步骤会出问题，咱们通常会抉择变量列表，如果匹配，则删除。咱们遍历的形式有以下几种：

  • foreach()：次要呈现 ConcurrentModificationException 异样
  • for(int i;**;i++)：次要呈现雷同数据跳过，可参考：https://blog.csdn.net/sun_flo…
  • Iterator 遍历：次要呈现 ConcurrentModificationException 可参考：https://www.cnblogs.com/dolph…

防止 ConcurrentModificationException 的无效方法是应用 Concurrent 包上面的 CopyOnWriteArrayList，后续会进行详细分析

1.5、toArray（）

ArrayList 提供了 2 个 toArray()函数：

  • Object[] toArray()
  • <T> T[] toArray(T[] contents)

调用 toArray() 函数会抛出“java.lang.ClassCastException”异样，然而调用 toArray(T[] contents) 能失常返回 T[]。

toArray() 会抛出异样是因为 toArray() 返回的是 Object[] 数组，将 Object[] 转换为其它类型 (如如，将 Object[] 转换为的 Integer[])则会抛出“java.lang.ClassCastException”异样，因为 Java 不反对向下转型。

toArray（）源码：

    public Object[] toArray() {return Arrays.copyOf(elementData, size);
    }

1.6、subList（）

如果咱们在开发过程中有须要获取汇合中的某一部分的数据进行操作，咱们能够通过应用 SubList（）办法来进行获取，这里会创立 ArrayList 的一个外部类 SubList（）。

SubList 继承了 AbstractList，并且实现了大部分的 AbstractList 动作。

须要留神的是，SubList 返回的汇合中的某一部分数据，是会与原汇合相关联。即当咱们对 Sublist 进行操作的时候，其实还是会影响到原始汇合。
咱们来看一下 Sublist 中的 add 办法：

      public void add(int index, E e) {rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

能够看到，Sublist 中的 加操作，其实还是调用了 parent（也就是原汇合）中的加操作。所以在应用 subList 办法时，肯定要想分明，是否须要对子集合进行批改元素而不影响原有的 list 汇合。

总结

ArrayList 总体来说比较简单，不过 ArrayList 还有以下一些特点：

  • ArrayList 本人实现了序列化和反序列化的办法，因为它本人实现了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 办法

    • ArrayList 基于数组形式实现，无容量的限度（会扩容）
    • 增加元素时可能要扩容（所以最好预判一下），删除元素时不会缩小容量（若心愿缩小容量，trimToSize()），删除元素时，将删除掉的地位元素置为 null，下次 gc 就会回收这些元素所占的内存空间。
    • 线程不平安
    • add(int index, E element)：增加元素到数组中指定地位的时候，须要将该地位及其后边所有的元素都整块向后复制一位
    • get(int index)：获取指定地位上的元素时，能够通过索引间接获取（O(1)）
    • remove(Object o)须要遍历数组
    • remove(int index)不须要遍历数组，只需判断 index 是否符合条件即可，效率比 remove(Object o)高
    • contains(E)须要遍历数组
    • 应用 iterator 遍历可能会引发多线程异样

拓展思考

  • 拓展思考 1、RandomAccess 接口是如何实现疾速定位资源的？
  • 拓展思考 2、EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的作用？
  • 拓展思考 3、remove 办法存在的坑？
  • 拓展思考 4:、ArrayList 为什么不是线程平安？

二、Vector

在介绍 Vector 的时候，人们常说：

底层实现与 ArrayList 相似，不过 Vector 是线程平安的，而 ArrayList 不是。

那么这句话定义的到底对不对呢？咱们接下来联合上一篇文章进行剖析：

Java 汇合系列 1、细思极恐之 ArrayList 

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector 是一个矢量队列，它的依赖关系跟 ArrayList 是统一的，因而它具备一下性能：

  • 1、Serializable：反对对象实现序列化，尽管成员变量没有应用 transient 关键字润饰，Vector 还是实现了 writeObject() 办法进行序列化。
  • 2、Cloneable：重写了 clone（）办法，通过 Arrays.copyOf（）拷贝数组。
  • 3、RandomAccess：提供了随机拜访性能，咱们能够通过元素的序号疾速获取元素对象。
  • 4、AbstractList：继承了 AbstractList，阐明它是一个列表，领有相应的增，删，查，改等性能。
  • 5、List：留一个疑难，为什么继承了 AbstractList 还须要 实现 List 接口？

* 拓展思考：为什么 Vector 的序列化，只重写了 writeObject（）办法？

仔细的敌人如果在查看 vector 的源码后，能够发现，writeObject（）的正文中有这样的说法：

This method performs synchronization to ensure the consistency
    of the serialized data.

看完正文，可能会有一种豁然开朗的感觉，Vector 的核心思想不就是 线程平安吗？那么序列化过程必定也要加锁进行操作，能力过说其是线程平安啊。因而，即便没有 elementData 没有应用 transient 进行润饰，还是须要重写 writeObject()。

* 拓展思考：与 ArrayLit，以及大部分汇合类雷同，为什么继承了 AbstractList 还须要 实现 List 接口？

有两种说法，大家能够参考一下：

1、在 StackOverFlow 中：传送门
得票最高的答案的回答者说他问了当初写这段代码的 Josh Bloch，得悉这就是一个写法谬误。

2、Class 类的 getInterfaces 能够获取到实现的接口，却不能获取到父类实现接口，然而这种操作无意义。

2、Vector 成员变量

    /**
        与 ArrayList 中统一，elementData 是用于存储数据的。*/
    protected Object[] elementData;

    /**
     * The number of valid components in this {@code Vector} object.
      与 ArrayList 中的 size 一样，保留数据的个数
     */
    protected int elementCount;

    /**
     * 设置 Vector 的增长系数，如果为空，默认每次扩容 2 倍。*
     * @serial
     */
    protected int capacityIncrement;
    
     // 数组最大值
     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

与 ArrayList 中的成员变量相比，Vector 少了两个空数组对象：
EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA

因而，Vector 与 ArrayList 中的第一个不同点就是，成员变量不统一。

2.1、Vector 构造函数

Vector 提供了四种构造函数：

  • Vector()：默认构造函数
  • Vector(int initialCapacity)：capacity 是 Vector 的默认容量大小。当因为减少数据导致容量减少时，每次容量会增加一倍。
  • Vector(int initialCapacity, int capacityIncrement)：capacity 是 Vector 的默认容量大小，capacityIncrement 是每次 Vector 容量减少时的增量值。
  • Vector(Collection<? extends E> c)：创立一个蕴含 collection 的 Vector

乍一眼看上去，Vector 中提供的构造函数，与 ArrayList 中的一样丰盛。然而在上一节内容 中剖析过 ArrayList 的构造函数后，再来看 Vector 的构造函数，会感觉有一种索然无味的感觉。

    // 默认构造函数
    public Vector() {this(10);
    }
    
    // 带初始容量构造函数
    public Vector(int initialCapacity) {this(initialCapacity, 0);
    }
    
    // 带初始容量和增长系数的构造函数
    public Vector(int initialCapacity, int capacityIncrement) {super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity:"+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

代码看上去没有太多的问题，跟咱们平时写的代码一样，只是与 ArrayList 中的构造函数相比 短少了一种韵味。有趣味的同学能够去看一下 ArrayList 中的构造函数实现。

    public Vector(Collection<? extends E> c) {elementData = c.toArray();
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
    }

JDK 1.2 之后提出了将 Collection 转换成 Vector 的构造函数，实际操作就是通过 Arrays.copyOf() 拷贝一份 Collection 数组中的内容到 Vector 对象中。这里会有可能抛出 NullPointerException。

在构造函数下面的比照：Vector 的构造函数的设计上输于 ArrayList。

2.2、增加办法（Add）

Vector 在增加元素的办法下面，比 ArrayList 中多了一个办法。Vector 反对的 add 办法有：

  • add(E)
  • addElement(E)
  • add(int i , E element)
  • addAll(Collection<? extends E> c)
  • addAll(int index, Collection<? extends E> c)

2.2.1 addElement(E)

咱们看一下这个多进去的 addElement(E) 办法 有什么非凡之处：

    /**
     * Adds the specified component to the end of this vector,
     * increasing its size by one. The capacity of this vector is
     * increased if its size becomes greater than its capacity.
     *
     * <p>This method is identical in functionality to the
     * {@link #add(Object) add(E)}
     * method (which is part of the {@link List} interface).
     *
     * @param   obj   the component to be added
     */
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

从正文下面来看，这个办法就是 跟 add（E）办法是有着一样的性能的。因而除了返回数据不同外，也没什么非凡之处了。

咱们顺着上述代码来进行剖析 Vector 中的增加办法。能够看到 Vector 对整个 add 办法都上锁了（增加了 synchronized 润饰），其实咱们能够了解，在增加元素的过程次要包含以下几个操作：

  • ensureCapacityHelper（）：确认容器大小
  • grow（）：如果有须要，进行容器扩大
  • elementData[elementCount++] = obj：设值

为了防止多线程状况下，在 ensureCapacityHelper 容量不须要拓展的状况下，其余线程刚好将数组填满了，这时候就会呈现 ArrayIndexOutOfBoundsException，因而对整个办法上锁，就能够防止这种状况呈现。

与 ArrayList 中比照，确认容器大小这一步骤中，少了 ArrayList#ensureCapacityInternal 这一步骤，次要也是源于 Vector 在结构时，以及创立好默认数组大小，不会呈现数组为空的状况。

其次 grow（）办法中：

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 区别与 ArrayList 中的位运算，这里反对自定义增长系数
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Vector 中反对自定义的增长系数，也是它在 add() 办法中为数不多的亮点了。

2.2.2 add(int index, E element)

这部分代码跟 ArrayList 中没有太多的差别，次要是抛出的异样有所不同，ArrayList 中抛出的是 IndexOutOfBoundsException。这里则是抛出 ArrayIndexOutOfBoundsException。至于为什么须要将操作抽取到 insertElementAt（）这个办法中呢？童鞋们能够进行相干思考。

    /**
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index > size()})
     * @since 1.2
     */
    public void add(int index, E element) {insertElementAt(element, index);
    }
    
    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + ">" + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }

在增加办法下面，Vector 与 ArrayList 大同小异。Vector 多了一个奇怪的 addElement(E)。

2.3、删除办法（Remove）

Vecotr 中提供了比拟多的删除办法，然而只有查看一下源码，就能够发现其实大部分都是雷同的办法。

  • remove(int location)
  • remove(Object object)
  • removeAll(Collection<?> collection)
  • removeAllElements()
  • removeElement(Object object)
  • removeElementAt(int location)
  • removeRange(int fromIndex, int toIndex)
  • clear()

2.3.1、remove(int location) & removeElementAt(int location)

比照一下 remove(int location) 和 removeElementAt(int location)

public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + ">=" +
                                                     elementCount);
        }
        else if (index < 0) {throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }


public synchronized E remove(int index) {
        modCount++;
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        E oldValue = elementData(index);

        int numMoved = elementCount - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--elementCount] = null; // Let gc do its work

        return oldValue;
    }

除了返回的数据类型不同，其余外部操作其实是统一的。remove 是重写了父类的操作，而 removeElement 则是 Vector 中自定义的办法。ArrayList 中提供了 fastRemove（）办法，与其有着同样的成果，不过 removeElement 作用范畴为 public。

2.3.2、remove(Object object) & removeElement(Object object)

    public boolean remove(Object o) {return removeElement(o);
    }
    
    public synchronized boolean removeElement(Object obj) {
        modCount++;
        int i = indexOf(obj);
        if (i >= 0) {removeElementAt(i);
            return true;
        }
        return false;
    }

remove(Object object) 理论外部调用的就是 removeElement(Object object)。删除操作首先找到 对象的索引（与 ArrayList 中的 remmove（E）一样），而后调用 removeElementAt（i）（ArrayList 中调用 fastRemove（）办法）进行删除。

其余删除操作与 ArrayList 相似，这里不做具体解析。总体来说，在删除办法这一块的话，Vector 与 ArrayList 也是大同小异。

2.4、线程平安 Vector？

拓展思考，咱们常说 Vector 是线程平安的数组列表，那么它到底是不是无时无刻都是线程平安的呢？在 StackOverFlow 中有这样一个问题：

StackOverFlow 传送门

Is there any danger, if im using one Vector(java.util.Vector) on my server program when im accessing it from multiple threads only for reading? (myvector .size() .get() …) For writing im using synchronized methods. Thank you.

其中有一个答案解析的比拟具体的：

Vector 中的每一个独立办法都是线程平安的，因为它有着 synchronized 进行润饰。然而如果遇到一些比较复杂的操作，并且多个线程须要依附 vector 进行相干的判断，那么这种时候就不是线程平安的了。

if (vector.size() > 0) {System.out.println(vector.get(0));
}

如上述代码所示，Vector 判断完 size（）>0 之后，另一线程如果同时清空 vector 对象，那么这时候就会出现异常。因而，在复合操作的状况下，Vector 并不是线程平安的。

总结

本篇文章题目是：百密一疏之 Vector，起因在于，如果咱们没有具体去理解过 Vector，或者在面试中，经常会认为 Vector 是线程平安的。然而实际上 Vector 只是在每一个繁多办法操作上是线程平安的。

总结一下与 ArrayList 之间的差别：

  • 1、构造函数，ArrayList 比 Vector 稍有深度，Vector 默认数组长度为 10，创立是设置。
  • 2、扩容办法 grow（），ArrayList 通过位运算进行扩容，而 Vector 则通过增长系数（创立是设置，如果过为空，则增长一倍）
  • 3、Vector 办法调用是线程平安的。
  • 4、成员变量有所不同

三、LinkedList

咱们在后面的文章中曾经介绍过 List 大家族中的 ArrayList 和 Vector 这两位犹如孪生兄弟个别，从底层实现，性能都有着相似之处，除了一些个人行为不同（成员变量，构造函数和办法线程平安）。接下来，咱们将会认识一下他们的另一位功能强大的兄弟：LinkedList

LinkedList 的依赖关系：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
  • 1、继承于 AbstractSequentialList，实质下面与继承 AbstractList 没有什么区别，AbstractSequentialList 欠缺了 AbstractList 中没有实现的办法。
  • 2、Serializable：成员变量 Node 应用 transient 润饰，通过重写 read/writeObject 办法实现序列化。
  • 3、Cloneable：重写 clone（）办法，通过创立新的 LinkedList 对象，遍历拷贝数据进行对象拷贝。
  • 4、Deque：实现了 Collection 小家庭中的队列接口，阐明他领有作为双端队列的性能。

eng～从上述实现接口来看，LinkedList 与 ArrayList 之间在整体下面的区别在于，LinkedList 实现了 Collection 小家庭中的 Queue（Deque）接口，领有作为双端队列的性能。（就好比一个小孩子，他不仅仅有父母的个性，他们有些人还会有舅舅的一些个性，好比 外甥长得像舅舅个别）。

3.1、LinkedList 成员变量

    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient 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;
        }
    }

LinkedList 的成员变量次要由 size（数据量大小），first(头节点)和 last（尾节点）。联合数据结构中双端链表的思维，每个节点须要领有，保留数据（E item），指向下一节点（Node next）和指向上一节点（Node prev）。

LinkedList 与 ArrayLit、Vector 的成员变量比照中，显著没有提供 MAX_ARRAY_SIZE 这一个最大值的限定，这是因为链表没有长度限度的起因，他的内存地址不须要调配固定长度进行存储，只须要记录下一个节点的存储地址即可实现整个链表的间断。

拓展思考：LinkedList 中 JDK 1.8 与 JDK 1.6 有哪些不同？

次要不同为，LinkedList 在 1.6 版本以及之前，只通过一个 header 头指针保留队列头和尾。这种操作能够说很有深度，然而从代码浏览性来说，却加深了浏览代码的难度。因而在后续的 JDK 更新中，将头节点和尾节点 辨别开了。节点类也更名为 Node。

3.2、LinkedList 构造函数

LinkedList 只提供了两个构造函数：

  • LinkedList()
  • LinkedList(Collection<? extends E> c)

在 JDK1.8 中，LinkedList 的构造函数 LinkedList（）是一个空办法，并没有提供什么非凡操作。区别于 JDK1.6 中，会初始化 header 为一个空的指针对象。

3.2.1 LinkedList()

JDK 1.6

private transient Entry<E> header = new Entry<E>(null, null, null);
    public LinkedList() {header.next = header.previous = header;}

JDK 1.8
在应用的时候，才会创立第一个节点。

    public LinkedList() {}

3.2.2 LinkedList(Collection<? extends E> c)

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

这一构造方法次要通过 调用 addAll 进行创建对象，在介绍 LinkedList 增加办法的时候再进行细述。

3.2.3 小结

LinkedList 在新版本的实现中，除了辨别了头节点和尾节点外，更加重视在应用时进行内存调配，这里跟 ArrayList 相似（ArrayList 默认结构器是创立一个空的数组对象）。

4、增加办法（Add）

LinkedList 继承了 AbstractSequentialList（AbstractList），同时实现了 Deque 接口，因而，他在增加办法 这一块，蕴含了两者的操作：

AbstractSequentialList:

  • add(E e)
  • add(int index，E e)
  • addAll(Collection<? extends E> c)
  • addAll(int index, Collection<? extends E> c)

Deque

  • addFirst(E e)
  • addLast(E e)
  • offer(E e)
  • offerFirst(E e)
  • offerLast(E e)

4.1 add(E e) & addLast(E e) & offer(E e) & offerLast(E e)

尽管 LinkedList 别离实现了 List 和 Deque 的增加办法，然而在某种意义上，这些办法其实都是有共性的。例如，咱们调用 add（E e）办法，不论是 ArrayList 或 Vector 等列表，都是默认在数组开端进行增加，因而与 队列中在开端增加节点 addLast（E e）是有着一样的韵味的。所以，从 LinkedList 的源码中，这几个办法，底层操作其实是统一的。

    public boolean add(E e) {linkLast(e);
        return true;
    }
    
    public void addLast(E e) {linkLast(e);
    }
    
     public boolean offer(E e) {return add(e);
    }
    
    public boolean offerLast(E e) {addLast(e);
        return true;
    }
    
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

咱们次要剖析一下 linkLast 这个办法：

  • 获取尾节点（last）
  • 创立插入节点，并且设置上一节点为 last，下一节点为 null。
  • 设置新节点为开端节点（last）
  • 如果 l（初始开端节点）==null，阐明这是第一次操作，新退出的为头节点
  • 否则，设置 l（初始开端节点）的下一节点为新退出的节点
  • size + 1，操作计数 + 1

拓展思考：为什么外部变量 Node l 须要应用 final 进行润饰？

4.2 addFirst(E e) & offerFirst（E e）

    public boolean offerFirst(E e) {addFirst(e);
        return true;
    }
    
    public void addFirst(E e) {linkFirst(e);
    }

    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

从上述代码能够看出，offerFirst 和 addFirst 其实都是一样的操作，只是返回的数据类型不同。而 linkFirst 办法，则与 linkLast 其实是一样的思维，这里也不做细述。

4.3 add(int index，E e)

这里咱们次要讲一下，为什么 LinkedList 在增加、删除元素这一方面优于 ArrayList。

    public void add(int index, E element) {checkPositionIndex(index);
        // 如果插入节点为开端，直接插入
        if (index == size)
            linkLast(element);
        // 否则，找到该节点，进行插入
        else
            linkBefore(element, node(index));
    }
    
    Node<E> node(int index) {
        // 这里程序查找元素，通过二分查找的形式，决定从头或尾节点开始进行查找，工夫复杂度为 n/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;
        }
    }
    
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        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++;
    }

LinkedList 在 add（int index，Element e）办法的流程

  • 判断下标有效性
  • 如果插入地位为开端，直接插入
  • 否则，遍历 1 / 2 的链表找到 index 下标的节点
  • 通过 succ 设置新节点的前，后节点

LinkedList 在插入数据之所以会优于 ArrayList，次要是因为在插入数据这一环节（linkBefore），插入计算只须要设置节点的前，后节点即可，而 ArrayList 则须要将整个数组的数据进行后移（

System.arraycopy(elementData, index, elementData, index + 1,size - index);

）

4.4 addAll(Collection<? extends E> c)

LinkedList 中提供的两个 addAll 办法中，其实外部实现也是一样的，次要通过：
addAll(int index, Collection<? extends E> c)进行实现：

    public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
    }
    
      public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index);
        // 将汇合转化为数组
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        // 获取插入节点的前节点（prev）和尾节点（next）if (index == size) {
            succ = null;
            pred = last;
        } else {succ = node(index);
            pred = succ.prev;
        }
        // 将汇合中的数据编织成链表
        for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        // 将 Collection 的链表插入 LinkedList 中。if (succ == null) {last = pred;} else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

4.5 小结

LinkedList 在插入数据优于 ArrayList，次要是因为他只须要批改指针的指向即可，而不须要将整个数组的数据进行转移。而 LinkedList 优于没有实现 RandomAccess，或者说 不反对索引搜寻的起因，他在查找元素这一操作，须要耗费比拟多的工夫进行操作（n/2）。

5、删除办法（Remove）

AbstractSequentialList：

  • remove（int index）
  • remove（Object o）

Deque

  • remove()
  • removeFirst()
  • removeLast()
  • removeFirstOccurrence(Object o)
  • removeLastOccurrence(Object o)

5.1 remove（int index)&remove（Object o）

在 ArrayList 中，remove（Object o）办法，是通过遍历数组，找到下标后，通过 fastRemove（与 remove（int i）相似的操作）进行删除。而 LinkedList，则是遍历链表，找到指标节点（node），通过 unlink 进行删除：
咱们这里次要来看看 unlink 办法：

    E unlink(Node<E> 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 {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {last = prev;} else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

整个过程为：

  • 获取指标节点的 next、prev
  • 如果 prev 为空，阐明指标节点为头节点
  • 设置 first 为指标节点的下一节点（next）
  • 否则设置 prev 节点的下一节点为 next（行将本人重链表中剔除）
  • 如果 next 为空，阐明指标节点为尾节点
  • 设置 last 为指标节点的上一节点
  • 否则，设置 next 节点的上一节点为 prev
  • 将指标节点设置为 null

能够看到，删除办法与增加办法相似，只须要批改节点关系即可，防止了相似于 ArrayList 的数组平移状况，大大减少了工夫损耗。

5.2 Deque 中的 Remove

Deque 中的 removeFirstOccurrence 和 removeLastOccurrence 次要过程为，首先从 first/last 节点开始遍历，当发现第一个指标对象，则低哦啊用 remove（Object o）进行删除对象。总体上没有什么特别之处。

稍有不同的是 Deque 中的 removeFirst（）和 removeLast（）办法，在底层实现下面，因为明确晓得删除的对象为 first/last 对象，因而在删除操作下面 会更加简略：

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

整体操作为，将 first 节点的 next 设置为新的头节点，而后将 f 清空。removeLast 操作也相似。

联合队列的思维，removeFirst 和 removeLast 都会返回 数据 E，相当于咱们的入列操作（pollFirst/pollLast）

6 LinkedList 双端链表

咱们之所以说 LinkedList 为双端链表，是因为他实现了 Deque 接口，反对队列的一些操作，咱们来看一下有哪些办法实现：

  • pop（）
  • poll（）
  • push（）
  • peek（）
  • offer（）

能够看到 Deque 中提供的办法次要有上述的几个办法，接下来咱们来看看在 LinkedList 中是如何实现这些办法的。

6.1 pop（）& poll（）

LinkedList#pop 的源码：

    public E pop() {return removeFirst();
   }
       public E removeFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return unlinkFirst(f);
   }

从上述代码能够看出，Pop（）的操作为，队列头部元素出队列，如果过 first 为空 会抛出异样。

LinkedList#poll 的源码：

    public E poll() {
       final Node<E> f = first;
       return (f == null) ? null : unlinkFirst(f);
   }

比照 pop 和 poll 的源码能够看到，尽管同样是 first 出列，不同的是，如果 first 为 null，pop（）办法会抛出异样。

6.2 push（）

push（）办法的底层实现，其实就是调用了 addFirst（Object o）：

    public void push(E e) {addFirst(e);
   }

push()办法的操作，次要跟 栈（Stack）中的入栈操作相似。

6.3 peek（）

LinkedList#peek 操作次要为，将取队列头部元素的值（依据队列的 FIFO，peek 为取头部数据）

    public E peek() {
       final Node<E> f = first;
       return (f == null) ? null : f.item;
   }

6.4 offer（）

offer()办法为间接调用增加办法。

    public boolean offer(E e) {return add(e);
   }

7 LinkedList 遍历

LinkedList 因为没有实现 RandomAccess，因而，在以随机拜访的模式进行遍历时成果会十分低下。除此之外，LinkedList 提供了相似于通过 Iterator 进行遍历，节点的 prev 或 next 进行遍历，还有 for 循环遍历，都有不错的成果。

四、HashMap

在接下来次要为大家介绍一下Java 汇合家庭中另一小分队 Map，咱们先来看看 Map 家庭的整体架构：

咱们次要介绍一下 HashMap：

HashMap 的依赖关系：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
  • 1、AbstractMap：表明它是一个散列表，基于 Key-Value 的存储形式
  • 2、Cloneable：反对拷贝性能
  • 3、Seriablizable：重写了 write/readObject，反对序列化

从依赖关系下面来看，HashMap 并没有 List 汇合 那么的简单，次要是因为在迭代下面，HashMap 区别 key-value 进行迭代，而他们的迭代又依赖与 keySet-valueSet 进行，因而，尽管依赖关系下面 HashMap 看似简略，然而外部的依赖关系更为简单。

4.1、HashMap 成员变量

默认 桶（数组）容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表转树 大小
static final int TREEIFY_THRESHOLD = 8;

树转链表 大小
static final int UNTREEIFY_THRESHOLD = 6;

最小转红黑树容量
static final int MIN_TREEIFY_CAPACITY = 64;

存储数据节点
static class Node<K,V> implements Map.Entry<K,V> 

节点数组
transient Node<K,V>[] table;

数据容量
transient int size;

操作次数
transient int modCount;

扩容大小
int threshold;

比照于 JDK8 之前的 HashMap，成员变量次要的区别在于多了红黑树的相干变量，用于标示咱们在什么时候进行 list -> Tree 的转换。

附上 Jdk8 中 HashMap 的数据结构展现图：

4.2、HashMap 构造函数

HashMap 提供了四种构造函数：

  • HashMap（）：默认构造函数，参数均应用默认大小
  • HashMap（int initialCapacity）：指定初始数组大小
  • HashMap（int initialCapacity, float loadFactor）：指定初始数组大小，加载因子
  • HashMap（Map<? extends K, ? extends V> m）：创立新的 HashMap，并将 m 中内容存入 HashMap 中

4.3、HashMap Put 过程

接下来咱们次要解说一下，HashMap 在 JDK8 中的增加数据过程（援用）：

4.3.1、put(K key, V value)

    public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
    }

上述办法是咱们在开发过程中最常应用到的办法，然而却很少人晓得，其实外部真正调用的办法是这个putVal(hash(key), key, value, false, true) 办法。这里略微介绍一下这几个参数：

  • hash 值，用于确定存储地位
  • key：存入键值
  • value：存入数据
  • onlyIfAbsent：是否笼罩本来数据，如果为 true 则不笼罩
  • onlyIfAbsent：table 是否处于创立模式
4.3.1.1 hash(Object key)
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这里的 Hash 算法实质上就是三步：取 key 的 hashCode 值、高位运算、取模运算。
这里援用一张图，易于大家理解相干机制


这里可能会比拟纳闷，为什么须要对本身的 hashCode 进行运算，这么做能够在数组 table 比拟小的时候，让高位 bit 也能参加到 hash 运算中，同时不会又太大的开销。

4.3.2、putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

因为源码篇幅过长，这里我进行离开解说，同学们能够对照源码进行浏览

4.3.2.1 申明成员变量（第一步）
Node<K,V>[] tab; Node<K,V> p; int n, i;

第一局部次要县申明几个须要应用到的成员变量：

  • tab：对应 table 用于存储数据
  • p：咱们须要存储的数据，将转化为该对象
  • n：数组（table）长度
  • i：数组下标
4.3.2.2 Table 为 null，初始化 Table（第二步）

table 为空阐明以后操作为第一次操作，通过下面构造函数的浏览，咱们能够理解到，咱们并没有对 table 进行初始化，因而在第一次 put 操作的时候，咱们须要先将 table 进行初始化。

        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

从上述代码能够看到，table 的初始化和扩容，都依赖于 resize（） 办法，在前面咱们会对该办法进行详细分析。

4.3.2.3 Hash 碰撞确认下标（True）
 if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

在上一步咱们以及确认以后 table 不为空，而后咱们须要计算咱们对象须要存储的下标了。

如果该下标中并没有数据，咱们只需创立一个新的节点，而后将其存入 tab[] 即可。

4.3.2.4 Hash 碰撞确认下标（False）

与上述过程相同，Hash 碰撞后果后，发现该下标有保留元素，将其保留到变量 p = tab[i = (n - 1) & hash]，当初 p 保留的是指标数组下标中的元素。如上图所示(援用)：

4.3.2.4.1 key 值雷同笼罩

在获取到 p 后，咱们首先判断它的 key 是否与咱们这次插入的 key 雷同，如果雷同，咱们将其援用传递给 e

if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
4.3.2.4.2 红黑树节点解决
else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

因为在 JDK 8 后，会对过长的链表进行解决，即 链表 -> 红黑树，因而对应的节点也会进行相干的解决。红黑树的节点则为 TreeNode，因而在获取到 p 后，如果他跟首位元素不匹配，那么他就有可能为红黑树的内容。所以进行putTreeVal(this, tab, hash, key, value) 操作。该操作的源码，将会在后续进行细述。

4.3.2.4.3 链表节点解决
        else {
            //for 循环遍历链表，binCount 用于记录长度，如果过长则进行树的转化
                for (int binCount = 0; ; ++binCount) {
                // 如果发现 p.next 为空，阐明下一个节点为插入节点
                    if ((e = p.next) == null) {
                        // 创立一个新的节点
                        p.next = newNode(hash, key, value, null);
                        // 判断是否须要转树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        // 完结遍历
                        break;
                    }
                    // 如果插入的 key 雷同，退出遍历
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 替换 p
                    p = e;
                }
            }

链表遍历解决，整个过程就是，遍历所有节点，当发现如果存在 key 与插入的 key 雷同，那么退出遍历，否则在最初插入新的节点。判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 曾经存在间接笼罩 value 即可；

4.3.2.4.3 判断是否笼罩
        if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

如果 e 不为空，阐明在校验 key 的 hash 值，发现存在雷同的 key，那么将会在这里进行判断是否对其进行笼罩。

4.3.2.5 容量判断
        if (++size > threshold)
            resize();

如果 size 大于 threshold 则进行扩容解决。

4.4、Resize（）扩容

在下面的构造函数，和 put 过程都有调用过 resize（） 办法，那么，咱们接下来将会剖析一下 resize（） 过程。因为 JDK 8 引入了红黑树，咱们先从 JDK 7 开始浏览 resize（） 过程。上面局部内容参考：传送门

4.4.1 JDK 7 resize()

在 JDK 7 中，扩容次要分为了两个步骤：

  • 容器扩大
  • 内容拷贝
4.4.1.1 容器扩大
 1 void resize(int newCapacity) {   // 传入新的容量
 2     Entry[] oldTable = table;    // 援用扩容前的 Entry 数组
 3     int oldCapacity = oldTable.length;         
 4     if (oldCapacity == MAXIMUM_CAPACITY) {// 扩容前的数组大小如果曾经达到最大 (2^30) 了
 5         threshold = Integer.MAX_VALUE; // 批改阈值为 int 的最大值(2^31-1)，这样当前就不会扩容了
 6         return;
 7     }
 8  
 9     Entry[] newTable = new Entry[newCapacity];  // 初始化一个新的 Entry 数组
10     transfer(newTable);                         //！！将数据转移到新的 Entry 数组里
11     table = newTable;                           //HashMap 的 table 属性援用新的 Entry 数组
12     threshold = (int)(newCapacity * loadFactor);// 批改阈值
13 }
4.4.1.2 内容拷贝
 1 void transfer(Entry[] newTable) {2     Entry[] src = table;                   //src 援用了旧的 Entry 数组
 3     int newCapacity = newTable.length;
 4     for (int j = 0; j < src.length; j++) { // 遍历旧的 Entry 数组
 5         Entry<K,V> e = src[j];             // 获得旧 Entry 数组的每个元素
 6         if (e != null) {7             src[j] = null;// 开释旧 Entry 数组的对象援用（for 循环后，旧的 Entry 数组不再援用任何对象）8             do {
 9                 Entry<K,V> next = e.next;
10                 int i = indexFor(e.hash, newCapacity); //！！从新计算每个元素在数组中的地位
11                 e.next = newTable[i]; // 标记[1]
12                 newTable[i] = e;      // 将元素放在数组上
13                 e = next;             // 拜访下一个 Entry 链上的元素
14             } while (e != null);
15         }
16     }
17 }
4.4.1.3 扩容过程展现（援用）

上面举个例子阐明下扩容过程。假如了咱们的 hash 算法就是简略的用 key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组 table 的 size=2，所以 key = 3、7、5，put 程序顺次为 5、7、3。在 mod 2 当前都抵触在 table[1]这里了。这里假如负载因子 loadFactor=1，即当键值对的理论大小 size 大于 table 的理论大小时进行扩容。接下来的三个步骤是哈希桶数组 resize 成 4，而后所有的 Node 从新 rehash 的过程。

4.4.2 JDK 8 resize()

因为扩容局部代码篇幅比拟长，童鞋们能够比照着博客与源码进行浏览。
与上述流程类似，JDK 8 中扩容过程次要分成两个局部：

  • 容器扩大
  • 内容拷贝
4.4.2.1 容器扩大
        Node<K,V>[] oldTab = table;         // 创立一个对象指向以后数组
        int oldCap = (oldTab == null) ? 0 : oldTab.length;      // 获取旧数组的长度
        int oldThr = threshold;                             // 获取旧的阀值
        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)
                // 容器扩容一倍，并且将阀值设置为原来的一倍
                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;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        
        // 第二步，创立新数组
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;

从下面的流程剖析，咱们能够看到在 JDK 8 HashMap 中，开始应用位运算进行扩容计算，次要长处将会在后续数据拷贝中具体表现。

4.4.2.2 内容拷贝

在上述容器扩容完结后，如果发现 oldTab 不为空，那么接下来将会进行内容拷贝：

    if (oldTab != null) {
            // 对旧数组进行遍历
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //
                if ((e = oldTab[j]) != null) {
                    // 将旧数组中的内容清空
                    oldTab[j] = null;
                    // 如果 e 没有后续内容，只解决以后值即可
                    if (e.next == null)
                        通过位运算确定下标
                        newTab[e.hash & (newCap - 1)] = e;
                    // 如果 以后节点为红黑树节点，进行红黑树相干解决    
                    else if (e instanceof TreeNode)
                        ((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;
                        do {
                            next = e.next;
                            // 高位 与运算，确定索引为原索引
                            if ((e.hash & oldCap) == 0) {if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 高位与运算，确认索引为 愿索引 + oldCap
                            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;
                        }
                    }
                }
            }
        }

内容拷贝，在JDK 8 中优化，次要是：

  • 通过高位与运算确认存储地址
  • 链表不会呈现导致，JDK 8 通过创立新链表形式进行转移

咱们来看一下 JDK 8 是如何通过高位与运算确认存储地位的：

4.5、小结

HashMap 中，如果 key 通过 hash 算法得出的数组索引地位全副不雷同，即 Hash 算法十分好，那样的话，getKey 办法的工夫复杂度就是 O(1)，如果 Hash 算法技术的后果碰撞十分多，如果 Hash 算极其差，所有的 Hash 算法后果得出的索引地位一样，那样所有的键值对都集中到一个桶中，或者在一个链表中，或者在一个红黑树中，工夫复杂度别离为 O(n)和 O(lgn)。

(1) 扩容是一个特地耗性能的操作，所以当程序员在应用 HashMap 的时候，估算 map 的大小，初始化的时候给一个大抵的数值，防止 map 进行频繁的扩容。

(2) 负载因子是能够批改的，也能够大于 1，然而倡议不要轻易批改，除非状况十分非凡。

(3) HashMap 是线程不平安的，不要在并发的环境中同时操作 HashMap，倡议应用 ConcurrentHashMap。

(4) JDK1.8 引入红黑树大程度优化了 HashMap 的性能。

(5) 还没降级 JDK1.8 的，当初开始降级吧。HashMap 的性能晋升仅仅是 JDK1.8 的冰山一角。

参考

  • https://tech.meituan.com/java…
  • https://www.2cto.com/kf/20150…

五、总结

没有太多的拓展思考，脑子不够清晰，总体来说，List 接口上面的大家庭的源码以及剖析完了。对每一个成员都有了进一步的理解，面试的时候，也不会再简略的答复，linkedList 插入删除性能比拟好，ArrayList 能过疾速定位元素，Vector 是线程平安。只有在充沛理解其实现，你才会发现，你答复的尽管没错，然而也就 60 分而已，如果你想要将每一个问题答复的完满，那么请认真思考，认真去理解它。

最初贴一个新生的公众号（Java 补习课 ），欢送各位关注，次要会分享一下面试的内容（参考之前博主的文章），阿里的开源技术之类和阿里生存相干。最近在组建一个 阿里内推 & 技术交换群，感兴趣的童鞋，能够扫描二维码增加我的微信！

正文完
java
发表至： java
2021-06-30
 0
Windows-xp修改IP地址
关于java:实现内网穿透一
探索Java日志的奥秘：底层日志系统-log4j2
吃透动态代理，解密spring AOP源码（三）