Java中的容器类

Java中的容器类

2018, Dec 16    

概览

平时学习工作中,总会使用到各种各样的数据结构,map、set、LinkedHashMap等等,虽然在使用的过程中对此有了一定的了解,但是感觉还是不是很通透。故此写一篇blog用于总结java中的数据结构。

Java的容器类

Java中的容器类按照大的来分,主要可以分为:

  • collection:存储着对象的集合
  • map:存储着key,value的键值对 接下来的主要就分别以上面两个类别展开进行整理

Collection

List

List类别 特点
ArrayList 基于动态数组实现,支持随机访问,允许所有元素包括null
Vector 与ArrayList相似,但是Vector是线程安全的(同步的)
LinkedList 基于双向链表,只能顺序访问,可以快速的再链表中插入和删除元素(栈[Stack]、队列[Queue]、双向队列[Deque])。没有同步方法
Stack 继承自Vector,实现一个后进先出的堆栈。额外提供了5个方法使得Vector可以被当做堆栈使用:push,pop,peek,empty,search。刚刚创建的时候是空栈

和LinkedList一样,ArrayList也是非同步的(unsynchronized)。一般情况下使用这两个就可以了,因为非同步,所以效率比较高。 如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList。 几种java容器

有几个问题

  • ArrayList的扩容操作?

每一次扩容都会扩容到原来的1.5倍,使用grow()方法,第一次添加元素的时候分配10个对象空间,当添加到第11个元素的时候,就会扩容到原来的1.5倍,当添加到16个元素的时候,就会扩容到原来的15*1.5的大小,等等。每一次扩容都是通过Array.copyof(elementData,newCapacity)来实现的,会消耗大量的资源,代价比较大,因此在知道大致对象大小的时候,提前设置好ArrayList的大小是非常明智的选择。(old+old»1)

  • 为什么Vector是线程安全的?

Set

Set类别 特点
SortSet(TreeSet) 基于红黑树有序,TreeSet是set的一种变体,是可以实现排序等功能的集合 O(logN)
HashSet 基于hash表实现,可以看成一个只有key的HashMap O(1) ,不允许重复,无序,允许存在null(最多一个)
LinkedHashSet 具有HashSet的查找效率,且内部使用了双向链表维护了元素的插入顺序,保证了集合的有序性

写了 HashMap 和 HashSet,然后我们可以看到 HashSet 的方法基本上都是基于 HashMap 来实现的,说白了,HashSet内部的数据结构就是一个 HashMap,其方法的内部几乎就是在调用 HashMap 的方法。 LinkedHashSet 首先我们需要知道的是它是一个 Set 的实现,所以它其中存的肯定不是键值对,而是值。此实现与 HashSet 的不同之处在于,LinkedHashSet 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可为插入顺序或是访问顺序。 看到上面的介绍,是不是感觉其与 HashMap 和 LinkedHashMap 的关系很像?LinkedHashSet就是使用LinkedHashMap来实现的。 注意,此实现不是同步的。如果多个线程同时访问链接的哈希Set,而其中至少一个线程修改了该 Set,则它必须保持外部同步。

Queue

队列与Stack的区别在于,Stack的删除与添加都在队尾进行,而Queue删除在队头,添加在队尾

Queue类别 特点
LinkedList 基于双向链表,只能顺序访问,可以快速的再链表中插入和删除元素
PriorityQueue 基于堆结构实现,可以用来实现优先队列

Map

HashMap

HashMap实际上就是java中最基本的两个结构所实现的:数组和指针。通俗的说,就是数组和链表的结合体。(HashMap如何实现)

  • 每一个Entry的结构中包含了 key,value, int hash,和下一个Entry的指针next
  • 然后构造HashMap的时候,会初始化一个数组 table=new Entry[capacity]
  • 由此看来,entry就是键值对,另外还包含了写一个next的Entry指针,由此构成了链表
  • 在我们想要查找某一个元素的时候,只需要key和hash值,就能知道这个元素在什么位置,而不用去遍历链表,优化了查询的效率
  • HashMap的底层数组总是2的n次幂,这样的好处是可以让不同的key算出来的index相同的几率较小,那么数据在数组上的分布就会比较均匀
  • 从HashMap中get元素的时候,先计算出key的hashcode,然后找到数组中对应位置的某一元素,然后通过key的equals方法在对应的位置链表中找到需要的元素

当 HashMap 中的元素越来越多的时候,hash 冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对 HashMap 的数组进行扩容,数组扩容这个操作也会出现在 ArrayList 中,这是一个常用的操作,而在 HashMap 数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是 resize。

那么 HashMap 什么时候进行扩容呢?当 HashMap 中的元素个数超过数组大小 *loadFactor时,就会进行数组扩容,loadFactor的默认值为 0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为 16,那么当 HashMap 中元素个数超过 160.75=12 的时候,就把数组的大小扩展为 216=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知 HashMap 中元素的个数,那么预设元素的个数能够有效的提高 HashMap 的性能。

初始容量为16,负载因此为0.75,只要超过了16*0.75=12的时候,就会进行扩容到原来的两倍
遍历的时候最好使用map.entrySet().iterator()的方式,效率比较高 HashMap是非同步的。

解决hash冲突的方法:

方法 内容
开放地址法 按照一定的次序,从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素(线性探查法、平方探查法、双散列函数探查法)
链地址法(拉链法) jdk1.7 全都是单链表来存储同义词,jdk1.8之后,如果链表的长度大于8,会转换为红黑树来存储
再哈希法 同时构造多个不同的哈希函数,直到冲突不再产生,但是增加了计算时间
建立公共溢出区 将哈希表分为公共表和溢出表,当溢出发生的时候,将所有的溢出输出统一放到溢出区

HashTable

  • 与HashMap特别的相似,但是HashTable是线程安全的(如果想使用一个线程安全的HashMap,可以使用Collections类中的synchronizedMap()方法)
  • HashTable不允许null(key value 都不行),HashMap允许一个null的key,若干的value的null

LinkedHashMap

LinkedHashMap是HashMap的一个子类,它保留了插入时候的顺序,如果需要在输出的时候保持和输入的顺序时相同,就使用本结构(一言:有序的HashMap)

  • 维护着一个云星宇所有条目的双重链接列表。这个链接定义了迭代顺序,可以是插入顺序或者是访问顺序
  • 和HashMap一样,都是不同步的
  • 可以实现LRU缓存(Least Recently Used),把最近最少使用的数据溢出,让给最新读取的数据。

ConcurrentHashMap

ConcurrentHashMap 是一个并发散列映射表的实现,它允许完全并发的读取,并且支持给定数量的并发更新。相比于 HashTable 和用同步包装器包装的 HashMap(Collections.synchronizedMap(new HashMap())),ConcurrentHashMap 拥有更高的并发性。在 HashTable 和由同步包装器包装的 HashMap 中,使用一个全局的锁来同步不同线程间的并发访问。(基于java的内存机制(mark))(没有ConcurrentHashTable这个类)

SortedMap(TreeMap)

SortedMap mapA = new TreeMap();

Comparator comparator = new MyComparator();
SortedMap mapB = new TreeMap(comparator);

能够自然排序的一个map,用的并不是那么多

参考网站