概览

平时学习工作中，总会使用到各种各样的数据结构，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，用的并不是那么多

概览