java基础
集合承继包含图
Collection vs Collections
首先,"Collection" and "Collections"是两个不同的概念,从下面的继承关系图中我们可以看到,"Collection"是一个基础接口类,而"Collections"是一个静态的类,它提供了一些静态方法来操作某些集合类型。
image
集合的类继承关系图
下图说明了集合的继承关系。
image
Map的继承关系图
image
ArrayList如何实现排序?
// 排序方法 //ArrayList.class public void sort(Comparator<? super E> c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } //Array.class 实现比较接口 public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) { // 如果没有实现比较方法 if (c == null) { sort(a, fromIndex, toIndex); } else { rangeCheck(a.length, fromIndex, toIndex); if (Arrays.LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex, c); else TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0); } }//Array.class 未实现比较接口 public static void sort(Object[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); //经查资料,这是个传统的归并排序,需要通过设置系统属性后,才能进行调用 // System.setProperty("java.util.Arrays.useLegacyMergeSort", "true"); if (Arrays.LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex); else ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0); }
底层是一种传统归并排序。
Collection 和 Collections的区别
首先,"Collection" and "Collections"是两个不同的概念,从下面的继承关系图中我们可以看到,"Collection"是一个基础接口类,而"Collections"是一个静态的类,它提供了一些静态方法来操作某些集合类型。
image
ArrayList 和 Vector的区别
ArrayList,Vector主要区别为以下几点:
(1):Vector是线程安全的,源码中有很多的synchronized可以看出,而ArrayList不是。导致Vector效率无法和ArrayList相比;
(2):ArrayList和Vector都采用线性连续存储空间,当存储空间不足的时候,ArrayList默认增加为原来的50%,Vector默认增加为原来的一倍;
(3):Vector可以设置capacityIncrement,而ArrayList不可以,从字面理解就是capacity容量,Increment增加,容量增长的参数。
ArrayList的底层实现和扩容情况
构造ArrayList的时候,默认初始化容量为10,保存容器为 Object[] elementData。
向集合添加元素的时候,调用add方法,比如list.add("a");
add方法做的操作是:elementData[size++] = e; 然后元素就被存放进了elementData。
初始化容量为10,当我们存第十一个元素的时候,会怎么做呢?看ArrayList类的部分源码:
public class ArrayList<E> extends AbstractList<E> implements List<E> { private transient Object[] elementData; public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } //Constructs an empty list with an initial capacity of ten. public ArrayList() { this(10); } public boolean add(E e) { ensureCapacity(size + 1); // 扩充长度 elementData[size++] = e; // 先赋值,后进行size++。所以是从[0]开始存。 return true; } public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; // 旧集合长度 if (minCapacity > oldCapacity) { Object oldData[] = elementData; // 旧集合数据 int newCapacity = (oldCapacity * 3)/2 + 1; // 计算新长度,旧长度的1.5倍+1 if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); // 这就是传说中的可变集合。用新长度复制原数组。 } } public E get(int index) { RangeCheck(index); return (E) elementData[index]; } }
add方法中先调用ensureCapacity方法对原数组长度进行扩充,扩充方式为,通过Arrays类的copyOf方法对原数组进行拷贝,长度为原数组的1.5倍+1。
然后把扩容后的新数组实例对象地址赋值给elementData引用类型变量。扩容完毕。
经测试,如果要存100万数据,需要扩容28次,数据量越大,扩容次数越多,每一次的扩容代表着创建新数组对象,复制原有数据。
ArrayList 和 LinkedList的区别
ArrayList和Vector使用了数组的实现,可以认为ArrayList或者Vector封装了对内部数组的操作,比如向数组中添加,删除,插入新的元素或者数据的扩展和重定向。
LinkedList使用了循环双向链表数据结构。与基于数组ArrayList相比,这是两种截然不同的实现技术,这也决定了它们将适用于完全不同的工作场景。
LinkedList链表由一系列表项连接而成。一个表项总是包含3个部分:元素内容,前驱表和后驱表
(1)增加元素到列表尾端
ArrayList中add()方法的性能决定于ensureCapacity()方法。 扩容函数。
LinkeList由于使用了链表的结构,因此不需要维护容量的大小
(2)增加元素到列表任意位置
由于实现的不同,ArrayList和LinkedList在这个方法上存在一定的性能差异,由于ArrayList是基于数组实现的,而数组是一块连续的内存空间,如果在数组的任意位置插入元素,必然导致在该位置后的所有元素需要重新排列,因此,其效率相对会比较低。
(3)删除任意位置元素
对ArrayList来说,remove()方法和add()方法是雷同的。在任意位置移除元素后,都要进行数组的重组。
(4)容量参数
容量参数是ArrayList和Vector等基于数组的List的特有性能参数。它表示初始化的数组大小。当ArrayList所存储的元素数量超过其已有大小时。它便会进行扩容,数组的扩容会导致整个数组进行一次内存复制。因此合理的数组大小有助于减少数组扩容的次数,从而提高系统性能。
ArrayList提供了一个可以制定初始数组大小的构造函数 :
public ArrayList(int initialCapacity)
(5)遍历列表
最简便的ForEach循环并没有很好的性能表现,综合性能不如普通的迭代器,而是用for循环通过随机访问遍历列表时,ArrayList表项很好,但是LinkedList的表现却无法让人接受,甚至没有办法等待程序的结束。这是因为对LinkedList进行随机访问时,总会进行一次列表的遍历操作。性能非常差,应避免使用。
Array和ArrayList的区别?什么时候更适合Array
(1)ArrayList是Array的复杂版本
ArrayList内部封装了一个Object类型的数组,从一般的意义来说,它和数组没有本质的差别,甚至于ArrayList的许多方法,如Index、IndexOf、Contains、Sort等都是在内部数组的基础上直接调用Array的对应方法。
(2)存储的数据类型
ArrayList可以存储异构对象,而Array只能存储相同数据类型的数据。
(3)长度的可变
Array的长度实际上是不可变的,二维变长数组实际上的长度也是固定的,可变的只是其中元素的长度。而ArrayList的长度既可以指定(即使指定了长度,也会自动2倍扩容)也可以不指定,是变长的。
(4)存取和增删元素
对于一般的引用类型来说,这部分的影响不是很大,但是对于值类型来说,往ArrayList里面添加和修改元素,都会引起装箱和拆箱的操作,频繁的操作可能会影响一部分效率。另外,ArrayList是动态数组,它不包括通过Key或者Value快速访问的算法,所以实际上调用IndexOf、Contains等方法是执行的简单的循环来查找元素,所以频繁的调用此类方法并不比你自己写循环并且稍作优化来的快,如果有这方面的要求,建议使用Hashtable或SortedList等键值对的集合。
适用场景:
如果想要保存一些在整个程序运行期间都会存在而且不变的数据,我们可以将它们放进一个全局数组里,但是如果我们单纯只是想要以数组的形式保存数据,而不对数据进行增加等操作,只是方便我们进行查找的话,那么,我们就选择ArrayList。
去掉Vector中一个反复的元素
1. Vector.contains()
通过Vector.contains()方法判断是否包含该元素,如果没有包含就添加到新的集合当中,用于数据较小的情况
2. HashSet()
使用HashSet来解决这个问题,通过hashcode的过滤解决问题。
HashMap HasnTable concurrentHashMap原理、区别
HashTable
底层数组+链表实现,无论key还是value都不能为null,线程安全,实现线程安全的方式是在修改数据时锁住整个HashTable,效率低,ConcurrentHashMap做了相关优化
初始size为11,扩容:newsize = olesize*2+1
计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length
HashMap
底层数组+链表(红黑树)实现,可以存储null键和null值,线程不安全
初始size为16,扩容:newsize = oldsize*2,size一定为2的n次幂
扩容针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入
插入元素后才判断该不该扩容,有可能无效扩容(插入后如果扩容,如果没有再次插入,就会产生无效扩容)
当Map中元素总数超过Entry数组的75%,触发扩容操作,为了减少链表长度,元素分配更均匀
计算index方法:index = hash & (tab.length – 1)
ConcurrentHashMap
底层采用分段的数组+链表实现,线程安全
通过把整个Map分为N个Segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry的value变量是 volatile的,也能保证读取到最新的值。)
Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术
有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁
扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容
HashMap的初始值还要考虑加载因子:
哈希冲突:若干Key的哈希值按数组大小取模后,如果落在同一个数组下标上,将组成一条Entry链,对Key的查找需要遍历Entry链上的每个元素执行equals()比较。
加载因子:为了降低哈希冲突的概率,默认当HashMap中的键值对达到数组大小的75%时,即会触发扩容。因此,如果预估容量是100,即需要设定100/0.75=134的数组大小。
空间换时间:如果希望加快Key查找的时间,还可以进一步降低加载因子,加大初始大小,以降低哈希冲突的概率。
Hashtable与HashMap另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。
List Map Set三个接口,存取数据时各有什么特点
List与Set都是单列元素的集合,它们有一个功共同的父接口Collection。
Set里面不允许有重复的元素,
存元素:add方法有一个boolean的返回值,当集合中没有某个元素,此时add方法可成功加入该元素时,则返回true;当集合含有与某个元素equals相等的元素时,此时add方法无法加入该元素,返回结果为false。
取元素:没法说取第几个,只能以Iterator接口取得所有的元素,再逐一遍历各个元素。
List表示有先后顺序的集合,
存元素:多次调用add(Object)方法时,每次加入的对象按先来后到的顺序排序,也可以插队,即调用add(int index,Object)方法,就可以指定当前对象在集合中的存放位置。
取元素:
方法1:Iterator接口取得所有,逐一遍历各个元素
方法2:调用get(index i)来明确说明取第几个。
Map是双列的集合,
存放用put方法:put(obj key,obj value),每次存储时,要存储一对key/value,不能存储重复的key,这个重复的规则也是按equals比较相等。
取元素:用get(Object key)方法根据key获得相应的value。也可以获得所有的key的集合,还可以获得所有的value的集合,还可以获得key和value组合成的Map.Entry对象的集合。
List以特定次序来持有元素,可有重复元素。Set 无法拥有重复元素,内部排序。Map 保存key-value值,value可多值。
介绍一下TreeSet
Java中的TreeSet是Set的一个子类,TreeSet集合是用来对象元素进行排序的,同样他也可以保证元素的唯一。
TreeSet 是一个有序的集合,它的作用是提供有序的Set集合。它继承于AbstractSet抽象类,实现了NavigableSet<E>, Cloneable, java.io.Serializable接口。
TreeSet 继承于AbstractSet,所以它是一个Set集合,具有Set的属性和方法。
TreeSet 实现了NavigableSet接口,意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。
TreeSet 实现了Cloneable接口,意味着它能被克隆。
TreeSet 实现了java.io.Serializable接口,意味着它支持序列化。
TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式:自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
TreeSet为基本操作(add、remove 和 contains)提供受保证的 log(n) 时间开销。
另外,TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。
image
(1) TreeSet继承于AbstractSet,并且实现了NavigableSet接口。
(2) TreeSet的本质是一个"有序的,并且没有重复元素"的集合,它是通过TreeMap实现的。TreeSet中含有一个"NavigableMap类型的成员变量"m,而m实际上是"TreeMap的实例"。
TreeSet不支持快速随机遍历,只能通过迭代器进行遍历!
Java集合中那些类是线程安全的
在集合框架中,有些类是线程安全的,这些都是jdk1.1中的出现的。在jdk1.2之后,就出现许许多多非线程安全的类。 下面是这些线程安全的同步的类:
vector:就比arraylist多了个同步化机制(线程安全),因为效率较低,现在已经不太建议使用。在web应用中,特别是前台页面,往往效率(页面响应速度)是优先考虑的。
statck:堆栈类,先进后出
hashtable:就比hashmap多了个线程安全
enumeration:枚举,相当于迭代器
除了这些之外,其他的都是非线程安全的类和接口。
线程安全的类其方法是同步的,每次只能一个访问。是重量级对象,效率较低。
BlockingQueue是什么?如何用wait和notify实现blockingqueue
BlockingQueue是阻塞队列。
阻塞队列与普通队列的区别在于,当队列是空的时,从队列中获取元素的操作将会被阻塞,或者当队列是满时,往队列里添加元素的操作会被阻塞。试图从空的阻塞队列中获取元素的线程将会被阻塞,直到其他的线程往空的队列插入新的元素。
public class BlockingQueueDemo { //定义两把锁,只是简单的锁 private Object full = new Object(); private Object empty = new Object(); private int[] array; private int head; private int last; private int size; public BlockingQueueDemo(int maxSize) { this.head = 0; this.last = 0; array = new int[maxSize]; } public void put(int e) throws InterruptedException { synchronized(full){ //满锁 while (size == array.length) {//没有更多空间,需要阻塞 full.wait(); } } if (last < array.length) { array[last] = e; last++; } else { array[0] = e; last = 1; } size++; System.out.println(size+" :size大小,last: "+last+" :e: "+e); //放入数据以后,就可以唤醒obj2对象的锁 synchronized(empty){ //空锁 empty.notify();//达到了唤醒poll方法的条件 } } public int pool() throws InterruptedException { synchronized(empty){ while (size == 0) {//没有数据,阻塞 empty.wait(); } } int returnValue = 0; //队列中有数据,且head小于array的长度 returnValue = array[head]; array[head] = -1; System.out.println(returnValue + " 弹出的"+"head:"+ head); if (head < array.length) {//弹出head下标的数据 head++; } else { head = 0; } size--; //拿走数据后,唤醒full对象锁 synchronized(full){ full.notify(); } return returnValue; } public String toString(){ for (int i = 0; i < array.length; i++) { System.out.println(array[i]); } return ""; } public static void main(String[] args) throws InterruptedException { BlockingQueueDemo bq = new BlockingQueueDemo(5); bq.put(10); bq.put(20); bq.put(30); bq.put(40); bq.put(50); System.out.println(); bq.pool(); bq.pool(); bq.pool(); bq.pool(); System.out.println(); bq.toString(); System.out.println(); bq.put(100); bq.put(200); bq.put(300); bq.put(400); System.out.println(); bq.toString(); } }
作者:onlyHalfSoul
链接:https://www.jianshu.com/p/1115438b9014