第三章、Java 的集合

1、HashMap 排序题

已知一个 HashMap<Integer， User>集合， User 有 name（String）和 age（int）属性。请写一个方法实现对 HashMap 的排序功能，该方法接收 HashMap<Integer， User>为形参，返回类型为 HashMap<Integer，User>，要求对 HashMap 中的 User 的 age 倒序进行排序。排序时 key=value 键值对不得拆散。public class HashMapTest {    public static void main(String[] args) {        HashMap<Integer, User> users = new HashMap<>();        users.put(1, new User("张三", 25));        users.put(3, new User("李四", 22));        users.put(2, new User("王五", 28));        System.out.println(users);        HashMap<Integer, User> sortHashMap = sortHashMap(users);        System.out.println(sortHashMap);        /**         * 控制台输出内容         * {1=User [name=张三, age=25], 2=User [name=王五, age=28], 3=User [name=李四, age=22]}         {2=User [name=王五, age=28], 1=User [name=张三, age=25], 3=User [name=李四, age=22]}         */    }    public static HashMap<Integer, User> sortHashMap(HashMap<Integer, User> map) {        // 首先拿到 map 的键值对集合        Set<Entry<Integer, User>> entrySet = map.entrySet();        // 将 set 集合转为 List 集合，为什么，为了使用工具类的排序方法        List<Entry<Integer, User>> list = new ArrayList<Entry<Integer, User>>(entrySet);        // 使用 Collections 集合工具类对 list 进行排序，排序规则使用匿名内部类来实现        Collections.sort(list, new Comparator<Entry<Integer, User>>() {            @Override            public int compare(Entry<Integer, User> o1, Entry<Integer, User> o2) {                //按照要求根据 User 的 age 的倒序进行排                return o2.getValue().getAge() - o1.getValue().getAge();            }        });        //创建一个新的有序的 HashMap 子类的集合        LinkedHashMap<Integer, User> linkedHashMap = new LinkedHashMap<Integer, User>();        //将 List 中的数据存储在 LinkedHashMap 中        for (Entry<Integer, User> entry : list) {            linkedHashMap.put(entry.getKey(), entry.getValue());        }        //返回结果        return linkedHashMap;    }}

2、请问 ArrayList、 HashSet、 HashMap 是线程安全的吗？如果想要线程安全的集合怎么办？

都是线程不安全的。在集合中 Vector 和 HashTable 是线程安全的。其实就是把各自核心方法添加上了 synchronized 关键字。Collections 工具类提供了相关的 API，可以让上面那 3 个不安全的集合变为安全的。 Collections.synchronizedCollection(c);Collections.synchronizedList(list);Collections.synchronizedMap(m);Collections.synchronizedSet(s);上面几个函数都有对应的返回值类型，传入什么类型返回什么类型。打开源码其实实现原理非常简单，就是将集合的核心方法添加上了 synchronized 关键字。

3、ArrayList 内部用什么实现的？

ArrayList 内部是用 Object[] 实现的。它内部主要有两个成员变量，elementData 用于存储数据，size 用于标记存储了多少个元素，size 总是按最大值显示的（考虑多线程环境，添加元素先增加size）。

一、构造函数

1）空参构造

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData;public ArrayList() {  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}当我们 new 一个空参 ArrayList 的时候，系统内部使用了一个 new Object[0] 数组

2） 带参构造 1

private static final Object[] EMPTY_ELEMENTDATA = {};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);   }}

3）带参构造 2

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;    }}

二、add 方法

add(E e) 末尾插入新元素

