Java集合

• • 概述
  • 数组
  • • 优缺点
    • 操作数组
    • • 定义数组
      • 遍历数组
      • 数组去重
      • 数组与集合转换
      • 数组排序
      • 复制数组
  • ArrayList
  • • RandomAccess
    • Cloneable
    • • 浅拷贝与深拷贝
      • ArrayList中clone方法
    • ArrayList扩容
    • ArrayList与linkedList
    • 线程安全问题
  • Set
  • Queue
  • HashMap
  • • 相关概念
    • 结构
    • • 为什么要使用红黑树
      • 为什么不一开始就用红黑树代替链表结构
      • 为什么树化阈值为8
      • 为什么树化阈值和链表阈值不设置成一样
      • 引入红黑树后，如果单链表节点个数超过8个是否一定会树化
    • 容量
    • • 为什么负载因子默认是0.75
      • 如果指定容量大小为10，那么实际大小是多少
      • 默认初始化容量为什么是16
      • 初始化容量设置多少合适
    • 扩容
    • • 为什么要进行扩容
      • 什么时机进行扩容
      • 1.7扩容
      • 1.8扩容

Java中的集合主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

如果你看过ArrayList类源码，就知道ArrayList底层是通过数组来存储元素的，所以如果严格来说，数组也算集合的一种。

Java中提供的数组是用来存储固定大小的同类型元素，所以Java数组就是同类数据元素的集合。

数组是引用数据类型，如果使用了没有开辟空间的数组，则一定会出现NullPointerException异常信息。所以数组本质上也是Java对象，能够向下或者向上转型,能使用instanceof关键字。

// 数组的父类也是Object,可以将a向上转型到Object  
int[] a = new int[8];  
Object obj = a ; 

// 可以进行向下转型 
int[] b = (int[])obj;  

// 可以用instanceof关键字进行类型判定 
if(obj instanceof int[]){ 
}

void method_name(int ... value)方法中变参就是当数组处理的，参数为定参的编译后就是数组。一个方法只能有一个变参，即使是不同的类型也不行，变参参数只能在形参列表的末尾，如果传入的是数组，则只能传一个。

数组优点:

• 数组元素的内存地址是连续分配的，所以通过下标访问元素的效率很高，可以快速找到指定下标为n的元素的地址；

数组缺点:

• 数组一旦初始化之后长度是固定的不能变的；
• 数组进行元素的删除和插入操作的时候，效率比较低,需要移动大量的元素；
• 数组元素的类型只能是一种；
• 数组元素的内存地址是连续分配的,对内存要求高一些;相对于链表结构比较,链表的内存是连续不连续都可以；

数组的优点是效率高，但为此，所付出的代价就是数组对象的大小被固定。这也使得在工作中，数组并不实用。所以我们应该优选容器，而不是数组。只有在已证明性能成为问题的时候，并且确定切换到数组对性能提高有帮助时，才应该将项目重构为使用数组。

由于数组没有提供任何的封装，所有对元素的操作，都是通过自定义的方法实现的，对数组元素的操作比较麻烦，好在Java自带了一些API供开发者调用。

 int[] array1 = { 1,2,3,4,5 }; 
 int[] array2 = new int[10];
 int[] array3 = new int[]{ 1,2,3,4,5 };

需要注意的是[],写在数组名称的前后都可以,但是推荐第一种写法：

  int[] array1 = { 1,2,3,4,5 };
  int array2[] = { 1,2,3,4,5 };

 for (int i = 0; i < array1.length; i++) {
       System.out.println(array1[i]);
 }

// 最简单方法，利用 hashSet 集合去重
Set set2 = new HashSet();
for (int i = 0; i < arr11.length; i++) {
    set2.add(arr11[i]);
}

// 数组转成set集合
Set set = new HashSet(Arrays.asList(array2));

// 数组转list 
List list2 = Arrays.asList(array);

 // 原生方法 或 8种排序算法
 Arrays.sort(arr);

// 待复制的数组
int[] arr = {1, 2, 3, 4};

// 指定新数组的长度
int[] arr2 = Arrays.copyOf(arr, 10);

// 只复制从索引[1]到索引[3]之间的元素（不包括索引[3]的元素）
int[] arr3 = Arrays.copyOfRange(arr, 1, 3);

在List接口实现类中，最常用的就是ArrayList,ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，可以添加或删除元素。

ArrayList 继承了 AbstractList ，并实现了 List、RandomAccess, Cloneable 接口：

public class ArrayList extends AbstractList implements List, RandomAccess,Cloneable,Serializable

Random是随机的意思，Access是访问的意思，合起来就是随机访问的意思。

RandomAccess接口是一个标记接口，用来标记实现的List集合具备快速随机访问的能力。所有的List实现都支持随机访问的，只是基于基本结构的不同，实现的速度不同罢了。

当一个List拥有快速访问功能时，其遍历方法采用随机访问速度最快，而没有快速随机访问的List采用顺序访问的速度最快。如果集合中的数据量过大需要遍历时，此时需要格外注意，因为不同的遍历方式会影响很大，可以使用instanceof关键字来判断该类有没有RandomAccess标记:

// 假设 list 数据量非常大,推荐写法
List