数组，集合

数组

• 数组三大特性：

1. 一致性：数组只能保存相同数据类型元素，元素的数据类型可以是任何相同的数据类型。
   2.有序性：数组中的元素是有序的，通过下标访问。
   3.不可变性：数组一旦初始化，则长度（数组中元素的个数）不可变。

• 数组类型是从抽象基类 Array 派生的引用类型,Arrays 类是一个工具类，其中包含了数组操作的很多方法
  1.toString:将一个数组转换成一个字符串
  2.sort:对数组的数组元素进行排序
  3.equals:比较两个数组。长度相等，且数组元素也一一相同
  4.copyOf:复制一个新数组，可指定新的长度
  5.binarySearch：搜索元素值所在的索引，如没有返回负数，需要元素已经升序排列好
• 长度是length
• 缺点：就是一旦声明，就不能改变容量，这个也是其使用频率不高的原因。

集合

• Java 集合类型分为 Collection 和 Map，它们是 Java 集合的根接口，这两个接口又包含了一些子接口或实现类。
  1.Iterator——Collection——List,Set
  List——LinkedList,ArrayList,Vector
  Set——TreeSet，HashSet
  2.Map——HashMap,HashTable.TreeMap

List：有序集合，允许有相同的元素
Set：不能包含重复的元素
Map：以 key➡value 的形式保存
ArrayList:基于动态数组的实现，查找快，增删慢
LinkedList:链式，查找慢，增删快

ArrayList常用方法：

get(index):获取下标为index的元素值
index():返回此集合中第一次出现指定元素的索引，如果此集合不包含该元素，则返回 -1
lastIndexOf():返回此集合中最后一次出现指定元素的索引，如果此集合不包含该元素，则返回 -1
set():修改指定下标的元素值
subList(int fromlndex, int tolndex):返回一个指定下标段的新集合，前包后不包
add()：添加元素

ArrayList:

1.自动扩容：源码有个grow方法，每次扩大原来的1.5倍。扩容完后，会调用arraycopy来对数组进行拷贝。
2.使用ArrayList比较多的原因：平时遍历要比增删多，而且增加往往在最后增加，时间复杂度为O(1),Array底层增删倍优化过，现在也不比LinkedList慢。
3.线程不安全

Vector:

是线程安全的，扩容是2倍。

HashSet:

1.不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化。
2.HashSet 不是同步的，如果多个线程同时访问或修改一个 HashSet，则必须通过代码来保证其同步。
3.集合元素值可以是 null。
4.当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后根据该 hashCode 值决定该对象在 HashSet 中的存储位置。如果有两个元素通过 equals() 方法比较返回的结果为 true，但它们的 hashCode 不相等，HashSet 将会把它们存储在不同的位置，依然可以添加成功。
5.为优化査询速度而设计的 Set。它是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素，实现比较简单

HsahMap:

按哈希算法来存取键对象：
1，判断键值对数组是否为空或则为null,否则进行resize()扩容
2，根据键值key拿去计算hashcode，来定位数组索引，如果索引数组为null，就新建节点添加，添加完后判断实际存在得键值对是否超过最大容量，超过就扩容
3，如果索引数组不为null,判断首个元素是否和key一样，如果相同就覆盖value,相同就是先比hashcode,再比equals
4，看索引数组是否是红黑树，如果是红黑树，直接插入键值对
5，如果不是红黑树，就遍历索引数组里的链表，判断链表长度是否大于8，大于的话就把链表转成红黑树，在红黑树中插入，否则进行链表的插入，遍历过程中如果发现key存在就直接覆盖
6，填加完后判断实际存在得键值对是否超过最大容量，超过就扩容

扩容 resize 分为两步：
1）扩容：创建一个新的 Entry/Node 空数组，长度是原数组的 2 倍
2）ReHash：遍历原 Entry/Node 数组，把所有的 Entry/Node 节点重新 Hash 到新数组
为什么要 ReHash 呢？直接复制到新数组不行吗？
显然是不行的，因为数组的长度改变以后，Hash 的规则也随之改变。index 的计算公式是这样的：
index = HashCode(key) & (Length - 1)

Map接口的常用方法:

clear():删除该 Map 对象中的所有 key-value 对
containsKey(Object key):查询 Map 中是否包含指定的 key，如果包含则返回 true
containsValue(Object value):查询 Map 中是否包含一个或多个 value，如果包含则返回 true
get(Object key):返回 Map 集合中指定键对象所对应的值
put(K key, V value):向 Map 集合中添加键-值对，如果当前 Map 中已有一个与该 key 相等的 key-value 对，则新的 key-value 对会覆盖原来的 key-value 对
putAll(Map m):将指定 Map 中的 key-value 对复制到本 Map 中
remove(Object key):从 Map 集合中删除 key 对应的键-值对，返回 key 对应的 value，如果该 key 不存在，则返回 null
remove(Object key, Object value):这是 Java8 新增的方法，删除指定 key、value 所对应的 key-value 对。如果从该 Map 中成功地删除该 key-value 对，该方法返回 true，否则返回 false
isEmpty():查询该 Map 是否为空（即不包含任何 key-value 对），如果为空则返回 true
size():返回该 Map 里 key-value 对的个数