川制作官方网站,企业网站制作设计,在线印章生成器,南海佛山网站建设文章目录【背景】CollectionsListArrayList优势操作劣势操作LinkedList优势劣势最基本的两种检索集合中的所有对象的方法#xff1a;CopyOnWriteArrayList补充说明StackMapMap 的常用方法#xff1a;HashMapLinkedHashMapTreeMapConcurrentHashMapConcurrentSkipListMap补充说…
文章目录【背景】CollectionsListArrayList优势操作劣势操作LinkedList优势劣势最基本的两种检索集合中的所有对象的方法CopyOnWriteArrayList补充说明StackMapMap 的常用方法HashMapLinkedHashMapTreeMapConcurrentHashMapConcurrentSkipListMap补充说明关于nullSetSet接口主要实现了两个实现类补充说明Queue注意LinkedListArrayDequePriorityQueueConcurrentLinkedQueue/ConcurrentLinkedDequePriorityBlockingQueueDelayQueueArrayBlockingQueueLinkedBlockingQueue/LinkedBlockingDequeSynchronousQueue补充说明【背景】
在尽可能短的篇幅里将所有集合与并发集合的特征实现方式性能捋一遍。适合所有”精通Java”其实还不那么自信的人阅读。 Collections
Set 和List 都继承了Conllection,Map没有 Collection接口的方法
boolean add(Object o) :向集合中加入一个对象的引用void clear() :删除集合中所有的对象即不再持有这些对象的引用boolean isEmpty() :判断集合是否为空boolean contains(Object o): 判断集合中是否持有特定对象的引用Iterartor iterator() : 返回一个Iterator对象可以用来遍历集合中的元素boolean remove(Object o):从集合中删除一个对象的引用int size() :返回集合中元素的数目Object[] toArray() :返回一个数组该数组中包括集合中的所有元素关于Iterator() 和toArray() 方法都用于集合的所有的元素前者返回一个Iterator对象后者返回一个包含集合中所有元素的数组。 Iterator接口声明了如下方法:hasNext(): 判断集合中元素是否遍历完毕如果没有就返回truenext() :返回下一个元素remove():从集合中删除上一个有next()方法返回的元素。 Set 的 add()方法是如何判断对象是否已经存放在集合中 boolean isExistsfalse;Iterator iteratorset.iterator();while(it.hasNext()) {String oldStrit.next();if(newStr.equals(oldStr)){isExiststrue;}List
List的特征是其元素以线性方式存储,集合中可以存放重复对象。
ArrayList
以数组实现。节约空间但数组有容量限制。超出限制时会增加50%容量默认第一次插入元素时创建大小为10的数组。
优势操作
get(i)/set(i,e) 访问add(e) 末尾插入
劣势操作
System.arraycopy()来移动部分受影响的元素性能变差
add–add(i,e) 按下标插入add(i,e), remove(i), remove(e) 删除元素
LinkedList
以双向链表实现,链表无容量限制双向链表本身使用了更多空间需要额外的链表指针操作
优势
在链表两头的操作能省掉指针的移动
add()addFirst()removeLast()iterator()上的remove()
劣势
按下标访问元素–get(i)/set(i,e) 要遍历链表将指针移动到位(如果i数组大小的一半会从末尾移起)插入、删除元素时修改前后节点的指针即可仍要遍历部分链表的指针才能移动到下标所指的位置
最基本的两种检索集合中的所有对象的方法
1: 用for循环和get()方法for(int i0; ilist.size();i){System.out.println(list.get(i));}2: 使用 迭代器Iterator:Iterator itlist.iterator();while(it.hashNext){System.out.println(it.next);}CopyOnWriteArrayList
支持读多写少的并发情况 -增加了addIfAbsent(e)方法会遍历数组来检查元素是否已存在性能可想像的不太好如果更新频率较高或数组较大时使用Collections.synchronizedList(list)对所有操作用同一把锁来保证线程安全更好
补充说明
按值返回下标–contains(e), indexOf(e), remove(e) 都需遍历所有元素进行比较性能可想像的不太好没有按元素值排序的SortedList在线程安全类中也没有无锁算法的ConcurrentLinkedList凑合着用Set与Queue中的等价类时会缺少一些List特有的方法
Stack
Stack 的常用方法
push( num) 入栈
pop() 栈顶元素出栈
empty() 判定栈是否为空
peek() 获取栈顶元素
search(num) 判端元素num是否在栈中如果在返回1不在返回-1。 注意pop()和peek()的区别。pop()会弹出栈顶元素并返回栈顶的值peek()只是获取栈顶的值但是并不会把元素从栈顶弹出来 Map
Map 是一种把键对象和值对象映射的集合它的每一个元素都包含一对键对象和值对象,键对象不允许重复。Map没有继承于Collection接口从Map集合中检索元素时只要给出键对象就会返回对应的值对象。
Map 的常用方法 1 添加删除操作Object put(Object key, Object value): 向集合中加入元素Object remove(Object key): 删除与KEY相关的元素void putAll(Map t): 将来自特定映像的所有元素添加给该映像void clear(): 从映像中删除所有映射2 查询操作Object get(Object key): 获得与关键字key相关的值HashMap
以Entry[]数组实现的哈希桶数组用Key的哈希值取模桶数组的大小可得到数组下标插入元素时如果两条Key落在同一个桶(如哈希值1和17取模16后都属于第一个哈希桶)。Entry用一个next属性实现多个Entry以单向链表存放后入桶的Entry将next指向桶当前的Entry查找key时(如哈希值为17的)先定位到第一个哈希桶然后以链表遍历桶里所有元素逐个比较其key值当Entry数量达到桶数量的**75%**时(很多文章说使用的桶数量达到了75%但看代码不是)会成倍扩容桶数组并重新分配所有原来的Entry
LinkedHashMap
扩展HashMap增加双向链表的实现最占内存的数据结构支持iterator()时按Entry的插入顺序来排序(但是更新不算 如果设置accessOrder属性为true则所有读写访问都算) 实现上是在Entry上再增加属性before/after指针插入时把自己加到Header Entry的前面去。 如果所有读写访问都要排序还要把前后Entry的before/after拼接起来以在链表中删除掉自己
TreeMap
以红黑树实现篇幅所限详见入门教程支持iterator()时按Key值排序可按实现了Comparable接口的Key的升序排序或由传入的Comparator控制。可想象的在树上插入/删除元素的代价一定比HashMap的大 -支持SortedMap接口如firstKey()lastKey()取得最大最小的key或sub(fromKey, toKey), tailMap(fromKey)剪取Map的某一段
ConcurrentHashMap
并发优化的HashMap默认16把写锁(可以设置更多)有效分散了阻塞的概率而且没有读锁因为put/remove动作是个原子动作(比如put是一个对数组元素/Entry 指针的赋值操作)读操作不会看到一个更新动作的中间状态数据结构为Segment[]Segment里面才是哈希桶数组每个Segment一把锁。Key先算出它在哪个Segment里再算出它在哪个哈希桶里支持ConcurrentMap接口如putIfAbsent(keyvalue)与相反的replace(keyvalue)与以及实现CAS的replace(key, oldValue, newValue)
ConcurrentSkipListMap
JDK6新增的并发优化的SortedMap以SkipList实现SkipList是红黑树的一种简化替代方案是个流行的有序集合算法篇幅所限见入门教程Concurrent包选用它是因为它支持基于CAS的无锁算法而红黑树则没有好的无锁算法它的size()不能随便调会遍历来统计效率低
补充说明
关于null
HashMap和LinkedHashMap是随意的TreeMap没有设置Comparator时key不能为nullConcurrentHashMap在JDK7里value不能为nullJDK8里key与value都不能为nullConcurrentSkipListMap是所有JDK里key与value都不能为null
Set
Set对每个对象只接受一次并使用自己内部的排序方法Set几乎都是内部用一个Map来实现, 因为Map里的KeySet就是一个Set而value是假值全部使用同一个Object。Set的特征也继承了那些内部Map实现的特征。
Set接口主要实现了两个实现类
HashSet : HashSet类按照哈希算法来存取集合中的对象存取速度比较快,内部是HashMapTreeSet : TreeSet类实现了SortedSet接口能够对集合中的对象进行排序。LinkedHashSet内部是LinkedHashMap。ConcurrentSkipListSet内部是ConcurrentSkipListMap的并发优化的SortedSet。CopyOnWriteArraySet内部是CopyOnWriteArrayList的并发优化的Set利用其addIfAbsent()方法实现元素去重如前所述该方法的性能很一般。
补充说明
好像少了个ConcurrentHashSet本来也该有一个内部用ConcurrentHashMap的简单实现但JDK偏偏没提供。Jetty就自己封了一个Guava则直接用java.util.Collections.newSetFromMap(new ConcurrentHashMap()) 实现
Jetty 是一个开源的servlet容器它为基于Java的web容器 Guava是一种基于开源的Java库,谷歌很多项目使用它的很多核心库
Queue Queue是在两端出入的List所以也可以用数组或链表来实现。
add 增加一个元索 如果队列已满则抛出一个IIIegaISlabEepeplian异常remove 移除并返回队列头部的元素 如果队列为空则抛出一个NoSuchElementException异常element 返回队列头部的元素 如果队列为空则抛出一个NoSuchElementException异常offer 添加一个元素并返回true 如果队列已满则返回falsepoll 移除并返问队列头部的元素 如果队列为空则返回nullpeek 返回队列头部的元素 如果队列为空则返回nullput 添加一个元素 如果队列满则阻塞take 移除并返回队列头部的元素 如果队列为空则阻塞
注意 remove、element、offer 、poll、peek 其实是属于Queue接口。 add remove element操作在队满或者队空的时候会报异常。 offer poll peek 在队满或者队空的时候不会报异常。 put take操作属于阻塞操作。队满队空均会阻塞。 –普通队列–
LinkedList
以双向链表实现的LinkedList既是List也是Queue。它是唯一一个允许放入null的Queue。
ArrayDeque 以循环数组实现的双向Queue。大小是2的倍数默认是16。 普通数组只能快速在末尾添加元素为了支持FIFO从数组头快速取出元素就需要使用循环数组n有队头队尾两个下标
弹出元素时队头下标递增加入元素时如果已到数组空间的末尾则将元素循环赋值到数组0同时队尾下标指向0再插入下一个元素则赋值到数组[1]队尾下标指向1。如果队尾的下标追上队头说明数组所有空间已用完进行双倍的数组扩容。
PriorityQueue
PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序通过其 java.util.Comparable 实现或者根据传递给构造函数的 java.util.Comparator 实现来定位。用二叉堆实现的优先级队列详见入门教程不再是FIFO而是按元素实现的Comparable接口或传入Comparator的比较结果来出队数值越小优先级越高越先出队注意其iterator()的返回不会排序。
–线程安全的队列–
ConcurrentLinkedQueue/ConcurrentLinkedDeque ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们所以只要不需要知道队列的大 小 ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢需要遍历队列。 无界的并发优化的Queue基于链表实现了依赖于CAS的无锁算法。 ConcurrentLinkedQueue的结构是单向链表和head/tail两个指针因为入队时需要修改队尾元素的next指针以及修改tail指向新入队的元素两个CAS动作无法原子所以需要的特殊的算法篇幅所限见入门教程。
–线程安全的阻塞队列–
BlockingQueue的队列长度受限用以保证生产者与消费者的速度不会相差太远避免内存耗尽队列长度设定后不可改变当入队时队列已满或出队时队列已空不同函数的效果见下表
PriorityBlockingQueue
一个由优先级堆支持的无界优先级队列。无容量限制无界的并发优化的PriorityQueue也是基于二叉堆。使用一把公共的读写锁。虽然实现了BlockingQueue接口其实没有任何阻塞队列的特征空间不够时会自动扩容。
DelayQueue
一个由优先级堆支持的、基于时间的调度队列。内部包含一个PriorityQueue同样是无界的。元素需实现Delayed接口每次调用时需返回当前离触发时间还有多久小于0表示该触发了。pull()时会用peek()查看队头的元素检查是否到达触发时间。ScheduledThreadPoolExecutor用了类似的结构。一个存放Delayed 元素的无界阻塞队列只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满则队列没有头部并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时则出现期满poll就以移除这个元素了。此队列不允许使用 null 元素。
ArrayBlockingQueue
一个由数组支持的有界队列指定容量定长的并发优化的BlockingQueue基于循环数组实现。有一把公共的读写锁与notFull、notEmpty两个Condition管理队列满或空时的阻塞状态。可以选择是否需要公平性如果公平参数被设置true等待时间最长的线程会优先得到处理其实就是通过将ReentrantLock设置为true来 达到这种公平性的即等待时间最长的线程会先操作。通常公平性会使你在性能上付出代价只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队 列此队列按 FIFO先进先出原则对元素进行排序。
LinkedBlockingQueue/LinkedBlockingDeque
一个由链接节点支持的可选有界队列。可选定长的并发优化的BlockingQueue基于链表实现所以可以把长度设为Integer.MAX_VALUE。利用链表的特征分离了takeLock与putLock两把锁继续用notEmpty、notFull管理队列满或空时的阻塞状态。
SynchronousQueue
一个利用 BlockingQueue 接口的简单聚集rendezvous机制
补充说明
JDK7有个LinkedTransferQueuetransfer(e)方法保证Producer放入的元素被Consumer取走了再返回比SynchronousQueue更好有空要学习下。
来源http://www.topthink.com/topic/11679.html 参考文章https://blog.csdn.net/imbingoer/article/details/85886312 参考文章https://blog.csdn.net/imbingoer/article/details/85884474
