目录
二、Collection 和 Collections 有什么区别?
八、ArrayList 和 LinkedList 的区别是什么?
十、在 Queue 中 poll()和 remove()有什么区别?
十四、Iterator 和 ListIterator 有什么区别?
十七、Java8开始ConcurrentHashMap,为什么舍弃分段锁?
十八、ConcurrentHashMap(JDK1.8)为什么要使用synchronized而不是如ReentranLock这样的可重入锁?
十九、concurrentHashMap和HashTable有什么区别
二十一、除了 ReetrantLock,你还接触过 JUC 中的哪些并发工具?
二十二、请谈谈 ReadWriteLock 和 StampedLock
(1)set
HashSet、TreeSet
(2)list
ArrayList、LinkedList、Vector
2、Map
HashMap、HashTable、TreeMap
1、Collection是最基本的集合接口,Collection派生了两个子接口list和set,分别定义了两种不同的存储方式。
2、Collections是一个包装类,它包含各种有关集合操作的静态方法(对集合的搜索、排序、线程安全化等)。
此类不能实例化,就像一个工具类,服务于Collection框架。
1、List简介
实际上有两种List:一种是基本的ArrayList,其优点在于随机访问元素,另一种是LinkedList,它并不是为快速随机访问设计的,而是快速的插入或删除。
ArrayList:由数组实现的List。允许对元素进行快速随机访问,但是向List中间插入与移除元素的速度很慢。
LinkedList :对顺序访问进行了优化,向List中间插入与删除的开销并不大。随机访问则相对较慢。
还具有下列方 法:addFirst(), addLast(), getFirst(), getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用。
2、Set简介
Set具有与Collection完全一样的接口,因此没有任何额外的功能。实际上Set就是Collection,只是行为不同。这是继承与多态思想的典型应用:表现不同的行为。Set不保存重复的元素(至于如何判断元素相同则较为负责)
Set : 存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。
HashSet:为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。
TreeSet: 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。
3、list与Set区别
(1)List,Set都是继承自Collection接口
(2)List特点:元素有放入顺序,元素可重复 ,Set特点:元素无放入顺序,元素不可重复,重复元素会覆盖掉,(元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的,加入Set 的Object必须定义equals()方法 ,另外list支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。)
(3)Set和List对比:
1、简介
HashMap基于map接口,元素以键值对方式存储,允许有null值,HashMap是线程不安全的。
2、基本属性
3、HashMap的存储结构
JDK1.7中采用数组+链表的存储形式。
HashMap采取Entry数组来存储key-value,每一个键值对组成了一个Entry实体,Entry类时机上是一个单向的链表结构,它具有next指针,指向下一个Entry实体,以此来解决Hash冲突的问题。
HashMap实现一个内部类Entry,重要的属性有hash、key、value、next。
JDK1.8中采用数据+链表+红黑树的存储形式。当链表长度超过阈值(8)时,将链表转换为红黑树。在性能上进一步得到提升。
1、HashSet
HashSet是set接口的实现类,set下面最主要的实现类就是HashSet(也就是用的最多的),此外还有LinkedHashSet和TreeSet。
HashSet是无序的、不可重复的。通过对象的hashCode和equals方法保证对象的唯一性。
HashSet内部的存储结构是哈希表,是线程不安全的。
2、TreeSet
TreeSet对元素进行排序的方式:
元素自身具备比较功能,需要实现Comparable接口,并覆盖compareTo方法。
元素自身不具备比较功能,需要实现Comparator接口,并覆盖compare方法。
3、LinkedHashSet
LinkedHashSet是一种有序的Set集合,即其元素的存入和输出的顺序是相同的。
HashSet实际上是一个HashMap实例,数据存储结构都是数组+链表。
HashSet是基于HashMap实现的,HashSet中的元素都存放在HashMap的key上面,而value都是一个统一的对象PRESENT。
private static final Object PRESENT = new Object();
HashSet中add方法调用的是底层HashMap中的put方法,put方法要判断插入值是否存在,而HashSet的add方法,首先判断元素是否存在,如果存在则插入,如果不存在则不插入,这样就保证了HashSet中不存在重复值。
通过对象的hashCode和equals方法保证对象的唯一性。
ArrayList是动态数组的数据结构实现,查找和遍历的效率较高;
LinkedList 是双向链表的数据结构,增加和删除的效率较高;
String[] arr = {"zs","ls","ww"};
List<String> list = Arrays.asList(arr);
System.out.println(list);
ArrayList<String> list1 = new ArrayList<String>();
list1.add("张三");
list1.add("李四");
list1.add("王五");
String[] arr1 = list1.toArray(new String[list1.size()]);
System.out.println(arr1);
for(int i = 0; i < arr1.length; i++){
System.out.println(arr1[i]);
}
1、offer()和add()区别:
增加新项时,如果队列满了,add会抛出异常,offer返回false。
2、poll()和remove()区别:
poll()和remove()都是从队列中删除第一个元素,remove抛出异常,poll返回null。
3、peek()和element()区别:
peek()和element()用于查询队列头部元素,为空时element抛出异常,peek返回null。
为了方便的处理集合中的元素,Java中出现了一个对象,该对象提供了一些方法专门处理集合中的元素.例如删除和获取集合中的元素.该对象就叫做迭代器(Iterator)。
Iterator 接口源码中的方法:
1、ListIterator 继承 Iterator
2、ListIterator 比 Iterator多方法
3、使用范围不同,Iterator可以迭代所有集合;ListIterator 只能用于List及其子类
我们很容易想到用final关键字进行修饰,我们都知道
final关键字可以修饰类,方法,成员变量,final修饰的类不能被继承,final修饰的方法不能被重写,final修饰的成员变量必须初始化值,如果这个成员变量是基本数据类型,表示这个变量的值是不可改变的,如果说这个成员变量是引用类型,则表示这个引用的地址值是不能改变的,但是这个引用所指向的对象里面的内容还是可以改变的。
那么,我们怎么确保一个集合不能被修改?首先我们要清楚,集合(map,set,list…)都是引用类型,所以我们如果用final修饰的话,集合里面的内容还是可以修改的。
我们可以做一个实验:
可以看到:我们用final关键字定义了一个map集合,这时候我们往集合里面传值,第一个键值对1,1;我们再修改后,可以把键为1的值改为100,说明我们是可以修改map集合的值的。
那我们应该怎么做才能确保集合不被修改呢?
我们可以采用Collections包下的unmodifiableMap方法,通过这个方法返回的map,是不可以修改的。他会报 java.lang.UnsupportedOperationException错。
同理:Collections包也提供了对list和set集合的方法。
Collections.unmodifiableList(List)
Collections.unmodifiableSet(Set)
1、队列先进先出,栈先进后出。
2、遍历数据速度不同。
栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来,而且在遍历数据的时候还得为数据开辟临时空间,保持数据在遍历前的一致性;
队列则不同,他基于地址指针进行遍历,而且可以从头或尾部开始遍历,但不能同时遍历,无需开辟临时空间,因为在遍历的过程中不影像数据结构,速度要快的多。
ConcurrentHashMap的原理是引用了内部的 Segment (ReentrantLock ) 分段锁,保证在操作不同段 map 的时候, 可以并发执行, 操作同段 map 的时候,进行锁的竞争和等待。从而达到线程安全, 且效率大于 synchronized。
但是在 Java8 之后, JDK 却弃用了这个策略,重新使用了synchronized+CAS。
弃用原因
通过 JDK 的源码和官方文档看来, 他们认为的弃用分段锁的原因由以下几点:
新的同步方案
既然弃用了分段锁, 那么一定由新的线程安全方案, 我们来看看源码是怎么解决线程安全的呢?(源码保留了segment 代码, 但并没有使用)。
我想从下面几个角度讨论这个问题:
1、锁的粒度
首先锁的粒度并没有变粗,甚至变得更细了。每当扩容一次,ConcurrentHashMap的并发度就扩大一倍。
2、Hash冲突
JDK1.7中,ConcurrentHashMap从过二次hash的方式(Segment -> HashEntry)能够快速的找到查找的元素。在1.8中通过链表加红黑树的形式弥补了put、get时的性能差距。
扩容
JDK1.8中,在ConcurrentHashmap进行扩容时,其他线程可以通过检测数组中的节点决定是否对这条链表(红黑树)进行扩容,减小了扩容的粒度,提高了扩容的效率。
下面是我对面试中的那个问题的一下看法。
为什么是synchronized,而不是ReentranLock
1、减少内存开销
假设使用可重入锁来获得同步支持,那么每个节点都需要通过继承AQS来获得同步支持。但并不是每个节点都需要获得同步支持的,只有链表的头节点(红黑树的根节点)需要同步,这无疑带来了巨大内存浪费。
2、获得JVM的支持
可重入锁毕竟是API这个级别的,后续的性能优化空间很小。
synchronized则是JVM直接支持的,JVM能够在运行时作出相应的优化措施:锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。
concurrentHashMap融合了hashmap和hashtable的优势,hashmap是不同步的,但是单线程情况下效率高,hashtable是同步的同步情况下保证程序执行的正确性。
但hashtable每次同步执行的时候都要锁住整个结构,如下图:
concurrentHashMap锁的方式是细粒度的。concurrentHashMap将hash分为16个桶(默认值),诸如get、put、remove等常用操作只锁住当前需要用到的桶。
concurrentHashMap的读取并发,因为读取的大多数时候都没有锁定,所以读取操作几乎是完全的并发操作,只是在求size时才需要锁定整个hash。
而且在迭代时,concurrentHashMap使用了不同于传统集合的快速失败迭代器的另一种迭代方式,弱一致迭代器。在这种方式中,当iterator被创建后集合再发生改变就不会抛出ConcurrentModificationException,取而代之的是在改变时new新的数据而不是影响原来的数据,iterator完成后再讲头指针替代为新的数据,这样iterator时使用的是原来的数据。
1、先了解一下HashCode
Java中的集合有两类,一类是List,一类是Set。
List:元素有序,可以重复;
Set:元素无序,不可重复;
要想保证元素的不重复,拿什么来判断呢?这就是Object.equals方法了。如果元素有很多,增加一个元素,就要判断n次吗?
显然不现实,于是,Java采用了哈希表的原理。哈希算法也称为散列算法,是将数据依特定算法直接指定到一根地址上,初学者可以简单的理解为,HashCode方法返回的就是对象存储的物理位置(实际上并不是)。
这样一来,当集合添加新的元素时,先调用这个元素的hashcode()方法,就一下子能定位到他应该放置的物理位置上。如果这个位置上没有元素,他就可以直接存储在这个位置上,不用再进行任何比较了。如果这个位置上有元素,就调用它的equals方法与新元素进行比较,想同的话就不存了,不相同就散列其它的地址。所以这里存在一个冲突解决的问题。这样一来实际上调用equals方法的次数就大大降低了,几乎只需要一两次。
简而言之,在集合查找时,hashcode能大大降低对象比较次数,提高查找效率。
Java对象的equals方法和hashCode方法时这样规定的:
相等的对象就必须具有相等的hashcode。
如果两个Java对象A和B,A和B不相等,但是A和B的哈希码相等,将A和B都存入HashMap时会发生哈希冲突,也就是A和B存放在HashMap内部数组的位置索引相同,这时HashMap会在该位置建立一个链接表,将A和B串起来放在该位置,显然,该情况不违反HashMap的使用规则,是允许的。当然,哈希冲突越少越好,尽量采用好的哈希算法避免哈希冲突。
equals()相等的两个对象,hashcode()一定相等;equals()不相等的两个对象,却并不能证明他们的hashcode()不相等。
2、HashMap和HashSet的区别
juc下常用的五个高并发工具:
1、ReadWriteLock
ReadWriteLock 可以实现多个读锁同时进行,但是读与写和写于写互斥,只能有一个写锁线程在进行。
2、StampedLock
StampedLock是Jdk在1.8提供的一种读写锁,相比较ReentrantReadWriteLock性能更好,因为ReentrantReadWriteLock在读写之间是互斥的,使用的是一种悲观策略,在读线程特别多的情况下,会造成写线程处于饥饿状态,虽然可以在初始化的时候设置为true指定为公平,但是吞吐量又下去了,而StampedLock是提供了一种乐观策略,更好的实现读写分离,并且吞吐量不会下降。
StampedLock包括三种锁:
(1)写锁writeLock:
writeLock是一个独占锁写锁,当一个线程获得该锁后,其他请求读锁或者写锁的线程阻塞, 获取成功后,会返回一个stamp(凭据)变量来表示该锁的版本,在释放锁时调用unlockWrite方法传递stamp参数。提供了非阻塞式获取锁tryWriteLock。
(2)悲观读锁readLock:
readLock是一个共享读锁,在没有线程获取写锁情况下,多个线程可以获取该锁。如果有写锁获取,那么其他线程请求读锁会被阻塞。悲观读锁会认为其他线程可能要对自己操作的数据进行修改,所以需要先对数据进行加锁,这是在读少写多的情况下考虑的。请求该锁成功后会返回一个stamp值,在释放锁时调用unlockRead方法传递stamp参数。提供了非阻塞式获取锁方法tryWriteLock。
(3)乐观读锁tryOptimisticRead:
tryOptimisticRead相对比悲观读锁,在操作数据前并没有通过CAS设置锁的状态,如果没有线程获取写锁,则返回一个非0的stamp变量,获取该stamp后在操作数据前还需要调用validate方法来判断期间是否有线程获取了写锁,如果是返回值为0则有线程获取写锁,如果不是0则可以使用stamp变量的锁来操作数据。由于tryOptimisticRead并没有修改锁状态,所以不需要释放锁。这是读多写少的情况下考虑的,不涉及CAS操作,所以效率较高,在保证数据一致性上需要复制一份要操作的变量到方法栈中,并且在操作数据时可能其他写线程已经修改了数据,而我们操作的是方法栈里面的数据,也就是一个快照,所以最多返回的不是最新的数据,但是一致性得到了保证。
往期精彩内容: