文章目录
数组千千万，集合是真理
我们在代码中常见的数据保存形式一般就是两种—>数组与集合；数组和集合的最大的区别在于查询和扩展，一般情况下，在数据确定的情况下，我们采用数组的形式会更便于我们查询，而在数据长度不确定的情况下，我相对更推荐集合。
数组与集合的扩容
数组的扩容
我们都知道的是数组在一旦确定下来的时候我们是无法对数组的长度进行改变的，所以对数组进行扩容就只能通过创建一个新的更长的数组来将原来的数组长度给复制过去才可以。这一段我在数组的时候就有所研究了，所以直接给大家上一段代码帮助理解：
int[] arr1 = new int[3];
arr1[0]=1;
arr1[1]=2;
arr1[2]=3;
//打印传入的数据
System.out.println("arr1:");
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i]+",");
}
System.out.println();
//复制值
int[] arr2 = new int[arr1.length*2];
for (int i = 0; i < arr1.length; i++) {
arr2[i] = arr1[i];
}
arr2[arr1.length] = 4;
//展示复制后的数组
for (int i = 0; i < arr2.length; i++) {
System.out.print(arr2[i]+",");
}
集合的扩容
集合的扩容相对来说就比数组要简单很多了，因为集合本身的特点就是:提供一种存储可变的存储模型，存储数据容量可以随时改变。下面以ArrayList举例叭:
List<String> list = new ArrayList<String>();
list.add("pier");
list.add("is");
list.add("大聪明");
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
集合细解
集合的大概框架
集合的大概主要分为两类：Collection集合与Map集合，他们都是用来存储数据的，但是最主要的使用区别是，Collection集合存储的更多是元素集合，他们内部的存储数据是有序的，数据是可以重复的，而Map集合存储的更多的是键值对形式的数据，它内部的数据是无序的，并且内部的‘键值’是不可重复的。
下面给大家分享一个集合的菜鸟编程图叭：
由上面图我们可以看到的东西分为下面三类框架：
接口：是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象
实现（类）：是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
算法：是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现。
Collection集合类架构
Collection集合分为三大类：List、Set、Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet等等接口。
List集合细解
List存储元素的特点
① List集合遵循集合的特点，他是有序的(怎么进去的，出来的顺序也是怎样的。)
② 它的内部元素是可以重复的。
深入研究ArrayList
下面先看一张简单的ArrayList图:
容量：CAPACITY ； 实际大小：size；
ArrayList底层的数据结构就是数组，数组元素类型为Object类型，即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作底层都是基于数组的。
ArrayList最主要的功能就是Add方法还有他的自动扩容机制，下面我们就通过他的源码，一起看看叭(注释翻译来源于百度翻译，有错误莫怪博主能力低下，不能翻译。)，我们发现了add方法有两个一个是有参的，一个是无参的，但是他们都有一个共同的特点就是在末尾加上自己的数据，因为我们读取时肯定是需要从头到尾读取，所以符合我们“先进先出”的原则，存入数据的步骤大概就是(箭头的指向就是信息传递的方向,然后名字只是一个代号，大家理解就好，由于第一次用，我小小解释一下啊)
上面一个简单对话，就把我们的数据的添加以及简单的扩容机制讲解清楚了，下面我们一起看看ArrayList的源码叭：
/**
*将指定的元素追加到此列表的末尾。
*要附加到此列表的@param e元素
*@return{@code true}（由{@link Collection#add}指定）
*/
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
//这是add(E e)的实现代码
/**
*这个助手方法从add（E）to keep方法中分离出来
*字节码大小小于35（默认值为-XX:MaxInlineSize），
*这有助于在C1编译循环中调用add（E）。
*/
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();//这里的grow就是我们下一段要讲的扩容机制
elementData[s] = e;
size = s + 1;
}
/**
*将指定的元素追加到此列表的末尾。
*
*要附加到此列表的@param e元素
*@return{@code true}（由{@link Collection#add}指定）
* /**
*将指定的元素插入此文件中的指定位置
*名单。移动当前处于该位置的元件（如果有），并
*右侧的任何后续元素（将一个元素添加到其索引中）。
*
*@param index将插入指定元素的索引
*@param元素要插入的元素
*@throws IndexOutOfBoundsException{@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
看完上面的Add方法是否发现了我们对话里面的grow老大了呢，是的有的，两个实现的Add方法都是需要grow()老大的，我们就去查看一下它的源码叭！
⚔一探grow()究竟
/**
*增加容量，以确保它至少可以容纳
*最小容量参数指定的元素数。
*
*@param minCapacity所需的最小容量
*@如果minCapacity小于零，则抛出OutOfMemoryError
*/
private Object[] grow(int minCapacity) {
// 获取当前数组的容量
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 扩容。新的容量=当前容量+当前容量/2.即将当前容量增加一半（当前容量增加1.5倍）。
//分解一下下面代码
// int newCapacity = oldCapacity + (oldCapacity >> 1);
//newlength代码
/**int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
if (newLength - MAX_ARRAY_LENGTH <= 0) {
return newLength;
}
}**/
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
//把原本的数值赋值给新的集合
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
private Object[] grow() {
return grow(size + 1);
}
看完这平平无奇的10多行代码,一种“我上我也行”的感觉油然而生，但就是这平平无奇的10多行代码就是我们整个ArrayList扩容机制的核心它内部的扩容确实也是我们能够实现的，但细读过后，你会发现它的扩容机制其实底层就是由数组的长度实现的，在初始值的长度为10的情况下，后面再逐步增加长度，当我们的size长度和CAPACITY数组最大长度一致时，就会引发扩容机制，而每一次增加长度为原来长度的1.5倍。
接下来，我们看一下这个整个add的完整流程图叭
由于这个有点太多了，下次再给大家分享具体的实现案例叭，今天先给大家分享一下他的大概流程了。
Set集合细解
Set集合特点：
①Set集合类似于一个罐子，程序可以依次把多个对象“丢进”Set集合，而Set集合通常不能记住元素的添加顺序。实际上Set就是Collection只是行为略有不同(Set不允许包含重复元素)。
②Set集合不允许包含相同的元素，如果试图把两个相同元素加入同一个Set集合中，则添加操作失败，add()方法返回false，且新元素不会被加入。
Set主要常用的几种接口就是TreeSet、HashSet以及它的子类(LinkedHashSet)。
接下来和我一起去看看他们三个接口使用的区别叭：
HashSet
**Hashset的概述：**HashSet是Set接口的典型实现，大多数时候使用Set集合时就是使用这个实现类。HashSet按Hash算法来存储集合中的元素，因此具有很好的存取和查找性能。底层数据结构是 哈希表
HashSet的特点:
①不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也可能发生变化；
②HashSet不是同步的；
③集合元素值可以是null；
HashSet注意点:
①HashSet存储的键key可以为null,但是也仅仅局限只有一个null；
②在使用HashSet时如果在自定义对象时一定要重写equals()和hashCode()方法，不然也可能会出现数据重复的情况，因为hashCode不知道怎么比较你的元素是否相同。
③HashSet集合判断两个元素的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode方法返回值也相等。
Ps:底层原理：靠元素重写hashCode方法和equals方法来判断两个元素是否相等，如果相等则覆盖原来的元素，依此来确保元素的唯一性。
HashSet元素不重复的底层代码研究
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
static final long serialVersionUID = -5024744406713321676L;
// 底层使用HashMap来保存HashSet中所有元素。
private transient HashMap<E,Object> map;
// 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
private static final Object PRESENT = new Object();
/**
* 默认的无参构造器，构造一个空的HashSet。
*
* 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
*/
public HashSet() {
map = new HashMap<E,Object>();
}
/**
* 构造一个包含指定collection中的元素的新set。
*
* 实际底层使用默认的加载因子0.75和足以包含指定
* collection中所有元素的初始容量来创建一个HashMap。
* @param c 其中的元素将存放在此set中的collection。
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* 以指定的initialCapacity和loadFactor构造一个空的HashSet。
*
* 实际底层以相应的参数构造一个空的HashMap。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 以指定的initialCapacity构造一个空的HashSet。
*
* 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
* @param initialCapacity 初始容量。
*/
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
/**
* 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
* 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。
*
* 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
* @param dummy 标记。
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。
*
* 底层实际调用底层HashMap的keySet来返回所有的key。
* 可见HashSet中的元素，只是存放在了底层HashMap的key上，
* value使用一个static final的Object对象标识。
* @return 对此set中元素进行迭代的Iterator。
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
/**
* 返回此set中的元素的数量（set的容量）。
*
* 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。
* @return 此set中的元素的数量（set的容量）。
*/
public int size() {
return map.size();
}
/**
* 如果此set不包含任何元素，则返回true。
*
* 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。
* @return 如果此set不包含任何元素，则返回true。
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
* 如果此set包含指定元素，则返回true。
* 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))
* 的e元素时，返回true。
*
* 底层实际调用HashMap的containsKey判断是否包含指定key。
* @param o 在此set中的存在已得到测试的元素。
* @return 如果此set包含指定元素，则返回true。
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* 如果此set中尚未包含指定元素，则添加指定元素。
* 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2))
* 的元素e2，则向此set 添加指定的元素e。
* 如果此set已包含该元素，则该调用不更改set并返回false。
*
* 底层实际将将该元素作为key放入HashMap。
* 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key
* 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true），
* 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变，
* 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中，
* 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。
* @param e 将添加到此set中的元素。
* @return 如果此set尚未包含指定元素，则返回true。
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/**
* 如果指定元素存在于此set中，则将其移除。
* 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e，
* 则将其移除。如果此set已包含该元素，则返回true
* （或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。
*
* 底层实际调用HashMap的remove方法删除指定Entry。
* @param o 如果存在于此set中则需要将其移除的对象。
* @return 如果set包含指定元素，则返回true。
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
/**
* 从此set中移除所有元素。此调用返回后，该set将为空。
*
* 底层实际调用HashMap的clear方法清空Entry中所有元素。
*/
public void clear() {
map.clear();
}
/**
* 返回此HashSet实例的浅表副本：并没有复制这些元素本身。
*
LinkedHashSet
**LinkedHashSet的概述：**它是HashSet的子类，它与HashSet最大的区别就是它可以记住你放进来数据的顺序
LinkedHashSet的特点：
由于LinkedHashSet是一个哈希表和链表的结合，且是一个双向链表，那么我们来看一下什么是双向连边?
双向连边: 双向链表是链表的一种，他的每个数据节点都有两个指针分别指向直接后继和直接前驱，所以从双向链表的任意一个节点开始都可以很方便的访问它的前驱节点和后继节点。这是双向链表的优点，那么有优点就有缺点，缺点是每个节点都需要保存当前节点的next和prior两个属性，这样才能保证优点。所以需要更多的内存开销，并且删除和添加也会比较费时间。
ps：LinkedHashSet：他的注意点和HashSet大致相同，唯一需要重点注意的是他们俩的使用场景，待会将TreeSet和他们量放一起说。
TreeSet
TreeSet概述:TreeSet是实现Set接口的实现类。所以它存储的值是唯一的，同时也可以对存储的值进行排序，排序用的是红黑树原理。所以要理解这个类，必须先简单理解一下什么是红黑树。
红黑树
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树的特性:(红黑树详解)
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
注意：
（01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
（02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接*衡的二叉树。
ps:我们可以简单的理解就是他会对进来的数据进行排序，将进来的第一个数据作为根节点，在依次存入数据，将比根节点大的放右边,比根节点小的放左边，以此来完成我们的排序。
Set总结
HashSet：哈希表是通过使用称为散列法的机制来存储信息的，元素并没有以某种特定顺序来存放；HashSet输出是和原来的添加的顺序是不一致的，因为其保存的位置是根据其哈希值来确定．
TreeSet：提供一个使用树结构存储Set接口的实现，对象以升序顺序存储，访问和遍历的时间很快。TreeSet使用红黑树结构进行保存，因此其内部是有序的，输出也是有序的．（TreeSet一般不能存null）
LinkedHashSet：以元素插入的顺序来维护集合的链接表，允许以插入的顺序在集合中迭代；LinkedHashSet使用链表来保存，因此输出时和插入时的顺序是一致的．
我们应该根据不同的数据去选择不同的集合来满足我们的要求。
Queue
它所对应的是队列，队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。
LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
Java的LinkedList是一种常用的数据容器，与ArrayList相比，LinkedList的增删操作效率更高，而查改操作效率较低。使用形式可以参考ArrayList。
Map集合类框架
Map集合的概述:
①将键映射到值的对象；
②一个映射不能包含重复的键；
③每个键最多只能映射到一个值。
Map接口和Collection接口的不同:
①Map是双列的,Collection是单列的;
②Map的键唯一,Collection的子体系Set是唯一的;
③Map集合的数据结构针对键有效，跟值无关;Collection集合的数据结构是针对元素有效。
Map功能讲解
常用方法
| 序号 | 使用方法 | 方法描述 |
|---|---|---|
| 1 | V put(K k,V v) | 向集合中添加一对元素 |
| 2 | V remove(K k) | 根据键删除键值对元素 |
| 3 | void clear() | 清空集合(官方:从此映射中移除所有映射关系（可选操作）) |
| 4 | boolean containsKey(K k) | 判断集合中是否包含指定的键 |
| 5 | boolean containsValue(V v) | 判断集合中是否包含指定的值 |
| 6 | boolean isEmpty() | 判断集合是否为空 |
| 7 | int size() | 获取集合的长度 |
| 8 | V get(K k) | 根据键获取值 |
| 9 | Set< K >keySet() | 获取所有的键，保存在Set集合中 |
| 10 | Collection values() | 获取所有的值，保存到Collection集合中 |
| 11 | Set<Map.Entry<K,V>> entrySet() | 获取所有键值对，封装成Entry对象 |
Map实例
public static void main(String[] args) {
Map<String,Integer> map = new HashMap<String,Integer>();
//存入数据
map.put("张三",800);
map.put("李四",1500);
map.put("王五",3000);
//查看数据
// System.out.println(map.toString());
for(String s : map.keySet()){
System.out.println(s+"的工资为:"+map.get(s)+"元。");
}
map.put("张三",2600);
//更改后查看张三的工资
System.out.println("张三工资更改成功！");
System.out.println("当前张三的工资为:"+map.get("张三")+"元。");
//加薪
System.out.println("给员工每人加100元。");
for (String s : map.keySet()){
map.put(s,(map.get(s)+100));
}
System.out.println("加薪成功！");
//查看所有员工
for(String s : map.keySet()){
System.out.print(s+"\t");
}
System.out.println("查看工资");
//遍历所有的工资方法一：
for(int i :map.values()){
System.out.println(i);
}
for(String s : map.keySet()){
System.out.println(s+"的工资为:"+map.get(s)+"元。");
}
//遍历所有的工资方法二：
Set<Map.Entry<String,Integer>> entries = map.entrySet();
for (Map.Entry<String,Integer> entry : entries) {
System.out.println(entry.getKey()+"的工资为:"+entry.getValue()+"元。");
}
}
一般情况下，使用方法二的entrySet方法的效率会比第一种高一点，推荐使用第二种方式。
最后在简单的为大家简述一下HashMap以及它子类LinkedHashMap还有TreeMap：
这几个实现类的区别与联系可以总结为以下几点：
1）HashMap：
非线程安全，是根据键的hashCode值来存储数据，具有很快的访问速度，但是遍历顺序不确定。 在JDK1.8之前HashMap的底层是由数组+链表实现的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间；
所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
2）LinkedHashMap：
是HashMap的一个子类，保存了记录的插入顺序。在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
3）TreeMap：
实现的是SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。底层实现是红黑树。