疯狂Java笔记之常见java集合的实现细节

Set和Map

1.Set和Map的关系

首先Set是一种集合元素无序,不可重复的集合。而Map则代表一种有多个key-value对组成的集合,Map集合类似于传统的关联数据。看起来他们没哟什么关联,实际上Set和Map是有莫大的关联的。可以说Map是Set集合的扩展。

当我们只看Map的Key时,会发现所有的key不能重复,key之间没有顺序。也就是说将Map所有的key集合起来就组成了一个set集合。Map也提供了如下方法来返回组成的set集合

Set<K> keySet()

对于一个Map集合而言,它本质上是一个关联数组,关联数组中的key-value对之间有严格的对应关系,那将key-value对捆绑在一起对待,如下所示:

java4.PNG

2.HashMap和HashSet

在HashSet里,系统采用Hash算法决定集合元素的存储位置,这样可以保证快速存,取集合元素;对于HashMap而言,系统将value当初key的‘附属物’,系统根据Hash算法开决定key的存储位置,这个可以保证快速存,取集合key,而value总是紧随key存储。

集合号称存储的是Java对象,但实际上并不会真正将Java对象放入Set集合中,而只是在Set集合中保留这些对象的引用而己。也就是说,Java集合实际上是多个引用变量所组成的集合,这些引用变量指向实际的Java对象。对于java集合他只是多个引用变量的集合。

当程序试图将一个key-value对放入HashMap中时,首先根据该key的hashCade()返回值决定该Entry的存储位置—如果两个Entry的key的hashCade返回值相同,那么它们的存储位置相同:如果这两个Entry的key通过equals比较返回true,则新添加Entry的value将覆盖集合中原有Entry的value,但key不会覆盖;如果这两个Entry的key通过equal比较返回false ,则新添加的Entry将与集合中原有的Entry形成Entry链,而且新添加的Entry位于Entry链的头部

当系统开始初始化HashMap时,系统会创建一个长度为capacity的Entry数组。这个数组可以存储元素的位置被称为“桶(bucket)”,每个bucket都有其指定的索引,系统可以根据其索引快速访问该bucket里存储的元素。

无论何时,HashMap的每一个“桶”只存储一个元素(即一个Entry).由于Entry对象可以包含一个引用变量(就是Entry构造器的最后一个参数)用于指向下一个Entry,因此可能出现:HashMap的bucket中只有一个Entry,但这个Entry指向另一个Entry这就形成一个Entry链,如图:

set.PNG

HashMap在每一个bucket里只有一个Entry,所以可以根据索引快速取出该bucket里的Enrty.当发生hash冲突时,单个bucket里存储的不是一个Entry,而是一个Entry链,系统会按顺序遍历每个Entry,知道找到想搜到的Entry为止,即使要搜索的末端,系统也会循环到最后找到该元素。

3.TreeMap和TreeSet

TreeSet底层实际使用的容器就是TrenMap.绝大部分的方法都是直接调用TreeMap的方法来实现的。而对于TreeMap而言,它采用一种被称为‘红黑树’的排序二叉树来保存Map中的每个Entry即每个Entry都是红黑树的一个节点。

对于TreeMap向言,由于它底层采用一棵红黑树来保存集合中的Entry,这意味着TreeMap添加元素、取出元素的性能都比HashMap低。当TreeMag添加元素时,需要通过循坏找到新 增Entry的插入位置,因此比较耗性能;当从TreeMap中取出元素时,需要通过循环才能找到合适的Entry,也比较耗性能·但TreeMap, TreeSet相比HashMag,HashSet的优势在于:'TreeMap中的所有Entry总是按key根据指定的排序规则保持有序状态,TreeSet中的所有元素总是根据指定的排序规则保持有序状态。

Map和List

1.Map的values()方法

不管是HashIvlap,还是TreeMap,它们的values()方法都可返回其所有value组成的Collection集合。按照通常理解,这个Collection集合应该是一个List集合,因为Map的多个valu。允许重复。 但实际上,HashMap,TreeMap的values()方法的实现要更巧妙。这两个Mad对象的values()方法返回的是一个不存储元素的Collection集合,当程序遍历Collection集合时,实际上就是遍历Map对象的value

HashMap和TreeMap的values()方法并未把Map中的value重新组合成一个包含元素的集合对象,这样就可以降低系统内存开销。

2.Map和List的关系

  • 从底层实现来看,Set和Map很相似;从用法的角度来看,Map和List也有很大的相似之处。

1.Map接口提供了get(K key)方法,允许Map对象根据key来取得value. 2.List接口提供了get(int index)方法,允许list对象根据元素索引来取得value

Map和List在底层实现上没有太大的相似之处,只是用法有一些相似之处。

ArrayList和LinkedList

1.Vector和ArrayList的区别

Vector和ArrayList这个两个集合类的本质并没有太大的不同,它们都实现了List接口,而且底层都是基于Java数组来存储集合元素的。

