Java基础集合上篇
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
本篇博文目录:
一.集合框架
集合类存放于 Java.util 包中主要有 3 种set(集、list(列表包含 Queue和 map(映射)。
① CollectionCollection 是集合 List、Set、Queue 的最基本的接口。
② Iterator迭代器可以通过迭代器遍历集合中的数据。
③ Map是映射表的基础接口。
集合框架二个顶级接口Collection和Map即相关子接口和实现类如下:
二.List
Java 的 List 是非常常用的数据类型。List 是有序的 Collection。Java List 一共三个实现类分别是 ArrayList、Vector 和 LinkedList。
1. ArrayList 数组
ArrayList 是最常用的 List 实现类内部是通过数组实现的(
数据结构:数组(动态)) 它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔当数组大小不满足时需要增加存储能力就要将已经有数组的数据复制到新的存储空间中数组扩容。当从 ArrayList 的中间位置插入或者删除元素时需要对数组进行复制、移动、代价比较高增删效率低。因此它适合随机查找和遍历不适合插入和删除查询修改效率高通过索引的方式查询效率非常的高可以达到O(1)。
- 初始化操作
ArrayList有三种初始化方式方式1传递一个数组长度进行初始化方式2无参构造函数方式3传递一个Collection的集合进行初始化。
当传入的initialCapacity=0时,Object [] elementData = {};当initialCapacity>0时 this.elementData = new Object[initialCapacity];
采用无参构造方法时: this.elementData = {}
采用Collection参数进行初始化时会通过elementData = c.toArray();将传入的Collection集合转换为Object[]类型的数组进行初始化操作并且如果当E[]类型的数据转换为object[]时出现问题 通过elementData = Arrays.copyOf(elementData, size, Object[].class); 进行初始化。
- 增
往数组中添加单个元素(add())有二种方式方式一直接传入数据方式二下标加数据的方式。
add(E e)方法中首先调用 ensureCapacityInternal(size + 1); // size默认为0,加1后为1 【
这个的作用就是确保容量够用不够用就扩容】
ensurecapacityInternal(int mincapacity)会返回DEFAULT_CAPACITY和minCapacity这二者中最大的一个值如果没有修改过minCapacity 的值的话,minCapacity = 1(首次添加元素,采用无参构造函数)默认采用DEFAULT_CAPACITY(private static final int DEFAULT_CAPACITY = 10;
ArrayList集合默认容量10)。
minCapacity - elementData.length > 0 判断是否需要进行扩容
grow()方法就是扩容方法其中oldCapacity表示获取未扩容前数组的大小newCapacity表示扩容后的大小oldCapacity + (oldCapacity >> 1);
表示每次增加当前容量的1/2(当前容量的1.5倍)然后判断扩容的容量是否能够装本次的数据如果可以采用扩容容量如果不可以采用添加数据后的容量大小接着判断一下当前容量是否超过了最大值Integer.MAX_VALUE - 8;超过了就采用hugeCapacity()返回的容量最后通过 Arrays.copyOf(elementData, newCapacity);对源数组进行扩容。
回到最初的add()方法ensureCapacityInternal(size+1)用来确保源数组够用elementData[size++] = e;才是执行数据添加操作。
add(int index, E element)方法中首先通过 rangeCheckForAdd(index);判断小标是否越界,然后看是否需要进行扩容 ensureCapacityInternal(size + 1); 接着通过System.arraycopy进行位置移动位置移动是因为往数组中添加一个值在该下标之后的值要往后移动有点类似于插队在队伍中插入了一个人该人后面的所有人都要往后面移动一个最后进行初始化elementData[index] = element;。
移动过程:
addAll的二种实现方式大致思路差不多:
方式1不带下表插入一组数据(
System.arraycopy(C, 0, elementData, size, C.length);):
方式2,带下标插入一组数据:
- 删
remove(int index) 删除的过程就是先通过移动位置把后面的值往前移动(队伍中有一个人不排了在该人后面的所有人都往前移动一个位置)然后把最后一个赋null
clear()方法就是遍历数组然后一个一个的赋Null
remove(Object o)有二种情况第一种传入的是一个null对象就把数组中所有null的值进行移除移除思路和上面的remove(int index)一样第二种情况传入指定删除的元素遍历数组获取指定元素的index,然后根据remove(int index)的思路进行删除。
- 查询
通过数组的索引获取指定元素的值所以查询效率非常高。
- 改
修改就是把旧值进行覆盖,这种方式不需要像添加那样去移动元素效率也是非常的高。
2.Vector 数组实现、线程同步
Vector 与 ArrayList 一样也是通过数组实现的不同的是它
支持线程的同步即某一时刻只有一个线程能够写 Vector避免多线程同时写而引起的不一致性但实现同步需要很高的花费因此Vector的访问效率比ArrayList慢。
- 默认容量为10
- 采用synchronized同步表示线程是安全的但是效率会降低
- 如果没有设置capacityIncrement自定义扩容大小不设置capacityIncrement=0表示采用默认扩容采用默认扩容为当前容量的2倍
3.LinkList链表
LinkedList 是用链表结构存储数据的
数据结构:双向链表很适合数据的动态插入和删除随机访问和遍历速度比较慢增删效率高查询和遍历效率低因为查询需要从头结点开始遍历。另外他还提供了 List 接口中没有定义的方法专门用于操作表头和表尾元素可以当作堆栈、队列和双向队列使用。
- 头结点和尾结点
- Node结点(next:表示下一个节点;prev:表示前一个节点;element:表示存放的数据)
- 增
可以通过addFirst(E e)和addLast(E e)添加头结点和尾结点
添加头结点的思路就是首先将newFirst的next指向oldFirst接着first=newFirst如果最开始没有头结点当前插入的头结点=尾结点如果最开始存在头结点将oldFirst的prev执行newFirst。(
添加效率相较于动态数组来说快多了不需要移动数据)
详细的源码:
添加尾结点的思路就是将oldLast的next指向newLast接着last=newLast如果最开始没有尾结点当前的头结点就是尾结点,如果最开始有尾结点 last=newLast。
详细的源码
add(E e)方法添加数据就是在往尾部添加和上面尾部添加数据思路一致。
addAll(Collection<? extends E> c)和addAll(int index, Collection<? extends E> c)第一种方法往尾部添加一组数据只需要遍历这组需要添加的数据然后通过尾部添加数据的方式依次添加数据最后将最后一个节点变为last节点方法2是指定位置插入一组数据首先获取指定数据的节点(succ)接着通过指定节点获取前一个节点(pre)然后通过尾部添加数据的方式依次添加数据最后将最后一个节点的next指向指定节点然后将指定节点的prev指向添加数据的最后一个节点。
思路图其中①表示尾部添加一组数据 addAll(Collection<? extends E> c)②表示指定位置插入一组数据addAll(int index, Collection<? extends E> c) 。
- 删
删除节点数据有三种方式方式一从头结点开始删方式2从尾结点开始删方式3指定位置或数据进行删方式一比如remove() 和removeFirst()方法就是按头结点进行移除思路就是获取first节点的下一个节点next然后将first节点的item和next置null,接着将next节点设置为first头结点,最后判断一下next节点是否为null(为null说明最开始只有一个头结点),如果为null就把last置null,不为null就把next的prev设置为null,因为next变为头结点后就没有前一个节点了。
方式2按尾结点进行删,思路和方式一差不多找到last的前一个节点prev然后将last节点置null(item和prev)然后将前一个节点prev设置为last尾结点最后判断一次prev节点是否为null(头结点=尾结点只有一个节点),如果为first置null,如果不为prev的next置null。
方式三remove(int index)和remove(Object o)都是通过unlink()方法删除当前节点数据unlink()方法就是先通过当前节点获取当前节点的前一个节点next和后一个节点prev;首先判断prev前一个节点是否为null,如果为null说明要删除的节点为first节点所以把first设置为next节点如果prev不为null,那么说明要删除的节点前面有节点将该节点的next指向next节点并把删除节点的prev设置为null,接着判断删除节点下一个节点next是否为null,如果为null说明删除节点是尾结点将尾结点last设置为删除节点的前一个节点prev,如果不为null说明删除节点后面存在下一个节点next,那么就把next节点的prev设置为删除节点的前一个节点prev,然后将删除节点的next设置为null 有点绕具体看下面三张图。
删除节点前后都有节点将prev节点的next指向next,将next的prev指向prev:
删除节点前无节点后有节点,说明删除节点为firt节点,将next节点设置为first节点:
删除节点前有节点后无节点,说明删除节点为last节点,将prev节点设置为last节点:
- 查询
查询首先判断一下index距离first和last谁更近如果离first更近就从first开始向后找直到找到后进行返回如果离last更近就从last往前开始找找到返回 (
和动态数组相比LinkedList查询效率明显慢的多)。
- 改
该需要先通过node(int index)方法找到要修改的node,然后将该node的值修改为新值。(
需要先进行查询然后再进行修改所以效率较低)
三.Set
Set 注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素值不能重复。对象的相等性本质是对象 hashCode 值java 是依据对象的内存地址计算出的此序号判断的如果想要让两个不同的对象视为相等的就必须覆盖 Object 的 hashCode 方法和 equals 方法。
1.HashSetHash 表
哈希表边存放的是哈希值(
数据结构:Hash表(数组+单向链表))。HashSet 存储元素的顺序并不是按照存入时的顺序和 List 显然不同 而是按照哈希值来存的所以取数据也是按照哈希值取得 (无序)。元素的哈希值是通过元素的hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值如果哈希值一样接着会比较equals 方法 如果 equls 结果为 true HashSet 就视为同一个元素。如果 equals 为 false 就不是同一个元素 (不能够存入相同元素相同元素就hashcode 和equals 都相同可以存入null)。
- 初始化
HashSet的初始化工作本质上是去初始化一个HashMap的集合
( map = new HashMap<>();)
- 增
add(E e)方法通过HashMap的put方法插入数据,key=传入的值,value=new Object() 对象( private static final Object PRESENT = new Object(); )。
put(K key, V value)方法中通过 putVal(hash(key), key, value, false, true); 插入数据。主要的三个参数第一个参数通过hash(key)获取一个hash值( 该hash值是一个当前key的hashCode做异或运算后的值并不是纯hashCode:
(key.hashCode()) ^ (h >>> 16)),第二个参数key,第三个参数value。
putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) 方法的代码非常的复杂需要一步一步的分析。
- 情况1第一次插入数据
存放数据的Hash表table默认为null数组的数据类型为node<K,V>是一个单向链表。
第一次通过 resize()进行初始化(扩容)
源代码如下,执行按到【?】中的序号进行执行,最后table初始化完后会得到一个容量为16的Node<K,V>[]数组;threshold =12【扩容的阀门】。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//【1】 首先声明一个Node<K,V>[] 类型的变量oldTab,并将table的值初始给它
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 【2】获取(oldCap)的容量oldCap
int oldThr = threshold;// 【3】声明oldThr并初始化oldThr=threshold;(int threshold;默认为0)
int newCap, newThr = 0;// 【4】声明newCap,并初始化newThr= 0
if (oldCap > 0) {// 【5】由于第一次进行插入数据,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; // double threshold
}
else if (oldThr > 0) // 【6】判断oldThr是否大于0,oldThr=0
newCap = oldThr;
else { // 【7】首次初始化
newCap = DEFAULT_INITIAL_CAPACITY;// 【8】newCap =16 ( static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16)
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 【9】newThr = (0.75*DEFAULT_INITIAL_CAPACITY) 【阀门,达到这个值就进行扩容】
}
if (newThr == 0) {// 【10】通过上面的初始化(newThr = 12(16*0.75=12)
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 【11】threshold = newThr;=12
({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //【12】 创建一个Node<K,V>[]类型的newTab数组大小为16
table = newTab;// 【13】作为参数初始化给table=newTab (长度为16的数组数组的数据类型为Node<K,V>)
if (oldTab != null) {// 【14】第一次插入数据,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 { // 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; // 【15】 返回扩容后的信息数组newTab
}
第一次插入数据的完整执行过程如下按到【?】序号执行插入成功返回null
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;// 【1】声明一些局部变量
if ((tab = table) == null || (n = tab.length) == 0) // 【2】table(Node<K,V>[] table)就是存放数据的Hash表
n = (tab = resize()).length;// 【3】Hash表还没有进行初始化(table=null table.length=0),通过resize()进行初始化
if ((p = tab[i = (n - 1) & hash]) == null)// 【4】i通过Hash表的长度与hash做与运算得到数组的索引,然后判断该索引系下是否为null
tab[i] = newNode(hash, key, value, null); // 【5】插入数据
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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;// 【6】modCount进行自增
if (++size > threshold) // 【7】判断size=0(transient int size;)是否大于threshold(12),显然不大于不需要扩容
resize();
afterNodeInsertion(evict);// 【8】afterNodeInsertion方法时一个空方法用于后期扩展用的
return null; // 【9】 返回null
}
map.put(e, PRESENT) == null返回true
- 第二次能够正常插入数据
table不需要进行初始化通过i = (tab.length - 1) & hash 获取索引然后判断该索引下的数据是否为null, 不为null通过tab[i] = newNode(hash, key, value, null);插入数据modCount自增,判断是否扩容最后返回null。
- 第三次如果插入的数据在对应索引上有数据( (p = tab[i = (n - 1) & hash]) != null )
如果插入的数据在table指定索引下有数据存在执行如下代码
执行的过程按到【?】顺序进行执行最后会将table上的value进行覆盖(
Set存放的是key没有任何影响)并返回这个覆盖的oldValue最后判断不为null返回false。
Node<K,V> e; K k; // 【1】声明临时变量
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))// 【2】p=tab[i = (n - 1) & hash]判断当前索引下的hash值是否和用户的相等并且插入的值和数组索引的值是否一致
e = p; 【3】初始化e
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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 【4】判断e是否为null,e=p != null
V oldValue = e.value; //【5】 oldValue = new Object() (Set的Value都是Object()对象)
if (!onlyIfAbsent || oldValue == null)// 【6】 onlyIfAbsent = false
e.value = value; // 【7】 e.value = new Object() (Set的Value都是Object()对象)说明如果相同值会进行覆盖
afterNodeAccess(e); // 【8】空方法
return oldValue; // 【9】 返回oldValue
}
- 第四次如果当前数组索引上有值但是不相等(
hashcode或equals()不相等)
为了确保上面这种情况发生重写hashCode和equals方法
按到以下代码插入数据,进行分析
当插入new User(“java”,16)时由于equals不相同所以会进入到else if中去p instanceof TreeNode就是判断当前索引下的节点是否进行了树化如果是就通过TreeNode的putTreeVal插入数据。
最终会进入到else中进行执行。
代码执行过程如下按到【?】 顺序进行执行最后返回null插入成功
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {// 【1】 判断一下当前数据索引的下一个节点是否为null
p.next = newNode(hash, key, value, null); // 【2】 如果为null那么就插入到next节点上
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 【3】 判断一下当前节点的长度是否大于等于8(8-1=7,因为从0开始的所以长度为8);static final int TREEIFY_THRESHOLD = 8;
treeifyBin(tab, hash); // 如果当前数组的长度大于等于64就进行树化否则当前数组进行扩容;(n = tab.length) < MIN_TREEIFY_CAPACITY); static final int MIN_TREEIFY_CAPACITY = 64;
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { //【5】 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; // 【6】 返回null
}
- 最后汇总
1.HashSet底层是HashMap,第一次添加时table数组扩容到16临界值(threshold)是16加载因子(loadFactor)是0.75=12
2.如果table数组使用到了临界值12,就会扩容到162=32,新的临界值就是32*0.75 =24,依次类推
3.插入数据会通过(tab.length - 1) & hash 计算出索引然后判断当前索引下是否存在数据如果不存在就直接插入如果存在就判断一下当前索引的值和插入的值是否相等(key.equals(k)是否相同)如果相同
就不添加如果不相同就从当前节点往下查找看是否有相同的如果都没有就在节点最后(p.next =null)进行添加如果有就不添加。
4.在Java8中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)并且table的大小>=MIN TREEIFY CAPACITY(默认64),就会进行树化(红黑树)否则仍然采用数组护容机制
2.LinkedHashSet HashSet+LinkedHashMap
对于 LinkedHashSet 而言它继承与 HashSet、又基于 LinkedHashMap 来实现的。LinkedHashSet 底层使用 LinkedHashMap
数据结构:数组+双向链表来保存所有元素它继承与 HashSet其所有的方法操作上又与 HashSet 相同因此 LinkedHashSet 的实现上非常简单只提供了四个构造方法并通过传递一个标识参数调用父类的构造器底层构造一个 LinkedHashMap 来实现在相关操作上与父类 HashSet 的操作相同直接调用父类 HashSet 的方法即可。 (HashSet采用单链表而LinkedHashSet采用双向链表,和HashSet相比LinkedHashSet能够保证存入数据的有序性)
- 继承与 HashSet类
- 有四个构造函数都是通过
map = new LinkedHashMap<>(initialCapacity, loadFactor);初始化map对象( HashMap<E,Object> map)
- 增删改查还是采用HashSet里面的方法(
扩容机制一样)
- 创建的newNode的节点实际上是创建的是一个LinkedhashMap.Entry,通过linkNodeLast()方法来构造双向链表,tail为尾节点head为头结点该双向链表保证了数据的有序性。
- 测试
3.TreeSet二叉树
- TreeSet()是使用二叉树的原理对新 add()的对象按照指定的顺序排序升序、降序每增加一个对象都会进行排序将对象插入的二叉树指定的位置
数据结构:红黑树。- Integer 和 String 对象都可以进行默认的 TreeSet 排序而自定义类的对象是不可以的自己定义的类必须实现 Comparable 接口并且覆写相应的 compareTo()函数才可以正常使用。
- 在覆写 compare()函数时要返回相应的值才能使 TreeSet 按照一定的规则来排序。
- 比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象则分别返回负整数、零或正整数。
- TreeSet的底层实际上是NavigableMap的接口大多数情况下是TreeMap实现类
- TreeSet只使用了Map集合的key,value采用默认值 new Object() (
private static final Object PRESENT = new Object();)
- 增
首次添加数据时,执行过程如下:
第二次添加,执行过程如下:
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 【0】 初始化临时变量
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;// 【1】获取比较器如果没有通过构造函数进行初始化的话为Null
if (cpr != null) {// 表示采用自己定义的比较器进行比较
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {// 表示采用默认比较器进比较(测试方法采用默认构造器)
if (key == null)//【2】 判断当前key是否为null
throw new NullPointerException();
("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;// 【3】没有初始化比较器采用默认比较器
do {
parent = t;// 【4】初始化parent变量,初始化值为父节点(头结点)
cmp = k.compareTo(t.key);// 【5】通过compareTo进行比较
if (cmp < 0) // 【6】获取比较后的结果,<0和左面的进行比较>0和右面的进行比较=0返回t说明值存在不插入
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); // 为相等时进行替换值
} while (t != null);//【7】 直到t=null时停止循环经过上面的循环可以得到插入数据的父节点
}
Entry<K,V> e = new Entry<>(key, value, parent);// 【8】 初始化要插入的节点
if (cmp < 0) // 【9】 将要插入的节点放在指定节点的左面或者右面<0左面,>0右面
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);// 对新加入的树进行调整
size++;
modCount++;
return null;// 【9】 返回Null 插入成功
}
默认比较器采用传入的类型的比较器,下面的比较器采用的是Integer的比较器所以存入的数据的顺序可以通过比较器来决定:
