Java集合
集合概述 Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。
说说 List, Set, Queue, Map 四者的区别？
List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。
Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，”x” 代表 key，”y” 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
集合框架底层数据结构总结 Collection 接口下面的集合
List
ArrayList： Object[] 数组
Vector：Object[] 数组
LinkedList： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)
Set
HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素
LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)
Queue
PriorityQueue: Object[] 数组来实现二叉堆
ArrayQueue: Object[] 数组 + 双指针
Map
HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》
Hashtable： 数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap： 红黑树（自平衡的排序二叉树）
集合和数组的区别
如何选用集合? 主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。
当我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。
为什么要使用集合？ 当我们需要保存一组类型相同的数据的时候，我们应该是用一个容器来保存，这个容器就是数组，但是，使用数组存储对象具有一定的弊端， 因为我们在实际开发中，存储的数据的类型是多种多样的，于是，就出现了“集合”，集合同样也是用来存储多个数据的。
数组的缺点是一旦声明之后，长度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数据的类型；而且，数组存储的数据是有序的、可重复的，特点单一。 但是集合提高了数据存储的灵活性，Java 集合不仅可以用来存储不同类型不同数量的对象，还可以保存具有映射关系的数据。
Collection 子接口之 List ArrayList 和 Vector 的区别?
底层存储数据结构 - 本质上都是数组,Vector是使用队列[先进先出]来存储数据,但是本质仍然是数组.
线程安全性 - 前者是线程不安全,后者是线程安全
默认大小 - 俩者都是长度为10
扩容机制 - 前者是1.5倍,后者默认是扩容2倍,可以扩容系数可以设置的.
ArrayList和Vector检索元素，由于是数组，时间复杂度是O(1)，在集合的尾部插入或者删除是O(1)，但是其他的地方增加，删除，都是O(n)，因为涉及到了数组元素的移动
ArrayList的删除和插入的效率一定会比LinkedList低吗? - 不一定,看是否操作的是集合的尾部
ArrayList 与 LinkedList 区别?
ArrayList基于动态数组实现；LinkedList基于双向链表实现。- 链表会比数组消耗更多的空间/内存.
对于随机index访问的get和set方法，ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素；LinkedList要移动指针遍历每个元素直到找到为止。
选择要么是header头结点开始,要么从尾节点开始
数组通过下标查询效率高->本质上数组在内存中是一块连续的区域,线性的有序的
新增和删除元素，LinkedList的速度要优于ArrayList。因为ArrayList在新增和删除元素时，可能扩容和复制数组；LinkedList实例化对象需要时间外，只需要修改指针即可。
LinkedList查询进行了一些优化 - index如果在前面一半，从前面开始遍历，index在后面一半，从后往前遍历。
另外，不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。我在上面也说了，LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的时间复杂度都是 O(n) 。
Collection 子接口之 Set comparable 和 Comparator 的区别
comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序
一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo()方法或compare()方法，当我们需要对某一个集合实现两种排序方式，比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo()方法和使用自制的Comparator方法或者以两个 Comparator 来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的 Collections.sort()
Comparator 定制排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ArrayList<Integer> arrayList = new ArrayList <Integer>(); arrayList.add(-1 ); arrayList.add(3 ); arrayList.add(3 ); arrayList.add(-5 ); arrayList.add(7 ); arrayList.add(4 ); arrayList.add(-9 ); arrayList.add(-7 ); System.out.println("原始数组:" ); System.out.println(arrayList); Collections.reverse(arrayList); System.out.println("Collections.reverse(arrayList):" ); System.out.println(arrayList); Collections.sort(arrayList); System.out.println("Collections.sort(arrayList):" ); System.out.println(arrayList); Collections.sort(arrayList, new Comparator <Integer>() { @Override public int compare (Integer o1, Integer o2) { return o2.compareTo(o1); } }); System.out.println("定制排序后：" ); System.out.println(arrayList); 原始数组: [-1 , 3 , 3 , -5 , 7 , 4 , -9 , -7 ] Collections.reverse(arrayList): [-7 , -9 , 4 , 7 , -5 , 3 , 3 , -1 ] Collections.sort(arrayList): [-9 , -7 , -5 , -1 , 3 , 3 , 4 , 7 ] 定制排序后： [7 , 4 , 3 , 3 , -1 , -5 , -7 , -9 ]
重写 compareTo 方法实现按年龄来排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 public class Person implements Comparable <Person> { private String name; private int age; public Person (String name, int age) { super (); this .name = name; this .age = age; } public String getName () { return name; } public void setName (String name) { this .name = name; } public int getAge () { return age; } public void setAge (int age) { this .age = age; } @Override public int compareTo (Person o) { if (this .age > o.getAge()) { return 1 ; } if (this .age < o.getAge()) { return -1 ; } return 0 ; } } public static void main (String[] args) { TreeMap<Person, String> pdata = new TreeMap <Person, String>(); pdata.put(new Person ("张三" , 30 ), "zhangsan" ); pdata.put(new Person ("李四" , 20 ), "lisi" ); pdata.put(new Person ("王五" , 10 ), "wangwu" ); pdata.put(new Person ("小红" , 5 ), "xiaohong" ); Set<Person> keys = pdata.keySet(); for (Person key : keys) { System.out.println(key.getAge() + "-" + key.getName()); } } 5 -小红10 -王五20 -李四30 -张三
无序性和不可重复性的含义是什么
无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
不可重复性是指添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 hashCode() 方法。
比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同
HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。
Collection 子接口之 Queue Queue 与 Deque 的区别 Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。
Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
Queue 接口
抛出异常
返回特殊值
插入队尾
add(E e)
offer(E e)
删除队首
remove()
poll()
查询队首元素
element()
peek()
Deque 是双端队列，在队列的两端均可以插入或删除元素。
Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：
Deque 接口
抛出异常
返回特殊值
插入队首
addFirst(E e)
offerFirst(E e)
插入队尾
addLast(E e)
offerLast(E e)
删除队首
removeFirst()
pollFirst()
删除队尾
removeLast()
pollLast()
查询队首元素
getFirst()
peekFirst()
查询队尾元素
getLast()
peekLast()
事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。
ArrayDeque 与 LinkedList 的区别 ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？
ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。
从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。
PriorityQueue(优先级队列) PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。
这里列举其相关的一些要点：
PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。
PriorityQueue 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第K大的数、带权图的遍历等，所以需要会熟练使用才行。
Map接口 HashMap 和 Hashtable 的区别
线程是否安全： HashMap 是非线程安全的 ，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；
对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个 ；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍 。② 创建时如果给定了容量初始值 ，那么 Hashtable 会直接使用你给定的大小，而HashMap 会将其扩充为 2 的幂次方大小 （HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间 （后文中我会结合源码对这一过程进行分析）。Hashtable 没有这样的机制。
HashMap为了得到元素的位置，首先需要根据元素的 KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。Hashtable直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数发来获得最终的位置。
HashMap 中带有初始容量的构造函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public HashMap (int initialCapacity, float loadFactor) { if (initialCapacity < 0 ) throw new IllegalArgumentException ("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException ("Illegal load factor: " + loadFactor); this .loadFactor = loadFactor; this .threshold = tableSizeFor(initialCapacity); } public HashMap (int initialCapacity) { this (initialCapacity, DEFAULT_LOAD_FACTOR); }
下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小。
1 2 3 4 5 6 7 8 9 10 11 12 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 ; }
HashMap 和 HashSet 区别 HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。
HashMap
HashSet
实现了 Map 接口
实现 Set 接口
存储键值对
仅存储对象
调用 put()向 map 中添加元素
调用 add()方法向 Set 中添加元素
HashMap 使用键（Key）计算 hashcode
HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以equals()方法用来判断对象的相等性
HashMap 和 TreeMap 区别 TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。
实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。
实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。示例代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public class Person { private Integer age; public Person (Integer age) { this .age = age; } public Integer getAge () { return age; } public static void main (String[] args) { TreeMap<Person, String> treeMap = new TreeMap <>(new Comparator <Person>() { @Override public int compare (Person person1, Person person2) { int num = person1.getAge() - person2.getAge(); return Integer.compare(num, 0 ); } }); treeMap.put(new Person (3 ), "person1" ); treeMap.put(new Person (18 ), "person2" ); treeMap.put(new Person (35 ), "person3" ); treeMap.put(new Person (16 ), "person4" ); treeMap.entrySet().stream().forEach(personStringEntry -> { System.out.println(personStringEntry.getValue()); }); } } person1 person4 person2 person3
上面，我们是通过传入匿名内部类的方式实现的，你可以将代码替换成 Lambda 表达式实现的方式：
1 2 3 4 TreeMap<Person, String> treeMap = new TreeMap <>((person1, person2) -> { int num = person1.getAge() - person2.getAge(); return Integer.compare(num, 0 ); });
综上，相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力 。
Lambda 表达式
1 2 3 4 5 6 7 8 new Thread (new Runnable () { @Override public void run () { System.out.println("The runable now is using!" ); } }).start(); new Thread (() -> System.out.println("It's a lambda function!" )).start();
HashSet 如何检查重复? 当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。
在 JDK1.8 中，HashSet的add()方法只是简单的调用了HashMap的put()方法，并且判断了一下返回值以确保是否有重复元素。
1 2 3 4 5 public boolean add (E e) { return map.put(e, PRESENT)==null ; }
在 JDK1.8 中，实际上无论HashSet中是否已经存在了某元素，HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。
1 2 3 4 5 6 final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {... }
HashMap 的底层实现
JDK1.8 之前
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。
JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。
1 2 3 4 5 6 7 static final int hash (Object key) { int h; return (key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); }
对比一下 JDK1.7 的 HashMap 的 hash 方法源码.
1 2 3 4 5 6 7 8 static int hash (int h) { h ^= (h >>> 20 ) ^ (h >>> 12 ); return h ^ (h >>> 7 ) ^ (h >>> 4 ); }
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。
所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
JDK1.8 之后
相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。
结合源码分析一下 HashMap 链表到红黑树的转换。
1、 putVal 方法中执行链表转红黑树的判断逻辑。
链表的长度大于 8 的时候，就执行 treeifyBin （转换红黑树）的逻辑。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 for (int binCount = 0 ; ; ++binCount) { if ((e = p.next) == null ) { p.next = newNode(hash, key, value, null ); if (binCount >= TREEIFY_THRESHOLD - 1 ) treeifyBin(tab, hash); break ; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break ; p = e; }
2、treeifyBin 方法中判断是否真的转换为红黑树。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 final void treeifyBin (Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1 ) & hash]) != null ) { TreeNode<K,V> hd = null , tl = null ; do { TreeNode<K,V> p = replacementTreeNode(e, null ); if (tl == null ) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null ); if ((tab[index] = hd) != null ) hd.treeify(tab); } }
将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树。
HashMap 的长度为什么是 2 的幂次方 为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。
这个算法应该如何设计呢？
我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方.
HashMap 多线程操作导致死循环问题 主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。
Iterator迭代器是什么 可迭代是Java集合框架下的所有集合类的一种共性，也就是把集合中的所有元素遍历一遍。迭代的过程需要依赖一个迭代器对象，那么什么是迭代器呢？
迭代器（Iterator）模式，又叫做游标模式，它的含义是，提供一种方法访问一个容器对象中各个元素，而又不需暴露该对象的内部细节。
HashMap 的 7 种遍历方式 HashMap 遍历从大的方向来说，可分为以下 4 类：
迭代器（Iterator）方式遍历；
For Each 方式遍历；
Lambda 表达式遍历（JDK 1.8+）;
Streams API 遍历（JDK 1.8+）。
但每种类型下又有不同的实现方式，因此具体的遍历方式又可以分为以下 7 种：
使用迭代器（Iterator）EntrySet 的方式进行遍历；
使用迭代器（Iterator）KeySet 的方式进行遍历；
使用 For Each EntrySet 的方式进行遍历；
使用 For Each KeySet 的方式进行遍历；
使用 Lambda 表达式的方式进行遍历；
使用 Streams API 单线程的方式进行遍历；
使用 Streams API 多线程的方式进行遍历。
接下来我们来看每种遍历方式的具体实现代码。
1.迭代器 EntrySet
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class HashMapTest { public static void main (String[] args) { Map<Integer, String> map = new HashMap (); map.put(1 , "Java" ); map.put(2 , "JDK" ); map.put(3 , "Spring Framework" ); map.put(4 , "MyBatis framework" ); map.put(5 , "Java中文社群" ); Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Integer, String> entry = iterator.next(); System.out.println(entry.getKey()); System.out.println(entry.getValue()); } } }
2.迭代器 KeySet
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class HashMapTest { public static void main (String[] args) { Map<Integer, String> map = new HashMap (); map.put(1 , "Java" ); map.put(2 , "JDK" ); map.put(3 , "Spring Framework" ); map.put(4 , "MyBatis framework" ); map.put(5 , "Java中文社群" ); Iterator<Integer> iterator = map.keySet().iterator(); while (iterator.hasNext()) { Integer key = iterator.next(); System.out.println(key); System.out.println(map.get(key)); } } }
3.ForEach EntrySet
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class HashMapTest { public static void main (String[] args) { Map<Integer, String> map = new HashMap (); map.put(1 , "Java" ); map.put(2 , "JDK" ); map.put(3 , "Spring Framework" ); map.put(4 , "MyBatis framework" ); map.put(5 , "Java中文社群" ); for (Map.Entry<Integer, String> entry : map.entrySet()) { System.out.println(entry.getKey()); System.out.println(entry.getValue()); } } }
4.ForEach KeySet
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class HashMapTest { public static void main (String[] args) { Map<Integer, String> map = new HashMap (); map.put(1 , "Java" ); map.put(2 , "JDK" ); map.put(3 , "Spring Framework" ); map.put(4 , "MyBatis framework" ); map.put(5 , "Java中文社群" ); for (Integer key : map.keySet()) { System.out.println(key); System.out.println(map.get(key)); } } }
5.Lambda
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class HashMapTest { public static void main (String[] args) { Map<Integer, String> map = new HashMap (); map.put(1 , "Java" ); map.put(2 , "JDK" ); map.put(3 , "Spring Framework" ); map.put(4 , "MyBatis framework" ); map.put(5 , "Java中文社群" ); map.forEach((key, value) -> { System.out.println(key); System.out.println(value); }); } }
6.Streams API 单线程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class HashMapTest { public static void main (String[] args) { Map<Integer, String> map = new HashMap (); map.put(1 , "Java" ); map.put(2 , "JDK" ); map.put(3 , "Spring Framework" ); map.put(4 , "MyBatis framework" ); map.put(5 , "Java中文社群" ); map.entrySet().stream().forEach((entry) -> { System.out.println(entry.getKey()); System.out.println(entry.getValue()); }); } }
7.Streams API 多线程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class HashMapTest { public static void main (String[] args) { Map<Integer, String> map = new HashMap (); map.put(1 , "Java" ); map.put(2 , "JDK" ); map.put(3 , "Spring Framework" ); map.put(4 , "MyBatis framework" ); map.put(5 , "Java中文社群" ); map.entrySet().parallelStream().forEach((entry) -> { System.out.println(entry.getKey()); System.out.println(entry.getValue()); }); } }
ConcurrentHashMap 和 Hashtable 的区别 ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式（重要）：
在 JDK1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据（下面有示意图），多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
到了 JDK1.8 的时候，ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
Hashtable :
JDK1.7 的 ConcurrentHashMap ：
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
Segment 数组中的每个元素包含一个 HashEntry 数组，每个 HashEntry 数组属于链表结构。
首先将数据分为一段一段（这个“段”就是 Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
Segment 继承了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
1 2 static class Segment <K,V> extends ReentrantLock implements Serializable {}
一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。
Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。
JDK1.8 的 ConcurrentHashMap ：
JDK1.8 的 ConcurrentHashMap 不再是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。
TreeNode是存储红黑树节点，被TreeBin包装。TreeBin通过root属性维护红黑树的根结点，因为红黑树在旋转的时候，根结点可能会被它原来的子节点替换掉，在这个时间点，如果有其他线程要写这棵红黑树就会发生线程不安全问题，所以在 ConcurrentHashMap 中TreeBin通过waiter属性维护当前使用这棵红黑树的线程，来防止其他线程的进入。
1 2 3 4 5 6 7 8 9 10 11 static final class TreeBin <K,V> extends Node <K,V> { TreeNode<K,V> root; volatile TreeNode<K,V> first; volatile Thread waiter; volatile int lockState; static final int WRITER = 1 ; static final int WAITER = 2 ; static final int READER = 4 ; ... }
Java 8 几乎完全重写了 ConcurrentHashMap，代码量从原来 Java 7 中的 1000 多行，变成了现在的 6000 多行。
ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。
Java 8 中，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。
JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？
线程安全实现方式 ：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。
Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。
并发度 ：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大.
Collection和Collections区别
Collection为集合层级的根接口,List和Set都是属于其子接口
Collections:集合工具类,里面提供了一系列操作集合的方法.
Java集合使用注意事项总结 集合判空 判断所有集合内部的元素是否为空，使用 isEmpty() 方法，而不是 size()==0 的方式。
集合转 Map 在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。
集合遍历 不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。
集合去重 可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains() 进行遍历去重或者判断包含操作。
集合转数组 使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的是类型完全一致、长度为 0 的空数组。
数组转集合 使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法， 它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。
源码分析 ArrayList源码&扩容机制分析 ArrayList 简介 ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
ArrayList继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
ArrayList 实现了 Cloneable 接口 ，即覆盖了函数clone()，能被克隆。
ArrayList 实现了 java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
Arraylist 和 Vector 的区别?
ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 ；
Vector 是 List 的古老实现类，底层使用 Object[ ]存储，线程安全的。
Arraylist 与 LinkedList 区别?
是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。
ArrayList 核心源码解读 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 package java.util;import java.util.function.Consumer;import java.util.function.Predicate;import java.util.function.UnaryOperator;public class ArrayList <E> extends AbstractList <E> implements List <E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L ; 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; 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); } } public ArrayList () { this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList (Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0 ) { if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this .elementData = EMPTY_ELEMENTDATA; } } public void trimToSize () { modCount++; if (size < elementData.length) { elementData = (size == 0 ) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } public void ensureCapacity (int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } private void ensureCapacityInternal (int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity (int minCapacity) { modCount++; if (minCapacity - elementData.length > 0 ) grow(minCapacity); } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 ; private void grow (int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1 ); if (newCapacity - minCapacity < 0 ) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0 ) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity (int minCapacity) { if (minCapacity < 0 ) throw new OutOfMemoryError (); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } public int size () { return size; } public boolean isEmpty () { return size = = 0 ; } public boolean contains (Object o) { return indexOf(o) >= 0 ; } 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 ; } public int lastIndexOf (Object 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 ; } public Object clone () { try { ArrayList<?> v = (ArrayList<?>) super .clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0 ; return v; } catch (CloneNotSupportedException e) { throw new InternalError (e); } } public Object[] toArray() { return Arrays.copyOf(elementData, size); } @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0 , a, 0 , size); if (a.length > size) a[size] = null ; return a; } @SuppressWarnings("unchecked") E elementData (int index) { return (E) elementData[index]; } public E get (int index) { rangeCheck(index); return elementData(index); } public E set (int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } public boolean add (E e) { ensureCapacityInternal(size + 1 ); elementData[size++] = e; return true ; } public void add (int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1 ); System.arraycopy(elementData, index, elementData, index + 1 , size - index); elementData[index] = element; size++; } 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; } 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 ; } 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 ; } public void clear () { modCount++; for (int i = 0 ; i < size; i++) elementData[i] = null ; size = 0 ; } public boolean addAll (Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); System.arraycopy(a, 0 , elementData, size, numNew); size += numNew; return numNew != 0 ; } public boolean addAll (int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); 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 ; } protected void removeRange (int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null ; } size = newSize; } private void rangeCheck (int index) { if (index >= size) throw new IndexOutOfBoundsException (outOfBoundsMsg(index)); } private void rangeCheckForAdd (int index) { if (index > size || index < 0 ) throw new IndexOutOfBoundsException (outOfBoundsMsg(index)); } private String outOfBoundsMsg (int index) { return "Index: " +index+", Size: " +size; } public boolean removeAll (Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false ); } public boolean retainAll (Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true ); } public ListIterator<E> listIterator (int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException ("Index: " +index); return new ListItr (index); } public ListIterator<E> listIterator () { return new ListItr (0 ); } public Iterator<E> iterator () { return new Itr (); }
ArrayList 扩容机制分析 先从 ArrayList 的构造函数说起
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 private static final int DEFAULT_CAPACITY = 10 ; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public ArrayList () { this .elementData = DEFAULTCAPACITY_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); } } public ArrayList (Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0 ) { if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this .elementData = EMPTY_ELEMENTDATA; } }
细心的同学一定会发现 ：以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。 下面在我们分析 ArrayList 扩容时会讲到这一点内容！
一步一步分析 ArrayList 扩容机制
先来看 add 方法
1 2 3 4 5 6 7 8 9 10 public boolean add (E e) { ensureCapacityInternal(size + 1 ); elementData[size++] = e; return true ; }
再来看看 ensureCapacityInternal() 方法
1 2 3 4 5 6 7 8 9 private void ensureCapacityInternal (int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }
当 要 add 进第 1 个元素时，minCapacity 为 1，在 Math.max()方法比较后，minCapacity 为 10。
如果调用 ensureCapacityInternal() 方法就一定会进入（执行）这个方法，下面我们来研究一下这个方法的源码！
1 2 3 4 5 6 7 8 9 private void ensureExplicitCapacity (int minCapacity) { modCount++; if (minCapacity - elementData.length > 0 ) grow(minCapacity); }
当我们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。
当 add 第 2 个元素时，minCapacity 为 2，此时 e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。
添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。
直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。
grow()方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 ; private void grow (int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1 ); if (newCapacity - minCapacity < 0 ) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0 ) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.
“>>”（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了 1 位所以相当于 oldCapacity /2。对于大数据的 2 进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源
我们再来通过例子探究一下grow() 方法 ：
当 add 第 1 个元素时，oldCapacity 为 0，经比较后第一个 if 判断成立，newCapacity = minCapacity(为 10)。但是第二个 if 判断不会成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，则不会进入 hugeCapacity 方法。数组容量为 10，add 方法中 return true,size 增为 1。
当 add 第 11 个元素进入 grow 方法时，newCapacity 为 15，比 minCapacity（为 11）大，第一个 if 判断不成立。新容量没有大于数组最大 size，不会进入 hugeCapacity 方法。数组容量扩为 15，add 方法中 return true,size 增为 11。
以此类推······
java 中的 length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法.
java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看
hugeCapacity() 方法。
从上面 grow() 方法源码我们知道： 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。
1 2 3 4 5 6 7 8 9 10 11 private static int hugeCapacity (int minCapacity) { if (minCapacity < 0 ) throw new OutOfMemoryError (); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
System.arraycopy() 和 Arrays.copyOf()方法 阅读源码的话，我们就会发现 ArrayList 中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index, E element)、toArray() 等方法中都用到了该方法！
System.arraycopy() 方法
1 2 3 4 5 6 7 8 9 10 11 12 public static native void arraycopy (Object src, int srcPos, Object dest, int destPos, int length) ;
场景
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public void add (int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1 ); System.arraycopy(elementData, index, elementData, index + 1 , size - index); elementData[index] = element; size++; }
测试
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class ArraycopyTest { public static void main (String[] args) { int [] a = new int [10 ]; a[0 ] = 0 ; a[1 ] = 1 ; a[2 ] = 2 ; a[3 ] = 3 ; System.arraycopy(a, 2 , a, 3 , 3 ); a[2 ]=99 ; for (int i = 0 ; i < a.length; i++) { System.out.print(a[i] + " " ); } } } 0 1 99 2 3 0 0 0 0 0
Arrays.copyOf()方法
源码
1 2 3 4 5 6 7 8 public static int [] copyOf(int [] original, int newLength) { int [] copy = new int [newLength]; System.arraycopy(original, 0 , copy, 0 , Math.min(original.length, newLength)); return copy; }
场景
1 2 3 4 5 6 7 public Object[] toArray() { return Arrays.copyOf(elementData, size); }
个人觉得使用 Arrays.copyOf()方法主要是为了给原有数组扩容，测试代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 public class ArrayscopyOfTest { public static void main (String[] args) { int [] a = new int [3 ]; a[0 ] = 0 ; a[1 ] = 1 ; a[2 ] = 2 ; int [] b = Arrays.copyOf(a, 10 ); System.out.println("b.length" +b.length); } } 10
两者联系和区别
联系：
看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法
区别：
arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。
ensureCapacity方法 ArrayList 源码中有一个 ensureCapacity 方法不知道大家注意到没有，这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，那么这个方法有什么作用呢？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public void ensureCapacity (int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } }
理论上来说，最好在向 ArrayList 添加大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数
我们通过下面的代码实际测试以下这个方法的效果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public class EnsureCapacityTest { public static void main (String[] args) { ArrayList<Object> list = new ArrayList <Object>(); final int N = 10000000 ; long startTime = System.currentTimeMillis(); for (int i = 0 ; i < N; i++) { list.add(i); } long endTime = System.currentTimeMillis(); System.out.println("使用ensureCapacity方法前：" +(endTime - startTime)); } } 使用ensureCapacity方法前：2158
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class EnsureCapacityTest { public static void main (String[] args) { ArrayList<Object> list = new ArrayList <Object>(); final int N = 10000000 ; long startTime1 = System.currentTimeMillis(); list.ensureCapacity(N); for (int i = 0 ; i < N; i++) { list.add(i); } long endTime1 = System.currentTimeMillis(); System.out.println("使用ensureCapacity方法后：" +(endTime1 - startTime1)); } } 使用ensureCapacity方法后：1773
通过运行结果，我们可以看出向 ArrayList 添加大量元素之前使用ensureCapacity 方法可以提升性能。不过，这个性能差距几乎可以忽略不计。而且，实际项目根本也不可能往 ArrayList 里面添加这么多元素。
HashMap源码&底层数据结构分析 HashMap 简介 HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。
HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。
底层数据结构分析
JDK1.8 之前
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。
HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。
JDK 1.8 HashMap 的 hash 方法源码:
JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。
1 2 3 4 5 6 7 static final int hash (Object key) { int h; return (key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); }
对比一下 JDK1.7 的 HashMap 的 hash 方法源码.
1 2 3 4 5 6 7 8 static int hash (int h) { h ^= (h >>> 20 ) ^ (h >>> 12 ); return h ^ (h >>> 7 ) ^ (h >>> 4 ); }
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。
所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
JDK1.8 之后
相比于之前的版本，JDK1.8 以后在解决哈希冲突时有了较大的变化。
当链表长度大于阈值（默认为 8）时，会首先调用 treeifyBin()方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 resize() 方法对数组扩容。相关源码这里就不贴了，重点关注 treeifyBin()方法即可！
类的属性：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public class HashMap <K,V> extends AbstractMap <K,V> implements Map <K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L ; 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 ; transient Node<k,v>[] table; transient Set<map.entry<k,v>> entrySet; transient int size; transient int modCount; int threshold; final float loadFactor; }
loadFactor 加载因子
loadFactor 加载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。
loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。
给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。
threshold
threshold = capacity * loadFactor，当 Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。
Node 节点类源码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 static class Node <K,V> implements Map .Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this .hash = hash; this .key = key; this .value = value; this .next = next; } public final K getKey () { return key; } public final V getValue () { return value; } public final String toString () { return key + "=" + value; } public final int hashCode () { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue (V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals (Object o) { if (o == this ) return true ; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true ; } return false ; } }
树节点类源码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 static final class TreeNode <K,V> extends LinkedHashMap .Entry<K,V> { TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super (hash, key, val, next); } final TreeNode<K,V> root () { for (TreeNode<K,V> r = this , p;;) { if ((p = r.parent) == null ) return r; r = p; }
HashMap 源码分析 构造方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public HashMap () { this .loadFactor = DEFAULT_LOAD_FACTOR; } public HashMap (Map<? extends K, ? extends V> m) { this .loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false ); } public HashMap (int initialCapacity) { this (initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap (int initialCapacity, float loadFactor) { if (initialCapacity < 0 ) throw new IllegalArgumentException ("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException ("Illegal load factor: " + loadFactor); this .loadFactor = loadFactor; this .threshold = tableSizeFor(initialCapacity); }
putMapEntries 方法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 final void putMapEntries (Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0 ) { if (table == null ) { float ft = ((float )s / loadFactor) + 1.0F ; int t = ((ft < (float )MAXIMUM_CAPACITY) ? (int )ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); } else if (s > threshold) resize(); for (Map.Entry<? extends K , ? extends V > e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false , evict); } } }
put 方法 HashMap 只提供了 put 用于添加元素，putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用。
对 putVal 方法添加元素的分析如下：
如果定位到的数组位置没有元素 就直接插入。
如果定位到的数组位置有元素就和要插入的 key 比较，如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。
说明:上图有两个小问题：
直接覆盖之后应该就会 return，不会有后续操作。参考 JDK8 HashMap.java 658 行（issue#608）。
当链表长度大于阈值（默认为 8）并且 HashMap 数组长度超过 64 的时候才会执行链表转红黑树的操作，否则就只是对数组扩容。参考 HashMap 的 treeifyBin() 方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 public V put (K key, V value) { return putVal(hash(key), key, value, false , true ); } final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0 ) n = (tab = resize()).length; if ((p = tab[i = (n - 1 ) & hash]) == null ) tab[i] = newNode(hash, key, value, null ); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this , tab, hash, key, value); else { for (int binCount = 0 ; ; ++binCount) { if ((e = p.next) == null ) { p.next = newNode(hash, key, value, null ); if (binCount >= TREEIFY_THRESHOLD - 1 ) treeifyBin(tab, hash); break ; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break ; p = e; } } if (e != null ) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null ) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null ; }
我们再来对比一下 JDK1.7 put 方法的代码
对于 put 方法的分析如下：
① 如果定位到的数组位置没有元素 就直接插入。
② 如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和插入的 key 比较，如果 key 相同就直接覆盖，不同就采用头插法插入元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public V put (K key, V value) if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null ) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); 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 ; }
get 方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public V get (Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode (int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1 ) & hash]) != null ) { if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null ) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null ); } } return null ; }
resize 方法
进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 final 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"}) 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 ) newTab[e.hash & (newCap - 1 )] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this , newTab, j, oldCap); else { 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; } if (hiTail != null ) { hiTail.next = null ; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