此外从序列化机制的角度看,ArrayList的实现比Vector的实现更安全 另外Vector是ArrayList的线程安全版本,ArrayList和Vector觉大部分方法的实现都是相同的,只是Vector的方法增加了synchronized修饰。

2.ArrayList和LinkedList的实现差异

List代表一种线性表的数据结构。ArrayList则是一种顺序存储的线性表,ArrayList底层采用数组来保存每个集合元素,LinkedList则是一种链式存储的线性表,其本质上就是一个双向链表,但它不仅实现了List接口,还实现了Deque接口。也就是说,LinkedList既可以当成双向链表使用,也可以当成队列使用,还可以当成栈来使用(Deque代表双端队列,既具有队列的特征.也具有栈的特征)。

ArrayList 因为ArrayList底层数据结构是数组,所以我们插入元素是需要完成两件事:

  • 保证ArrayList底层封装的数组长度大于集合数据长度
  • 插入之前将所有元素“整体搬家”,向后移动一格

同理在删除元素是也要对元素进行“整体搬家”,这就导致增加和删除的性能非常差,当时在取出数据元素时,性能基本和数组是一样的。

LinkedList 因为LinkedSet是采用双向链表的,如果单纯的添加某个节点性能是很好的,当时如果需要指定索引处添加节点,LinkedList必须必须先找到索引处的节点,这个搜索过程系统开销也是不少的,删除也同理,如下图所示:

LinkedList.PNG

LinkedList2.PNG

不过弊端是对于ArrayList而言,由于它底层采用数组来保存集合元素,因此可以直接根据数组索引取出index位置的元素;但对于LinkedList就比较麻烦,LinkedList必须逐个元素地搜索,直到找到第index个元素为止。所以性能相对较低。

3.ArrayList和LinkedList的性能分析和适用场景

当程序需要以get(int index)获取List集合指定的索引出的元素,ArrayList性能大大的优于LinkedList。因为ArrayList底层以数组来保存集合元素,所以调用get(int index)方法获取指定索引处的元素时,底层实际调用elementData[index]来返回改元素,因此性能非常好,而LinkedList则必须逐个的搜索。

当程序调用add(int index,Object obj)向List添加数据是,ArrayList需要“整体搬家”才能实现添加,而LinkedList需要找到索引而不用整体搬家,当时找索引也需要消耗一些系统性能,因为他是逐个搜索。同理,删除也是这样子。

当添加的数据个数大于底层数组的长度时,那么ArrayList必须创建一个长度为原来长度1.5倍的数组,再由垃圾回收机制进行回收。这样系统开销也有点大了。而LinkedList就不存在这个问题。

不过从大多数应用场景来说ArrayList总体性能还是优于LinkedList。

Iterator迭代器

1.Iterator实现类与迭代器模式

Java的lteratar和Enumeration两个接口都是迭代器模式的代表之作,它们就是迭代器模式里的“迭代器接口”。所谓迭代器模式指的是,系统为遍历多种数据列表、集合,容器提供一个标准的“迭代器接口”,这些数据列表、集合、容器就可面向相同的“迭代器接口”编程,通过相同的迭代器接口访问不同数据列表‘集合、容器里的数据.不同的数据列表、集合、容器如何实现这个“迭代器接口”, 则交给各数据列表、集合、容器自己完成。

2.迭代是删除指定元素

对于TreeSet, HashSet等Set集合而言,当使用Iterator遍历它们时,如果正在遍历最后一个集合元素,那么使用Set集合的remove()方法删除集合的任意元素并不会引发ConcurrentModificatianException异常,当正在遍历其他元素时删除集合的任意元素都将引发该异常。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏wannshan(javaer,RPC)

JDK PriorityBlockingQueue remove(Object o) 源码分析

先知道PriorityBlockingQueue 是利用数组存储二叉堆实现。最小值(最优先)放在queue[0]位置。 //删除某个元素 public bool...

3687
来自专栏开发之途

Java集合框架源码解析之LinkedHashMap

1243
来自专栏Android机动车

数据结构学习笔记——线性表(下)

了解过线性表的链式存储结构以后,有人就想出来用数组来代替指针,来描述单链表。看看他们是怎么做到的。

491
来自专栏Java进阶之路

纪念第一次手写源码

1820
来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

2506
来自专栏小樱的经验随笔

【Java数据结构学习笔记之一】线性表的存储结构及其代码实现

应用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系 线性结构:数据元素之间存在一个对一个的关系 树形结构:数...

3055
来自专栏用户画像

剑指offer 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

942
来自专栏开发之途

Java集合框架源码解析之LinkedList

1283
来自专栏java思维导图

【一分钟知识】常用集合List、Map、Set

Collection和Collections的区别 Collection是一个接口,它是Set、List等容器的父接口; Collections是个一个工具类...

3606
来自专栏韦弦的偶尔分享

Swift 有效的括号 - LeetCode

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

1792

扫码关注云+社区

领取腾讯云代金券