wordpress评论不准设置网站,网站在哪里设置关键字,注册公司费用大概多少,wordpress驾校模版目录
Java集合#xff08;一#xff09;
集合介绍
单列集合分类
Collection接口
创建Collection实现类对象
常用方法
迭代器
基本使用
迭代器的执行过程
迭代器底层原理
集合中的并发修改异常及原因分析
List接口
ArrayList类
介绍
常用方法
遍历集合
Array…目录
Java集合一
集合介绍
单列集合分类
Collection接口
创建Collection实现类对象
常用方法
迭代器
基本使用
迭代器的执行过程
迭代器底层原理
集合中的并发修改异常及原因分析
List接口
ArrayList类
介绍
常用方法
遍历集合
ArrayList底层源码分析
初始容量
数组扩容
LinkedList类
介绍
常用方法
遍历集合
LinkedList底层源码分析
LinkedList成员分析
LinkedList中add方法源码分析
LinkedList中get方法源码分析
增强for循环 Java集合一
集合介绍
在前面已经使用了一个最基本的数据结构数组但是数组的缺点很明显定长这个缺点导致数组的增删不够方便为了解决这个问题可以使用Java的相关集合
Java集合分为两种
单列集合集合中每一个元素只有一种元素类型多列集合集合中每一个元素包括两种数据类型第一个数据类型对应的元素被称为key第二个数据类型对应的元素被称为value二者组成的共同体被称为键值对
Java集合有以下三个特点
只能存储引用数据类型的数据而不能存储基本数据类型的数据每一种集合长度均是可变的集合中有很多使用的方法便于调用
单列集合分类
在Java中单列集合最大的接口是Collection接口该接口下有两个子接口分别是list接口和set接口 对于list接口来说一共有三个实现类
ArrayList类LinkedList类Vector类现不常用
三个实现类都具有以下特点
元素存储顺序与插入顺序一致集合中元素可重复可以使用索引方式操作
三个实现类中ArrayList类和Vector类底层的数据结构是数组LinkedList类底层的数据结构是不带头双向不循环链表并且只有Vector类是线程安全的类但是Vector类的效率低 对于set接口来说一共有三个实现类
HashSet类LinkedHashSet类TreeSet类
三个实现类都具有以下特点
不可以添加重复的数据即元素唯一不可以使用索引方式操作线程不安全
三个实现类中HashSet类底层数据结构是哈希表LinkedHashSet类底层数据结构是哈希表双向链表TreeSet类底层数据结构是红黑树并且对于HashSet来说其插入的数据在结构中的顺序与插入时的顺序不一定相同对于LinkedHashSet类来说插入的数据在结构中的顺序与插入时的顺序相同对于TreeSet类来说因为红黑树会按照一定比较方式对插入顺序进行排序所以数据在结构中都是在一定规则下有序的
总结如下图所示 Collection接口
创建Collection实现类对象
Collection接口是单列集合的顶级接口创建对象时使用对应的实现类创建但是可以使用Collection接口的引用接收即多态基本格式如下
CollectionE 对象名 new 实现类对象E()
其中 E表示泛型Java中的泛型只可以写引用数据类型所以导致集合只能存储引用数据类型的数据 使用泛型时赋值符号左侧的部分必须写具体类型但是赋值符号右侧的部分可以省略JVM会自动根据左侧泛型的具体类型推导右侧部分
常用方法
注意下面的方法本质使用的还是实现类中重写的方法 boolean add(E e)向集合中插入元素返回值表示插入成功true或者失败false一般情况下可以不用接收boolean addAll(Collection? extends E c)将另一个集合元素添加到当前集合中相当于集合的合并void clear()清除当前集合中所有的元素boolean contains(Object o)查找对应集合中是否含有指定元素存在返回true否则返回falseboolean isEmpty()判断集合是否为空为空返回true否则返回falseboolean remove(Object o)从当前集合中移除指定元素返回值代表删除成功或者失败int size()返回集合中的元素个数Object[] toArray()将集合中的数据存储到数组中
基本使用如下
public class Test {public static void main(String[] args) {CollectionString collection new ArrayList();//boolean add(E e)collection.add(萧炎);collection.add(萧薰儿);collection.add(彩鳞);collection.add(小医仙);collection.add(云韵);collection.add(涛哥);System.out.println(collection);//boolean addAll(Collection? extends E c)CollectionString collection1 new ArrayList();collection1.add(张无忌);collection1.add(小昭);collection1.add(赵敏);collection1.add(周芷若);collection1.addAll(collection);System.out.println(collection1);//void clear()collection1.clear();System.out.println(collection1);//boolean contains(Object o)boolean result01 collection.contains(涛哥);System.out.println(result01 result01);//boolean isEmpty()System.out.println(collection1.isEmpty());//boolean remove(Object o)collection.remove(涛哥);System.out.println(collection);//int size() 返回集合中的元素个数。System.out.println(collection.size());//Object[] toArray()Object[] arr collection.toArray();System.out.println(Arrays.toString(arr));}
}
迭代器
基本使用
当需要遍历一个集合时最常用的就是迭代器在Java中迭代器是IteratorE接口获取当前集合的迭代器可以使用Collection中的方法
IteratorE iterator()
常用的方法有两种
boolean hasNext()判断集合中的下一个元素是否存在E next()获取下一个元素其中E由创建集合时的数据类型决定
基本使用如下
public class Test01 {public static void main(String[] args) {CollectionString list new ArrayList();list.add(a);list.add(b);list.add(c);list.add(d);// 使用迭代器遍历IteratorString iterator list.iterator();while (iterator.hasNext()) {// 存在下一个元素就更新String next iterator.next();System.out.println(next);}}
}
需要注意尽量不要在遍历过程中使用多次next()方法不同情况下可能结果不一样当next()方法没有访问到指定的数据此时就会抛出异常NoSuchElementException
迭代器的执行过程
以前面的代码为例当前size为4
当执行hasNext方法时对应的源码如下
public boolean hasNext() {return cursor ! size;
}int cursor; // 下一个元素的下标
int lastRet 1; // 上一个元素的下标 满足条件进入循环执行next方法对应源码如下
public E next() {// ...int i cursor;if (i size)throw new NoSuchElementException();Object[] elementData ArrayList.this.elementData;if (i elementData.length)throw new ConcurrentModificationException();cursor i 1;return (E) elementData[lastRet i];
}
因为cursor既不大于size也不大于新建数组elementData的长度所以两个分支语句均不执行
因为 ArrayList实现的 Iterator是一个 IteratorE的内部实现类所以访问 ArrayList中的 elementData成员相当于内部类访问外部类的成员而 ArrayList中的 elementData数组存储的是当前集合中的数据因为 ArrayList底层是数组所以直接将对应的 elementData的地址给新数组引用即可实现数组数据共享 接下来cursori1使cursor走到下一个元素的位置因为前面已经判断cursor!size表示一定存在下一个元素所以此处不会出现越界问题接着返回elementData数组中的元素但是因为新数组引用是Object类型所以此处需要进行强制类型转换以确保返回的数据类型与泛型对应的数据类型一致
此处返回的 elementData数组元素下标使用到了赋值符号的返回值赋值符号的返回值为赋值符号左侧变量的值因为取下标需要先计算内部 lastReti表达式所以此处既让 lastRet向后移动又拿到了 lastRet向后移动对应位置的值 所以本过程运行结果如下图 其余情况以此类推直到cursor!size返回false代表已经没有下一个元素循环结束
迭代器底层原理
在获取迭代器时调用到了对应集合的成员方法例如前面ArrayList获取其迭代器对象时使用的代码
IteratorString iterator list.iterator();
对应的源码如下
public class ArrayListE extends AbstractListEimplements ListE, RandomAccess, Cloneable, java.io.Serializable
{// 返回迭代器对象public IteratorE iterator() {return new Itr();}// ...private class Itr implements IteratorE {int cursor; // index of next element to returnint lastRet 1; // index of last element returned; 1 if no suchint expectedModCount modCount;Itr() {}// ...}// ...
}
实际上获取到的迭代器就是CollectionE实现类的ArrayList类中内部实现IteratorE的对象
需要注意并不是所有的集合都是new Itr()例如HashSet的源码
// HashSet中
public IteratorE iterator() {return map.keySet().iterator();
}// HashMap中
public SetK keySet() {SetK ks keySet;if (ks null) {ks new KeySet();keySet ks;}return ks;
}final class KeySet extends AbstractSetK {// ...public final IteratorK iterator() { return new KeyIterator(); }// ...
}
在HashSet中iterator()方法返回的是HashMap中的内部类KeySet中的迭代器
集合中的并发修改异常及原因分析
并发修改异常出现于使用迭代器遍历集合的过程中修改集合中的内容例如下面的代码
以 ArrayList为例其余集合类似 public class Test02 {public static void main(String[] args) {//需求定义一个集合,存储 唐僧,孙悟空,猪八戒,沙僧,遍历集合,如果遍历到猪八戒,往集合中添加一个白龙马ArrayListString list new ArrayList();list.add(唐僧);list.add(孙悟空);list.add(猪八戒);list.add(沙僧);IteratorString iterator list.iterator();while(iterator.hasNext()){String element iterator.next();// 使用迭代器遍历过程中修改集合中的内容if (猪八戒.equals(element)){list.add(白龙马);}}System.out.println(list);}
}报错信息
Exception in thread main java.util.ConcurrentModificationExceptionat java.util.ArrayList$Itr.checkForComodification(ArrayList.java911)at java.util.ArrayList$Itr.next(ArrayList.java861)at com.epsda.advanced.test_Collection.Test02.main(Test02.java24)
查看源码分析出现这个异常的原因
public E next() {checkForComodification();// ...
}// 迭代器内部类
int expectedModCount modCount;final void checkForComodification() {if (modCount ! expectedModCount)throw new ConcurrentModificationException();
}
在执行next方法时第一行先调用checkForComodification()方法该方法用于检测modCount和expectedModCount是否一致其作用是在多线程环境下检测集合是否被其他线程修改过。而在对应的add函数中代码如下
public boolean add(E e) {ensureCapacityInternal(size 1); // Increments modCount!!elementData[size] e;return true;
}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private void ensureExplicitCapacity(int minCapacity) {modCount;// overflowconscious codeif (minCapacity elementData.length 0)grow(minCapacity);
}
如果在使用迭代器遍历时修改集合元素就会因为迭代器对象已经创建完毕而此时的expectedModCount与modCount初始值相等因为每一次添加数据都会导致modCount改变导致此时的modCount和expectedCount不对应从而在checkForComodification()方法中抛出异常具体流程如下 总结不要在使用迭代器遍历集合的同时修改集合中的内容
List接口
根据前面的单列集合图可以看出List接口是Collection接口的子接口常见的实现类一共有三种
ArrayList类LinkedList类Vector类现不常用
ArrayList类
介绍
ArrayList类是List接口的实现类其特点如下
存储顺序与插入顺序相同元素可重复可以使用索引方式操作线程不安全底层数据结构是数组可扩容
常用方法
boolean add(E e)向集合尾部插入元素返回值表示插入成功true或者失败false一般情况下可以不用接收void add(int index, E element)在指定位置添加元素如果指定位置有元素则在该元素前插入元素boolean remove(Object o)从当前集合中移除指定元素返回值代表删除成功或者失败E remove(int index)根据索引删除元素返回被删除的元素E set(int index, E element)修改指定索引的元素返回被修改的元素E set(int index)根据索引获取元素int size()返回集合中的元素个数
基本使用如下
public class Test03 {public static void main(String[] args) {ArrayListString list new ArrayList();//boolean add(E e)list.add(铁胆火车侠);list.add(喜洋洋);list.add(火影忍者);list.add(灌篮高手);list.add(网球王子);System.out.println(list);//void add(int index, E element)list.add(2,猪猪侠);System.out.println(list);//boolean remove(Object o)list.remove(猪猪侠);System.out.println(list);//E remove(int index)String element list.remove(0);System.out.println(element);System.out.println(list);//E set(int index, E element)String element2 list.set(0, 金莲);System.out.println(element2);System.out.println(list);//E get(int index)System.out.println(list.get(0));//int size()System.out.println(list.size());}
}
遍历集合
既可以使用迭代器遍历集合也可以使用for循环下标遍历例如下面的代码
public class Test03 {public static void main(String[] args) {ArrayListString list new ArrayList();list.add(铁胆火车侠);list.add(喜洋洋);list.add(火影忍者);list.add(灌篮高手);list.add(网球王子);// 迭代器遍历集合IteratorString iterator list.iterator();while(iterator.hasNext()) {String next iterator.next();System.out.println(next);}// for循环下标遍历for (int i 0; i list.size(); i) {System.out.println(list.get(i));}}
}
ArrayList底层源码分析
初始容量
实际上ArrayList还有一种构造方法ArrayList(int initialCapacity)根据给定的数值初始化ArrayList的容量
如果使用空参构造则默认情况下ArrayList的容量为10但是需要注意ArrayList在使用无参构造并且之后不添加任何元素时其初始容量依旧是0只有在第一次添加数据时才会开辟容量为10的空间源码如下
// 默认容量为0的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};// ArrayList的数据结构
transient Object[] elementData;
// 无参构造方法开始时直接使用空数组构造
public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
第一次调用add方法时
// 默认容量
private static final int DEFAULT_CAPACITY 10;// add方法
public boolean add(E e) {ensureCapacityInternal(size 1); // Increments modCount!!elementData[size] e;return true;
}// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}// 确保内部数组容量方法
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}// 修改内部数组大小
private void ensureExplicitCapacity(int minCapacity) {modCount;// overflowconscious codeif (minCapacity elementData.length 0)grow(minCapacity);
}private void grow(int minCapacity) {// overflowconscious codeint oldCapacity elementData.length;int newCapacity oldCapacity (oldCapacity 1);if (newCapacity minCapacity 0)newCapacity minCapacity;if (newCapacity MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a winelementData Arrays.copyOf(elementData, newCapacity);
}
因为此时底层数组的容量大小为0所以在calculateCapacity方法中进入分支语句此时判断默认容量大小成员DEFAULT_CAPACITY和minCapacity哪一个大而minCapacity在add方法中是size成员加1的结果此时因为数组长度为0所以size也为0所以minCapacity此时就是1很明显DEFAULT_CAPACITY和minCapacityDEFAULT_CAPACITY会更大所以calculateCapacity方法返回DEFAULT_CAPACITY给ensureExplicitCapacity方法在该方法中的分支语句判断时因为minCapacity为1elementData.length为0所以此时需要扩容进入grow方法传递minCapacity在grow方法中oldCapacity为0newCapacity此时也为0所以newCapacityminCapacity此时是DEFAULT_CAPACITY满足小于0的条件newCapacity就被更新为DEFAULT_CAPACITY的值开辟空间后拷贝原数组的数据即可
综上所述使用ArrayList的无参构造时默认情况下不会开辟一个容量为10的数组只有在第一次添加数据时该数组容量才会变为10
数组扩容
private void grow(int minCapacity) {// overflowconscious codeint oldCapacity elementData.length;int newCapacity oldCapacity (oldCapacity 1);if (newCapacity minCapacity 0)newCapacity minCapacity;if (newCapacity MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a winelementData Arrays.copyOf(elementData, newCapacity);
}public static T T[] copyOf(T[] original, int newLength) {return (T[]) copyOf(original, newLength, original.getClass());
}public static T,U T[] copyOf(U[] original, int newLength, Class? extends T[] newType) {SuppressWarnings(unchecked)T[] copy ((Object)newType (Object)Object[].class)? (T[]) new Object[newLength] (T[]) Array.newInstance(newType.getComponentType(), newLength);System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));return copy;
}
从这个源码可以看出当newCapacity大于minCapacity时两个分支if都不会执行并且扩容大小为原数组大小的1.5倍传递newCapacity和当前数组调用copyOf方法进入该方法后底层调用系统数组拷贝方法arraycopy在拷贝时使用了min方法控制是否要改变数组长度将原数组的数据拷贝到新数组中再改变成员elementData的指向但是不论是否原数组长度小于新长度还是其他情况都会对原数据进行拷贝
需要注意尽管在某些情况下不需要扩容但为了简化代码逻辑和保证数据一致性通常会统一处理即总是创建一个新数组并拷贝原有内容。这样做虽然在某些场景下可能有些许性能开销但在整体上更加安全可靠。 LinkedList类
介绍
LinkedList类是List接口的实现类其特点如下
存储顺序与插入顺序相同元素可重复可以使用索引方式操作线程不安全底层数据结构是不带头双向不循环链表
常用方法
public void addFirst(E e)将指定元素插入此列表的开头public void addLast(E e)将指定元素添加到此列表的结尾public E getFirst()返回此列表的第一个元素public E getLast()返回此列表的最后一个元素public E get(int index)获取索引位置的元素public E removeFirst()移除并返回此列表的第一个元素返回被删除的元素public E removeLast()移除并返回此列表的最后一个元素返回被删除的元素public boolean isEmpty()如果列表没有元素则返回true否则返回false
基本使用如下
public class Test05 {public static void main(String[] args) {LinkedListString linkedList new LinkedList();linkedList.add(吕布);linkedList.add(刘备);linkedList.add(关羽);linkedList.add(张飞);linkedList.add(貂蝉);System.out.println(linkedList);linkedList.addFirst(孙尚香);System.out.println(linkedList);linkedList.addLast(董卓);System.out.println(linkedList);System.out.println(linkedList.getFirst());System.out.println(linkedList.getLast());linkedList.removeFirst();System.out.println(linkedList);linkedList.removeLast();System.out.println(linkedList);}
}
需要注意两个比较特殊的方法
public E pop()删除链表头数据返回被删除的元素public void push(E e)在链表头插入数据
public class Test06 {public static void main(String[] args) {LinkedListString linkedList new LinkedList();linkedList.add(吕布);linkedList.add(刘备);linkedList.add(关羽);linkedList.add(张飞);linkedList.add(貂蝉);linkedList.pop();System.out.println(linkedList);linkedList.push(孙尚香);System.out.println(linkedList);}
}
遍历集合
与ArrayList一样可以使用迭代器也可以使用for循环下标
需要注意默认情况下 LinkedList不支持下标访问因为链表没有下标的概念但是因为 LinkedList提供了类似于下标访问的方法所以可以使用下标 public class Test06 {public static void main(String[] args) {LinkedListString linkedList new LinkedList();linkedList.add(吕布);linkedList.add(刘备);linkedList.add(关羽);linkedList.add(张飞);linkedList.add(貂蝉);// 迭代器遍历IteratorString iterator linkedList.iterator();while (iterator.hasNext()) {String next iterator.next();System.out.println(next);}// for循环下标for (int i 0; i linkedList.size(); i) {System.out.println(linkedList.get(i));}}
}
LinkedList底层源码分析
LinkedList成员分析
对于LinkedList来说
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{transient int size 0;/*** Pointer to first node.* Invariant: (first null last null) ||* (first.prev null first.item ! null)*/transient NodeE first;/*** Pointer to last node.* Invariant: (first null last null) ||* (last.next null last.item ! null)*/transient NodeE last;// ...
}
对于其中的NodeE类型LinkedList的内部类来说
private static class NodeE {E item;NodeE next;NodeE prev;Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}
下图是一种情况对于每一个成员的作用进行解释 LinkedList中add方法源码分析
public boolean add(E e) {linkLast(e);return true;
}void linkLast(E e) {final NodeE l last;final NodeE newNode new Node(l, e, null);last newNode;if (l null)first newNode;elsel.next newNode;size;modCount;
}
调用add方法相当于调用linkLast方法当last节点为空节点时说明当前不存在任何一个节点此时将头结点指向新插入的节点否则让最后一个节点的next引用新插入的节点
LinkedList中get方法源码分析
public E get(int index) {checkElementIndex(index);return node(index).item;
}NodeE node(int index) {// assert isElementIndex(index);if (index (size 1)) {NodeE x first;for (int i 0; i index; i)x x.next;return x;} else {NodeE x last;for (int i size - 1; i index; i--)x x.prev;return x;}
}
对于LinkedList中的get方法采用了一种二分的思想但不完全是二分查找算法的思想其基本思想是将链表的长度切一半如果查找的下标小于链表大小的一半说明需要在前一半中顺序遍历查找否则在后一半中顺序遍历查找
增强for循环
增强for循环对于集合来说本质是使用到了迭代器而对于数组来说本质是数组的下标遍历
使用格式如下
for(集合/数组元素的类型 存储元素的变量名 : 集合/数组名) {// 遍历操作
}
基本使用如下
public class Test07 {public static void main(String[] args) {ArrayListString list new ArrayList();list.add(张三);list.add(李四);list.add(王五);list.add(赵六);for (String s : list) {System.out.println(s);}System.out.println();int[] arr {1,2,3,4,5};for (int i : arr) {System.out.println(i);}}
}
反编译查看底层
