一、区别
- 数组：可以存储基本数据类型和对象，数组的长度固定，不适合在对象数量未知的情况下使用。
- 集合：只能存储对象，对象类型可以不一样，长度可变，可在多数情况下使用。
二、数组
1、介绍
Java中最基本的一个存储结构。
提供了动态创建和访问 Java 数组的方法。其中的元素的类型必须相同。
效率高，但容量固定且无法动态改变。
它无法判断其中实际存有多少元素，length只是告诉我们array的容量。
数组是多个相同类型数据的组合，实现对这些数据的统一管理
数组属于引用类型，数组型数据是对象（Object），数组中的每个元素相当于该对象的成员变量
数组中的元素可以是任何数据类型，包括基本类型和引用类型
数组作为参数和返回值时，传递的都是地址值
2、初始化方式
- 动态初始化（指定长度）
动态初始化时数组时，数组中元素自动拥有默认值：
int：0 boolean：false float：0.0 char：”\u0000”(十六进制，空白字符) 引用类型：null
int[] nums = new int[3];- 静态初始化（指定数组内容）
int[] nums = new int[]{1,2,3};
int[] nums = {1,2,3}; //简写- 不能在给定初始值的同时还给定长度
3、数组的使用
- 获取数组长度
int l = nums.length;- 获取数组指定索引的值
int a = nums[1];- 对数组进行赋值
nums[1]=1;- 数组输出字符串
直接输出数组为地址值
System.out.println( Arrays.toString(nums) );- 数组转化为集合
Arrays.asList()限制太多，所以采用原始方式
int arrs[] = {1, 2};
//1.遍历
List<Integer> list = new ArrayList<>();
for (int ele : arrs) {
list.add(ele);
}
System.out.println(list);4、静态类Arrays
此静态类专门用来操作array ，提供搜索、排序、复制等静态方法
//1.转化为字符串
public static String toString(Object[] a)
//2.使用二分搜索算法搜索指定值，返回目标索引
//a：被搜索数组
//fromIndex/toIndex：搜索开始结束索引，可省略
//key：搜索目标
public static int binarySearch(Object[] a, int fromIndex, int toIndex,Object key)
//3.复制指定数组，返回新数组
//original：源数组
//newLength：指定新数组的长度，如果大于原数组，则将多余的部分填充默认值；如果小于，则截去多余部分
//from/to：复制原数组的范围
public static <T> T[] copyOf(T[] original, int newLength)
public static <T> T[] copyOfRange(T[] original, int from, int to)
//4.判断2个数组对象地址值是否相等，即是否是同一个对象
public static boolean equals(Object[] a, Object[] a2)
//5.判断2个数组对象内容是否相等
public static boolean deepEquals(Object[] a1, Object[] a2)
//6.将指定的值填充到数组的每个元素
//fromIndex/toIndex:填充范围的开始索引和结束索引，可省略（代表全部填充）
//val:填充的值
public static void fill(Object[] a, int fromIndex, int toIndex, Object val)
//7.按照数字顺序排列指定数组
//fromIndex/toIndex:开始结束索引，可省略
//cmp:排序方法，可省略
public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> cmp)
//8.使用提供的生成函数来计算每个元素，设置指定数组的所有元素。
public static <T> void setAll(T[] array, IntFunction<? extends T> generator)
//9.排序元素，双轴快速排序
// 该算法在许多数据集上提供O（n log（n））性能，导致其他快速排序降级为二次性能，并且通常比传统（单轴）Quicksort实现更快。
//fromIndex/toIndex:开始结束索引，可省略
public static void sort(Object[] a, int fromIndex, int toIndex)Arrays.asList()
该方法是将数组转化成List集合的方法。
String[] ss = {"a","b","c"};
List<String> strings = Arrays.asList(ss);注意：
（1）该方法适用于对象型数据的数组（String、Integer…）
（2）该方法不建议使用于基本数据类型的数组（byte,short,int,long,float,double,boolean）
（3）该方法将数组与List列表链接起来：当更新其一个时，另一个自动更新
（4）不支持add()、remove()、clear() 等方法，但支持 get()、set()，即获得的新集合只能查询和修改元素，不能删除和新增元素
如果存储基本数据类型
int[] nums = {1,2,3};
String[] ss = {"a","b","c"};
List<int[]> ints = Arrays.asList(nums);
System.out.println(ints);
List<String> strings = Arrays.asList(ss);
System.out.println(strings);输出
[[I@5e9f23b4]
[a, b, c]源码
Arrays 的内部类 ArrayList 采用了装饰者模式，装饰了原数组，当调用查询和修改方法时，操作的是原数组，所以通过 asList() 方法创建的集合和原数组数据都是存储在原数组中
public class Arrays {
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable {
private static final long serialVersionUID = -2764017481108945198L;
// 源数组
private final E[] a;
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
@Override
public int size() {
return a.length;
}
@Override
public Object[] toArray() {
return a.clone();
}
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
int size = size();
if (a.length < size)
return Arrays.copyOf(this.a, size,
(Class<? extends T[]>) a.getClass());
System.arraycopy(this.a, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
@Override
public E get(int index) {
return a[index];
}
@Override
public E set(int index, E element) {
E oldValue = a[index];
a[index] = element;
return oldValue;
}
@Override
public int indexOf(Object o) {
E[] a = this.a;
if (o == null) {
for (int i = 0; i < a.length; i++)
if (a[i] == null)
return i;
} else {
for (int i = 0; i < a.length; i++)
if (o.equals(a[i]))
return i;
}
return -1;
}
@Override
public boolean contains(Object o) {
return indexOf(o) != -1;
}
@Override
public Spliterator<E> spliterator() {
return Spliterators.spliterator(a, Spliterator.ORDERED);
}
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
for (E e : a) {
action.accept(e);
}
}
@Override
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
E[] a = this.a;
for (int i = 0; i < a.length; i++) {
a[i] = operator.apply(a[i]);
}
}
@Override
public void sort(Comparator<? super E> c) {
Arrays.sort(a, c);
}
}
}三、Collection集合接口
单列集合。统一定义了一套单列集合的接口
继承该接口的集合接口：List，set
Set和List对比：
Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。
1、接口方法
- 添加元素
向集合中添加一个元素。集合更改则添加成功返回true，如果该集合不允许重复并且已经包含指定的元素。返回false。部分子类的add方法可能会限制添加到集合中的元素类型，或者不会将NULL添加到集合中。
boolean add(E e)
//将指定集合添加到源集合中
boolean addAll(Collection<? extends E> c);- 删除集合所有元素
void clear();- 判断集合是否包含指定元素
boolean contains(Object o);
//判断集合中是否包含指定集合的所有元素
boolean containsAll(Collection<?> c);- 判空
boolean isEmpty();- 判等
boolean equals(Object o);- 删除元素
//删除指定元素，List中重写该方法
boolean remove(Object o);
//删除原集合中包含的所有参数集合的元素
boolean removeAll(Collection<?> c);
//仅保留源集合中的参数集合的元素
boolean retainAll(Collection<?> c);- 获得集合的元素数（集合长度）
int size();- 集合转化为数组
Object[] toArray();
//可转化为指定的数据类型的数组
<T> T[] toArray(T[] a);2、List集合
- 继承 自collection接口
- 有序集合，存取一致
- 有索引
- 允许重复元素
（1）ArrayList：底层数据结构是数组，查询快，增删慢，线程不安全，效率高，可以存储重复元素
（2）LinkedList 底层数据结构是链表，查询慢，增删快，线程不安全，效率高，可以存储重复元素
（3）Vector:底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素
（1）List接口特有方法
- 在指定索引处添加元素
void add(int index, E element);- 返回指定索引处的元素
E get(int index);- 删除指定索引处的元素
E remove(int index);- 替换元素
用element元素替换原集合中索引为index的元素
E set(int index, E element);（2）ArrayList
底层的数据结构就是数组elementData，数组元素类型为Object类型，即可以存放所有类型数据，线程不安全。
①ArrayList实现AbstractList抽象类，而AbstractList抽象类实现List接口为什么要这样？
接口中全部是抽象的方法，而抽象类中可以有抽象方法，还可以有具体的实现方法
②构造方法
无参（初始化时默认为空数组，在添加元素时赋予默认初始容量为10）
有参（设置数组的初始容量）
有参（将指定Collection集合的元素赋值到新的Arraylist中）
③扩容机制
以无参数构造方式创建ArrayList时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作（首次调用add方法）时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10。
当add第11个元素时，又会进行扩容，数组大小扩容为原来的1.5倍。
扩容调用的是grow()方法：
- 现将
int newCapacity = oldCapacity + (oldCapacity >> 1);通过位运算将容量置为原来的1.5倍。 - 新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，所以每次扩容不一定是原来的1.5倍，也可能是数组当前的所需最小容量
- 判断新容量是否大于集合的最大容量（2的31次方-8）
- 给elementData从新赋值
（3）LinkedList
底层是双向链表，线程不安全
他还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆 栈、队列和双向队列使用。
//LinkedList三个属性
transient int size = 0; //链表长度
transient Node<E> first; //首节点
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;
}
}get方法
public E getFirst() //获取第一个元素
public E getLast() //获取最后一个元素
//获取第index个元素
public E get(int index)
/*比较传入的索引参数index与集合长度size/2，如果是index小，那么从第一个顺序循环，直到找到为止；如果index大，那么从最后一个倒序循环，直到找到为止。也就是说越靠近中间的元素，调用get(int index方法遍历的次数越多，效率也就越低，而且随着集合的越来越大，get(int index)执行性能也会指数级降低。*/peek方法
public E peek() //获取第一个元素
public E peekFirst() //同peek
public E peekLast() //获取最后一个元素
peek和get的区别，当链表为空时，get会抛出异常，而peek会返回null（4）Vector
底层是数组，线程安全
3、Set集合
- 不允许重复元素
- 无索引
- 不能用普通的for循环遍历
不重复原理：存储的元素不许重写hashCode和equal方法
（1）HashSet
- 元素无序且唯一，存取不一
- 底层是哈希表（数组+链表 / 数组+红黑树）（查询速度非常快）
- 存储自定义元素时，必须重写hashCode和equal方法
- 线程不安全，效率高，可以存储null元素
底层采用HashMap实现，将数据存储到HashMap的key中保证唯一。
底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性。
具体实现唯一性的比较过程：存储元素首先会使用hash()算法函数生成一个int类型hashCode散列值，然后已经的所存储的元素的hashCode值比较，如果hashCode不相等，则所存储的两个对象一定不相等，此时存储当前的新的hashCode值处的元素对象；如果hashCode相等，存储元素的对象还是不一定相等，此时会调用equals()方法判断两个对象的内容是否相等，如果内容相等，那么就是同一个对象，无需存储；如果比较的内容不相等，那么就是不同的对象，就该存储了，此时就要采用哈希的解决地址冲突算法，在当前hashCode值处类似一个新的链表， 在同一个hashCode值的后面存储存储不同的对象，这样就保证了元素的唯一性。
Set的实现类的集合对象中不能够有重复元素，HashSet也一样他是使用了一种标识来确定元素的不重复，HashSet用一种算法来保证HashSet中的元素是不重复的， HashSet采用哈希算法，底层用数组存储数据。默认初始化容量16，加载因子0.75。
Object类中的hashCode()的方法是所有子类都会继承这个方法，这个方法会用Hash算法算出一个Hash（哈希）码值返回，HashSet会用Hash码值去和数组长度取模， 模（这个模就是对象要存放在数组中的位置）相同时才会判断数组中的元素和要加入的对象的内容是否相同，如果不同才会添加进去。
（2）LinkedHashSet
底层数据结构采用链表和哈希表共同实现，双向链表（记录元素的存储顺序）保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。其实就是 LinkedHashMap
线程不安全，效率高。
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -2851667679971038690L;
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
@Override
public Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
}
}- LinkedHashSet继承于HashSet,它的源码很少，只有几个构造函数，基本上都是调用父类HashSet的构造函数。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
// LinkedHashSet 调用的是该构造函数，非 public
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
}（3）TreeSet
不允许null值
底层数据结构采用二叉树来实现，元素唯一且已经排好序。
唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造），自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同，不需要存储；比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法；
4、Collections集合工具类
//1.往集合中加入多个元素
public static <T> boolean addAll(Collection<? super T> c, T... elements)
//2.使用二叉搜索算法搜索元素
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
//3.将src集合元素复制到dest集合，会覆盖原有得到元素，只支持List集合
public static <T> void copy(List<? super T> dest, List<? extends T> src)
//4.如果两个指定的集合“没有”共同的元素，则返回 true 。
public static boolean disjoint(Collection<?> c1, Collection<?> c2)
//5.用指定元素填充集合
public static <T> void fill(List<? super T> list, T obj)
//6.返回集合中与该元素相等的元素的个数
public static int frequency(Collection<?> c, Object o)
//7.返回目标集合在源集合中 第一次/最后一次 出现的索引
public static int indexOfSubList(List<?> source, List<?> target)
public static int lastIndexOfSubList(List<?> source, List<?> target)
//8.根据其元素的 自然顺序返回给定集合的 最大/最小 元素。 可自定义排序方式
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
//9.替换集合中的某个指定值的所有元素
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)
//10.反转集合的元素顺序
public static void reverse(List<?> list)
//11.返回一个比较器，它对实现Comparable接口的对象集合施加与自然排序相反的比较。 （自然顺序是由物体本身的确定的顺序对compareTo方法）。这使得能够简单成语用于分拣（或维持）实现该对象的集合（或阵列） Comparable在反向自然顺序接口。
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)
//12.随机打乱元素顺序
public static void shuffle(List<?> list)
//13.排序元素，采用双轴快速排序
public static <T> void sort(List<T> list, Comparator<? super T> c)
//14.交换指定列表中指定位置的元素。
public static void swap(List<?> list, int i, int j)
四、Map集合
- 没有继承自Collection接口
- 双列集合，包含key，value
- key不可重复，value可重复
1、HashMap
详细参阅：https://blog.csdn.net/woshimaxiao1/article/details/83661464
（1）数据结构
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）
Entry是HashMap中的一个静态内部类。
简单来说，HashMap由数组+单向链表（+红黑树jdk1.8新增）组成的（哈希表），数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
hashMap在jdk1.7和1.8有较大的改进
JDK1.7
由数组+链表实现，初始容量16，负载因子默认0.75，当内部数据存储达到容量*负载因子时进行扩容。
entry静态内部类，数组中存储的数据是以Entry的形式存在。，包含以下属性
final K key;
V value;
Entry<K,V> next; //实现链表，指向下一个Entry
int hash; //哈希值JDK1.8
由数组+链表+红黑树实现，初始容量16，负载因子默认为0.75；
HashMap数组部分成为哈希桶，当链表长度大于等于8时，链表转化为红黑树；当长度降到6时，红黑树转化为链表。
数据存储的形式由Entry变更为Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
....
}（2）put方法
HashMap采用链表法解决哈希冲突；HashMap中的每一个对象不仅仅是一个Entry对象，还是一个链表的头结点；当出现哈希冲突时，会把新值加入指定位置的链表的头结点（1.8之前头插法，1.8及之后尾插法）；当查找一个值时，会先查找到链表的头结点，如果该节点的值不是期望的值时，会继续查找链表其他的值；
Hash算法：
index=HashCode（key）&（length-1）先求出key的哈希值，在这个值和HashMap当前容量-1做按位与运算；
//当存储key="rewind"，value="value"
"rewind”.hashcode()=766411=10111011000111001001(2) //计算key的哈希值
length-1=15=1111(2) //当前容量-1，当前为默认容量，当容量-1为2的次幂时，结果都为1
1011011000111001001 & 1111=1001 //按位与运算，获得数组索引（key的映射）1001=9，当容量-1全为1时，数组索引值只取决于key的哈希值的后面几位数
//1、为何要于(容量-1)做或运算？
//答：目的是获取当前元素在新数组的索引时，索引值不会大于容量。
//2、为何HashMap的容量必须是2的次幂？
//答：当容量为2的次幂时，容量-1的二进制数必定全为1，这样&计算得出的结果只取决于key的哈希值，由此
//HashMap的Node的数组索引的分布只取决于外部因素（key），相对来说比较均匀，不会出现一部分索引有很
//多数据（链表很长），而一部分索引没有数据.
//当容量不为2的次幂时，例如10，则10-1的二进制数为1001(2)，当进行&运算时，永远不会出现0110等，
//因为0与0、1进行&运算时都为0，这样就导致了HashMap数组中的好几个索引处不可能存在数据，导致内存
//地址的浪费由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同（因为结果总是只取决于key的哈希值的后几位），这就是哈希冲突。
当出现哈希冲突时，采用链表法解决
- JDK1.7 会将相同的index的新值放到链表的头结点（头插法），即数组中的相应索引的位置，因为HashMap认为后插入的元素查询的次数比较多。
- JDK 1.8 尾插法，因为头插法会导致链表死链
（3）HashMap扩容
resize() 方法
因为HashMap数组容量有限，当多次插入数据后，key的映射（数组索引）发生冲突的概率比较高，此时HashMap需要扩容他的数组长度，也就是HashMap的扩容。
判断HashMap扩容的条件：
HashMap当前存储的数据量 >= HashMap的数组最大容量 * 负载因子（默认0.75）满足条件时，会创建新的Node数组，长度为原来的2倍，之后会遍历原来的Node数组，把之前所有的Node对象重新哈希到新的数组。
不可以直接复制，因为哈希的规则随着数组的容量改变而改变，当数组容量发生改变时，key的映射也应该发生改变。
// 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// int 最大值
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final Node<K,V>[] resize() {
// oldTab 为旧数组
Node<K,V>[] oldTab = table;
// oldCap 旧数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// threshold 字段为 hashmap 下一次扩容长度
// oldThr 即此次扩容的结果的长度
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// oldCap 大于 int 最大值,则取int最大值,不在进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新长度 = 2 * 旧长度
// 16 <= 旧长度 <= 2 * 旧长度 < int 最大值 ， 则下一次扩容的目标长度为此次的2倍
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);
}
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;
// 将旧数组元素赋值到e
if ((e = oldTab[j]) != null) {
// 断开旧数组对e的引用
oldTab[j] = null;
if (e.next == null)
// 如果e没有后续元素，即只有头结点，直接hash赋值即可
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;
}
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;
}（4）链表、红黑树转化
当链表节点数小于8时，采用的是链表方式实现，当大于8时，链表转化为红黑树（目的：提高查找效率）
当红黑树的节点个数小于6时，转化为链表。
（5）为什么1.8链表从头插法改成尾插法
因为头插法
resize()会造成死链JDK7用头插是考虑到了一个所谓的热点数据的点(新插入的数据可能会更早用到)，但这其实是个伪命题,因为JDK7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置(就是因为头插) 所以最后的结果 还是打乱了插入的顺序 所以总的来看支撑JDK7使用头插的这点原因也不足以支撑下去了 所以就干脆换成尾插 一举多得
2、HashTable、ConcurrentHashMap
HashTable线程安全，但是已经淘汰，当前要求线程安全一般采用ConcurrentHashMap
由于 HashMap 是一个线程不安全的容器，主要体现在容量大于总量*负载因子发生扩容时会出现环形链表 从而导致死循环。因此需要支持线程安全的并发容器 ConcurrentHashMap
3、HashMap和Hashtable区别
相同点
- 都是基于哈希表实现的，内部元素都是key，value的形式
- 都实现了Map，Cloneable，Serializable接口
不同点
父类不同：HashMap继承自AbstractMap，Hashtable继承自Dictionary
是否允许null值：HashMap允许null的key-value值，Hashtable不允许null值
线程安全性：HashMap线程不安全，Hashtable线程安全，HashTable 内部的方法基本都经 过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
性能方面：HashMap的put、get操作可以达到常数的时间复杂度，Hashtable的put和get操作因为加了
syncharonized锁，所以效率较差底层数据结构：jdk1.8之后hashMap新增了红黑树，而HashTable没有
初始容量大小和每次扩充容量大小的不同：
①创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。 HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小
4、HashMap的遍历方式
（1）通过 map.keySet 遍历 key 和 value
普遍使用
for(String key :map.keySet()){
System.out.println("key= "+key+" value= "+map.get(key));
} （2）通过 map.entrySet 使用 iterator 遍历 key 和 value
Iterator<Map.Entry<String, String>> ite = map.entrySet().iterator();
while(ite.hasNext()){
Map.Entry<String, String> entry = ite.next();
System.out.println("key= "+entry.getKey()+" value= "+entry.getValue());
}（3）通过 map.entrySet 遍历 key 和 value
推荐尤其是容量大的时候
for(Map.Entry<String, String> entry: map.entrySet()){
System.out.println("key= "+entry.getKey()+" value= "+entry.getValue());
}（4）使用 map.values()遍历所有的 value 但不能遍历 key
for(String v:map.values()){
System.out.println("value= "+v);
}5、为什么由头插改成尾插
HashMap 在并发的情况下存在两个问题：
- 并发扩容导致数据丢失（问题仍未解决）
- 链表死循环（改成尾插法解决了该问题）
（1）并发扩容数据丢失
即2个及以上线程并发添加数据，同时进行扩容，此时节点 Node 内的 next 指针无法保证线程安全
线程1：put c
当前old table（后面简称OT）的索引3: 3=a->b->null
当前new table（后面简称NT）的索引3：null
取出OT索引3处节点a
节点a子节点置为NT的索引3处节点，即：a->null
放入NT索引3处节点a
当前new table（后面简称NT）的索引3：3=a->null
取出OT索引3处节点的子节点b
节点b子节点置为NT的索引3处节点，即：b->a->null
放入NT索引3处节点b，并将NT索引3处的节点a置为节点b的子节点
当前new table（后面简称NT）的索引3：3=b->a->null
线程1扩容结束
线程2：put d
- 当前old table（后面简称OT）的索引3: 3=a->b->null
- 当前new table（后面简称NT）的索引3：3=null
- 取出OT索引3处节点a
- 节点c子节点置为NT的索引3处节点，即：a->null
- 放入NT索引3处节点a
- 此时节点a子节点为null，遍历结束
- 最终new table（后面简称NT）的索引3：3=a->null
- 线程2扩容结束
（2）链表死循环
头插法的初衷是设计者遵循一个新加进来的元素可能被使用的频率更高，这其实是一个伪命题，因为在hashmap扩容的时候，链表也是会发生颠倒的，因为是先从头节点开始转移掉新的hash表中。
头插法还有一个致命的缺点，就是在多线程下会出现循环链的情况，导致死循环
具体是怎么死循环的可以理解为因为扩容是会有一个颠倒的机制，所以多线程操作的时候有可能出现线程1让A->B 而线程2让B->A,导致了循环，之所以会出现这个情况，核心在于这样一句代码，e.next = newTable[i];
这也就是头插法的代码，但是这样会出现一个问题就是，假如在原数组中是a指向b，当线程1完成元素迁移时若是a，b仍在一个索引那么会变成b指向a，但是此时线程二拿到CPU资源，但是在线程2中e指向的是a，那么此时执行e.next = newTable[i]；就会变成a指向b，那么就形成了一个循环链表。
jdk 1.8 改成尾插法，解决了该问题
- 造成原因就是扩容转移过程中修改了原来链表中节点的引用关系。
- 使用尾插法不会引起死循环，是因为保持之前节点的引用关系。
6、LinkedHashMap
LinkedHashMap继承自HashMap，它的多种操作都是建立在HashMap操作的基础上的。同HashMap不同的是，LinkedHashMap维护了一个Entry的双向链表，保证了插入的Entry中的顺序。
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V> {
static class Entry<K,V> extends HashMap.Node<K,V> {
// 双向链表
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
//...
}五、阻塞队列
BlockingQueue（阻塞队列）：
ArrayBlockingQueue：基于数组实现的阻塞队列LinkedBlockingQueue：基于链表实现的阻塞队列PriorityBlockingQueue：基于堆实现的带有优先级的阻塞队列
六、线程安全容器
1、第一代线程安全集合类
Vector、Hashtable
是怎么保证线程安排的：使用synchronized修饰方法
缺点：效率低下
2、第二代线程非安全集合类
ArrayList、HashMap
线程不安全，但是性能好，用来替代Vector、Hashtable
使用ArrayList、HashMap,需要线程安全怎么办呢？
Collections.synchronizedList(list);
Collections.synchronizedMap(m);底层使用synchronized代码块锁虽然也是锁住了所有的代码，但是锁在方法里边，并所在方法外边性能可以理解为稍有提高吧。毕竟进方法本身就要分配资源的
3、第三代线程安全集合类
在大量并发情况下如何提高集合的效率和安全呢？
java.util.concurrent.*
ConcurrentHashMap：底层采用 CAS 和synchronized锁少量代码CopyOnWriteArrayList：底层采用ReentrantLockCopyOnWriteArraySet：注意不是CopyOnWriteHashSet，底层采用ReentrantLock