public boolean add(E e) {    ensureCapacityInternal(size + 1);  //判断是否需要扩容    elementData[size++] = e;    return true;}1、首先进行了扩容，最终调用的是 grow 方法：从这里我们知道每次扩容后的大小为原来的容量 n + n/2，例如原来的容量是 10，扩容后的容量则成了 15.2、将新元素放到了原来的元素的后面，因为不用移动原来的元素，所以比较快。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);}

add(int index, E e) 指定位置插入新元素

public void add(int index, E element) {    rangeCheckForAdd(index);    ensureCapacityInternal(size + 1);  // Increments modCount!!    System.arraycopy(elementData, index, elementData, index + 1,size - index);    elementData[index] = element;    size++;}1. 检查index位置是否合理（太小，太大）。2. 同上，检查是否需要扩大数组容量。3. 将原来index后面的所有元素往后面移动一个位置，这样index位置就空出来了。4. 将新元素放到index位置，接着size加1。从这里我们知道，因为每次插入都需要移动index后面的元素，所以效率很低，尽量避免使用该方法。

三、get 方法

get(int index)

public E get(int index) {    rangeCheck(index);    return elementData(index);}获取指定位置元素，直接返回数组对应的位置，不需要额外操作，很快！（这也是为什么它能够实现了AccessRandom）

四、remove 方法

remove(int index)

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; // clear to let GC do its work    return oldValue;}直接移动 index 后面的所有元素向前移动，覆盖 index 位置，简单粗暴。 从这里我们知道需要移动数组，效率并不高。

五、index 方法

index(E e) 查询元素位置

public int indexOf(Object 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;}遍历查找第一个 equals 要找的的元素的位置，返回，简单粗暴。

六、trimToSize 方法

trimToSize()

public void trimToSize() {    modCount++;    if (size < elementData.length) {        elementData = (size == 0)          ? EMPTY_ELEMENTDATA          : Arrays.copyOf(elementData, size);    }}这个方法是用来缩减空间的，当你的 ArrayList 装的东西已经确定以后（以后不会再删除，添加），可以调用这个方法节省内存空间。 它会把数组的长度缩减得和size一样。

七、总结

1. ArrayList 内部使用一个数组存储数据，使用一个 size 变量标记储存了多少个元素。2. 它可以存储任一对象，包括 null，当向其中添加元素时，会进行扩容操作，每次扩容增加的大小为原来数组长度的一半。所以最好使用之前能够估计好元素的数量。3. 查找元素，末尾插入元素很快，指定位置插入元素，移除元素效率很低，因为需要移动数组。 所以查找操作多推荐使用ArrayList，删除操作多时推荐使用 LinkedList。4. 可以调用 trimToSize”瘦身“。5.继承了一个 AccessRandom 标记接口，继承者在算法实现上应该考虑 for 循环遍历元素要快于 iterator 遍历。

4、并发集合和普通集合如何区别？

并发集合常见的有 ConcurrentHashMap、 ConcurrentLinkedQueue、 ConcurrentLinkedDeque 等。并发集合位于 java.util.concurrent 包下。在 java 中有普通集合、同步（线程安全）的集合、并发集合。普通集合通常性能最高，但是不保证多线程的安全性和并发的可靠性。线程安全集合仅仅是给集合添加了 synchronized 同步锁，严重牺牲了性能，而且对并发的效率就更低了，并发集合则通过复杂的策略不仅保证了多线程的安全又提高的并发时的效率。

5、List 的三个子类的特点

ArrayList：底层结构是数组,底层查询快,增删慢。LinkedList：底层结构是链表型的,增删快,查询慢。Voctor：底层结构是数组 线程安全的,增删慢,查询慢。

6、List 和 Map、Set 的区别

List 和 Set 是存储单列数据的集合，Map 是存储键和值这样的双列数据的集合；List 中存储的数据是有顺序，并且允许重复；Map 中存储的数据是没有顺序的，其键是不能重复的，它的值是可以有重复的，Set 中存储的数据是无序的，且不允许有重复，但元素在集合中的位置由元素的 hashcode 决定，位置是固定的（Set 集合根据 hashcode 来进行数据的存储，所以位置是固定的，但是位置不是用户可以控制的，所以对于用户来说 set 中的元素还是无序的）；List 接口有三个实现类（LinkedList：基于链表实现，链表内存是散乱的，每一个元素存储本身内存地址的同时还存储下一个元素的地址。链表增删快，查找慢；ArrayList：基于数组实现，非线程安全的，效率高，便于索引，但不便于插入删除；Vector：基于数组实现，线程安全的，效率低）。Map 接口有三个实现类（HashMap：基于 hash 表的 Map 接口实现，非线程安全，高效，支持 null 值和 null键；HashTable：线程安全，低效，不支持 null 值和 null 键；LinkedHashMap：是 HashMap 的一个子类，保存了记录的插入顺序；SortMap 接口： TreeMap，能够把它保存的记录根据键排序，默认是键值的升序排序）。Set 接口有两个实现类（HashSet：底层是由 HashMap 实现，不允许集合中有重复的值，使用该方式时需要重写 equals()和 hashCode()方法；LinkedHashSet：继承与HashSet，同时又基于 LinkedHashMap 来进行实现，底层使用的是 LinkedHashMp）。List 集合中对象按照索引位置排序，可以有重复对象，允许按照对象在集合中的索引位置检索对象，例如通过list.get(i)方法来获取集合中的元素； Map 中的每一个元素包含一个键和一个值，成对出现，键对象不可以重复，值对象可以重复； Set 集合中的对象不按照特定的方式排序，并且没有重复对象，但它的实现类能对集合中的对象按照特定的方式排序，例如 TreeSet 类，可以按照默认顺序，也可以通过实现 Java.util.Comparator<Type>接口来自定义排序方式。

7、HashMap 和 HashTable 有什么区别?

HashMap 是线程不安全的,HashMap 是一个接口,是 Map 的一个子接口,是将键映射到值得对象,不允许键值重复,允许空键和空值;由于非线程安全,HashMap 的效率要较 HashTable 的效率高一些.HashTable 是线程安全的一个集合,不允许 null 值作为一个 key 值或者 Value 值;HashTable 是 sychronize,多个线程访问时不需要自己为它的方法实现同步,而 HashMap 在被多个线程访问的时候需要自己为它的方法实现同步;

8、数组和链表分别比较适合用于什么场景，为什么？

数组是将元素在内存中连续存储；它的优点：因为数据是连续存储的，内存地址连续，所以在查找数据的时候效率比较高；它的缺点：在存储之前，我们需要申请一块连续的内存空间，并且在编译的时候就必须确定好它的空间的大小。在运行的时候空间的大小是无法随着你的需要进行增加和减少而改变的，当数据两比较大的时候，有可能会出现越界的情况，数据比较小的时候，又有可能会浪费掉内存空间。在改变数据个数时，增加、插入、删除数据效率比较低；链表是动态申请内存空间，不需要像数组需要提前申请好内存的大小，链表只需在用的时候申请就可以，根据需要来动态申请或者删除内存空间，对于数据增加和删除以及插入比数组灵活。还有就是链表中数据在内存中可以在任意的位置，通过应用来关联数据（就是通过存在元素的指针来联系）；数组应用场景：数据比较少；经常做的运算是按序号访问数据元素；数组更容易实现，任何高级语言都支持；构建的线性表较稳定。链表应用场景：对线性表的长度或者规模难以估计；频繁做插入删除操作；构建动态性比较强的线性表。

9、Java 中 ArrayList 和 Linkedlist 区别？

1、Arraylist：底层是基于动态数组，根据下表随机访问数组元素的效率高，向数组尾部添加元素的效率高；但是，删除数组中的数据以及向数组中间添加数据效率低，因为需要移动数组。例如最坏的情况是删除第一个数组元素，则需要将第2至第n个数组元素各向前移动一位。而之所以称为动态数组，是因为Arraylist在数组元素超过其容量大，Arraylist可以进行扩容（针对JDK1.8  数组扩容后的容量是扩容前的1.5倍），Arraylist源码中最大的数组容量 Integer.MAX_VALUE-8，对于空出的8位，目前解释是 ：①存储Headerwords；②避免一些机器内存溢出，减少出错几率，所以少分配③最大还是能支持到Integer.MAX_VALUE（当Integer.MAX_VALUE-8依旧无法满足需求时）；2、Linkedlist：基于链表的动态数组，数据添加删除效率高，只需要改变指针指向即可，但是访问数据的平均效率低，需要对链表进行遍历。由于LinkedList是一个双向链表，因此不需要扩容机制，直接在前后添加元素即可；

10、List a=new ArrayList()和 ArrayList a =new ArrayList()的区别？

List list = new ArrayList(); //这句创建了一个 ArrayList 的对象后往上溯到了 List。此时它是一个 List 对象了，ArrayList 有但是 List 没有的属性和方法，它就不能再用了。而 ArrayList list = new ArrayList();创建一对象则保留了ArrayList 的所有属性。 所以需要用到 ArrayList 独有的方法的时候不能用前者。实例代码如下：List list = new ArrayList();ArrayList arrayList = new ArrayList();list.trimToSize(); //错误，没有该方法。arrayList.trimToSize(); //ArrayList 里有该方法。

11、要对集合更新操作时， ArrayList 和 LinkedList 哪个更适合？

1. ArrayList 是实现了基于动态数组的数据结构，LinkedList 基于链表的数据结构。2. 如果集合数据是对于集合随机访问 get 和 set，ArrayList 绝对优于 LinkedList，因为 LinkedList 要移动指针。3. 如果集合数据是对于集合新增和删除操作 add 和 remove， LinedList 比较占优势，因为 ArrayList 要移动数据。ArrayList 和 LinkedList 是两个集合类，用于存储一系列的对象引用(references)。例如我们可以用 ArrayList 来存储一系列的 String 或者 Integer。4. 对 ArrayList 和 LinkedList 而言，在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList 而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对 LinkedList 而言，这个开销是统一的，分配一个内部 Entry 对象。5. 在 ArrayList 的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在 LinkedList 的中间插入或删除一个元素的开销是固定的。6. LinkedList 不支持高效的随机元素访问。7. ArrayList 的空间浪费主要体现在在 list 列表的结尾预留一定的容量空间，而LinkedList 的空间花费则体现在它的每一个元素都需要消耗相当的空间。可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList 会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用 LinkedList了。

12、请用两个队列模拟堆栈结构

两个队列模拟一个堆栈，队列是先进先出，而堆栈是先进后出。模拟如下队列 a 和 b（1）入栈：a 队列为空，b 为空。例：则将” a,b,c,d,e” 需要入栈的元素先放 a 中，a 进栈为” a,b,c,d,e”（2）出栈：a 队列目前的元素为” a,b,c,d,e”。将 a 队列依次加入 Arraylist 集合a中。以倒序的方法，将 a 中的集合取出，放入 b 队列中，再将 b 队列出列。public static void main(String[] args) {    Queue<String> queue = new LinkedList<String>(); //a 队列    Queue<String> queue2 = new LinkedList<String>(); //b 队列    ArrayList<String> a = new ArrayList<String>(); //arrylist 集合是中间参数    //往 a 队列添加元素    queue.offer("a");    queue.offer("b");    queue.offer("c");    queue.offer("d");    queue.offer("e");    System.out.print("进栈： ");    //a 队列依次加入 list 集合之中    for (String q : queue) {        a.add(q);        System.out.print(q);    }    //以倒序的方法取出（a 队列依次加入 list 集合）之中的值，加入 b 对列    for (int i = a.size() - 1; i >= 0; i--) {        queue2.offer(a.get(i));    }    //打印出栈队列    System.out.println("");    System.out.print("出栈： ");    for (String q : queue2) {        System.out.print(q);    }}打印结果为（遵循栈模式先进后出）：进栈： a b c d e出栈： e d c b a

13、Map 中的 key 和 value 可以为 null 么？

HashMap 对象的 key、 value 值均可为 null。HahTable 对象的 key、 value 值均不可为 null。且两者的的 key 值均不能重复，若添加 key 相同的键值对，后面的 value 会自动覆盖前面的 value，但不会报错。

14、Hashmap如何实现key的唯一性？

1、对于 HashMap HashSet 的实现是：维护了一张 HashTable 容器中的元素全部存储在 Hashtable 中，每次添加元素都会先判断是否有重复的元素，hashcode() 方法进行比较，若一样再equals()方法比较，他们的底层数据结构如果也相同的话，JVM就认为数据已经存在了，就不会添加数据2、对于 TreeMap  TreeSet他们底层是数据结构的实现是：维护了一棵二叉树。 容器中添加元素的时候，他们有是怎么判断是否有相同元素的？我们都知道 TreeMap TreeSet  她们 都是 有序的存储数据。 为了维护 数据的唯一性。 在存入数据的时候，他们会调用元素中 实现的 Comparable 的 compareTo()  方法（代码1）。 或者 集合本身创建的时候 传入了 迭代器（代码2）.  具体的实现是：调用比较方法，返回-1  的时候，添加到左子树，返回1 的时候 添加到 右子树。返回0 有相同数据 不添加该元素！

15、HashMap的工作原理

HashMap 基于 hashing 原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时会发生什么？ 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。

16、HashMap 和HashTable的区别？

HashMap 和 HashTable 都实现了 Map 接口。主要的区别有：线程安全性，同步( synchronization )，以及速度。1、HashMap 几乎可以等价于 Hashtable，除了 HashMap 是非 synchronized 的，并可以接受 null (HashMap 可以接受为 null 的键值(key)和值(value)，而Hashtable则不行)。2、HashMap 是非 synchronized，而 Hashtable 是 synchronized，这意味着 Hashtable 是线程安全的，多个线程可以共享一个 Hashtable；而如果没有正确的同步的话，多个线程是不能共享 HashMap 的。Java 5提供了 ConcurrentHashMap，它是 HashTable 的替代，比 HashTable 的扩展性更好。3、另一个区别是 HashMap 的迭代器(Iterator)是 fail-fast 迭代器，而 Hashtable 的 enumerator 迭代器不是 fail-fast 的。所以当有其它线程改变了 HashMap 的结构（增加或者移除元素），将会抛出 ConcurrentModificationException，但迭代器本身的 remove() 方法移除元素则不会抛出 ConcurrentModificationException 异常。但这并不是一个一定发生的行为，要看 JVM。这条同样也是 Enumeration 和 Iterator 的区别。4、由于 Hashtable 是线程安全的也是 synchronized，所以在单线程环境下它比 HashMap 要慢。如果你不需要同步，只需要单一线程，那么使用 HashMap 性能要好过 Hashtable。5、HashMap 不能保证随着时间的推移Map中的元素次序是不变的；6、HashMap 和 Hashtable 的底层实现都是数组+链表结构实现；

17、LinkedHashMap的应用

LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。LinkedHashMap实现与HashMap的不同之处在于，LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序（insert-order）或者是访问顺序，其中默认的迭代访问顺序就是插入顺序，即可以按插入的顺序遍历元素，这点和HashMap有很大的不同，最近经常使用的元素就放在后面，最近最少使用的就排在了链表的前面，基于LinkedHashMap的访问顺序的特点，可构造一个LRU（Least Recently Used）最近最少使用简单缓存，ehcache的淘汰策略（LRU）就是在LinkedHashMap上扩展的。

18、为什么hashMap 的数组长度为2的n次幂

'tab[i = (n - 1) & hash]'当数组长度不为2的n次幂的时候，hashCode 值与数组长度减一做与运算的时候，会出现重复的数据，因为不为2的n次幂 的话，对应的二进制数肯定有一位为0 ,这样，不管你的hashCode 值对应的该位，是0 还是1 ,最终得到的该位上的数肯定是0 ，这带来的问题就是HashMap 上的数组元素分布不均匀，而数组上的某些位置，永远也用不到jdk 1.8 已经在链表数据超过'8'个以后转换成了红黑树的操作.

19、JDK1.8中HashMap如何应对hash冲突？

1、什么是hash冲突我们知道HashMap底层是由'数组+链表/红黑树'构成的，当我们通过 put(key, value) 向 hashmap 中添加元素时，需要通过散列函数确定元素究竟应该放置在数组中的哪个位置，当不同的元素被放置在了数据的同一个位置时，后放入的元素会以链表的形式，插在前一个元素的尾部，这个时候我们称发生了hash冲突。HashMap中调用 hashCode() 方法来计算hashCode。由于在Java中两个不同的对象可能有一样的hashCode,所以不同的键可能有一样hashCode，从而导致冲突的产生2、如何解决hash冲突采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);}static final int hash(Object key) {    int h;  	// 判断key是否为null, 如果为null,则直接返回0;  	// 如果不为null，则返回(h = key.hashCode()) ^ (h >>> 16)的执行结果    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}'(h = key.hashCode()) ^ (h >>> 16)' 执行了三步操作：第1步：h = key.hashCode()这一步会根据key值计算出一个 int 类型的h值也就是hashcode值第2步：h >>> 16将第1步计算出的h值无符号右移16位第3步：h ^ (h >>> 16)将hashcode值的高低16位进行异或操作(同0得0、同1得0、不同得1)得到hash值

20、为什么HashMap中链表长度超过8会转换成红黑树？

HashMap在jdk1.8之后引入了红黑树的概念，表示若桶中链表元素超过8时，会自动转化成红黑树；若桶中元素小于等于6时，树结构还原成链表形式。原因：红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。选择6和8的原因是：中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

21、说说HashMap的扩容过程

JDK1.7void resize(int newCapacity) {        Entry[] oldTable = table;//保存旧数组        int oldCapacity = oldTable.length;        if (oldCapacity == MAXIMUM_CAPACITY) {//判断当前数组大小是否达到最大值            threshold = Integer.MAX_VALUE;            return;        }        Entry[] newTable = new Entry[newCapacity];//创建一个新数组        boolean oldAltHashing = useAltHashing;        useAltHashing |= sun.misc.VM.isBooted() &&                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);        boolean rehash = oldAltHashing ^ useAltHashing;//是否需要重新计算hash值        transfer(newTable, rehash);//将oldTable的元素迁移到newTable        table = newTable;//将新数组重新赋值  			//重新计算阈值        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}void transfer(Entry[] newTable, boolean rehash) {        int newCapacity = newTable.length;        for (Entry<K,V> e : table) {//遍历oldTable迁移元素到newTable            while(null != e) {//①处会导致闭环，从而导致e永远不为空，然后死循环，内存直接爆了                Entry<K,V> next = e.next;                if (rehash) {//是否需要重新计算hash值                    e.hash = null == e.key ? 0 : hash(e.key);                }                int i = indexFor(e.hash, newCapacity);//！！重新计算每个元素在数组中的位置                e.next = newTable[i];//①                newTable[i] = e;//① 将元素放在数组上                e = next;//① 访问下一个Entry链上的元素            }        }}

JDK1.8final Node<K,V>[] resize() {        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; //扩容两倍的阈值        }        else if (oldThr > 0) // 初始化新的数组大小            newCap = oldThr;        else {//上面条件都不满足，则使用默认值            newCap = DEFAULT_INITIAL_CAPACITY;            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;//将新阈值赋值到当前对象        @SuppressWarnings({"rawtypes","unchecked"})  			//创建一个newCap大小的数组Node        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];        table = newTab;        if (oldTab != null) {            for (int j = 0; j < oldCap; ++j) {//遍历旧的数组                Node<K,V> e;                if ((e = oldTab[j]) != null) {                    oldTab[j] = null;//释放空间                    if (e.next == null)                      //如果旧数组中e后面没有元素，则直接计算新数组的位置存放                        newTab[e.hash & (newCap - 1)] = e;                    else if (e instanceof TreeNode)//如果是红黑树则单独处理                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                    else { //链表结构逻辑，解决hash冲突                        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;                            }                            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;                        }                        //原索引+oldCap放入数组中                        if (hiTail != null) {                            hiTail.next = null;                            newTab[j + oldCap] = hiHead;//jdk1.8优化的点                        }                    }                }            }        }        return newTab;    }

jdk1.7扩容是重新计算hash；jdk1.8是要看看原来的hash值新增的那个bit是1还是0，如果是0则索引没变，如果是1则索引变成"原索引+oldCap".这是jdk1.8的亮点，设计的确实非常的巧妙，即省去了重新计算hash值得时间，又均匀的把之前的冲突的节点分散到新的数组bucket上jdk1.7在rehash的时候，旧链表迁移到新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是jdk1.8不会倒置。

22、JDK1.8之前HashMap并发情况为什么会发生死循环

进行put操作到阈值时，进行扩容的时候会导致死循环

23、HashMap到底是插入链表头部还是尾部

在jdk1.8之前是插入头部的，在jdk1.8中是插入尾部的