Set,Map,List 数据结构 详解

这些都代表了Java中的集合，这里主要从其元素是否有序，是否可重复来进行区别记忆，以便恰当地使用，当然还存在同步方面的差异，见上一篇相关文章。

 

 

			有序否	允许元素重复否
Collection			否	是
List			是	是
Set		AbstractSet	否	否
Set	HashSet	否	否
Set	TreeSet	是（用二叉树排序）	否
Map		AbstractMap	否	使用 key-value 来映射和存储数据， Key 必须惟一， value 可以重复
Map	HashMap	否
Map	TreeMap	是（用二叉树排序）

 

Collections => Collection是所有List跟Set的始祖，List必须以特定次序来持有对象，Set无法拥有重复元素

ArrayList => 用Array实做的List，允许快速随机存取，相较于LinkedList 不适合拿来进行元素安插和移除动作

LinkedList => 提供最佳循序存取，适合安插和移除元素，随机存取动作比起ArrayList缓慢

HashSet => 是一种collection，但是只存放唯一值，是把搜寻时间看的很重要的set，用hash方式实作的set，故Access time complexity = O(1)

TreeSet => 同上，但是存入的元素都会经过排列，所以速度比HashSet 慢一点

LinkedHashSet =>

Performance is likely to be just slightly below that of HashSet, due to the added eXPense of maintaining the linked list, with one exception: Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity.

BitSet => 能够高效率的储存大量 [ 1 / 0 ] (开/关) 资料

HashMap => 用来取代HashTable，储存 (key/value) pairs

TreeMap => 储存 (key/value) pairs，会自动根据Key值排序

LinkedHashMap =>

Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

IdentityHashMap =>

This has better locality for large tables than does using separate arrays.) For many JRE implementations and operation mixes, this class will yield better performance than HashMap (which uses chaining rather than linear-probing

WeakHashMap => 这个map中，由于每个Value仅存在一个实体，因而节省了储存空间，一但程序需要某个Value，便在map中搜寻既有的对象，并使用找到的那个对象 （而非重新再造一个），由于这是一种节省储存空间的技巧，所以能够方便的让GC自动清理Key和Value，一但Key不在被使用，便会触发清理动作

容器简介

1.容器的分类

1.1.Collection：一组各自独立的元素，即其内的每个位置仅持有一个元素。

1)List：以元素安插的次序来放置元素，不会重新排列。

2)Set：不接爱重复元素，它会使用自己内部的一个排列机制

1.2.Map：一群成对的key-value对象，即所持有的是key-value pairs。

Map中不能有重复的key，它拥有自己的内部排列机制。

2.容器中的元素类型都为Object。从容器取得元素时，必须把它转换成原来的类型。

List 接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList。你可以将任何东西放到一个List容器 中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内 部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的Iterator只能对容器进行向前遍历，而 ListIterator则继承了Iterator的思想，并提供了对List进行双向遍历的方法。

Set接口也是 Collection的一种扩展，而与List不同的时，在Set中的对象元素不能重复，也就是说你不能把同样的东西两次放入同一个Set容器中。它的常 用具体实现有HashSet和TreeSet类。HashSet能快速定位一个元素，但是你放到HashSet中的对象需要实现hashCode()方 法，它使用了前面说过的哈希码的算法。而TreeSet则将放入其中的元素按序存放，这就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外 两个实用类Comparable和Comparator。一个类是可排序的，它就应该实现Comparable接口。有时多个类具有相同的排序算法，那就 不需要在每分别重复定义相同的排序算法，只要实现Comparator接口即可。集合框架中还有两个很实用的公用类：Collections和 Arrays。Collections提供了对一个Collection容器进行诸如排序、复制、查找和填充等一些非常有用的方法，Arrays则是对一 个数组进行类似的操作。

Map是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map，依次类推，这 样就可 形成一个多级映射。对于键对象来说，像Set一样，一个Map容器中的键对象不允许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得 到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使 用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求。你可以将任意多个键都映射到一 个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。Map有两种比较常用的实 现：HashMap和TreeMap。HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的 方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用 pub(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。

2.List、vector、set、map的区别与联系

在使用Java的时候，我们都会遇到使用集合（Collection）的时候，但是Java API提供了多种集合的实现，我在使用和面试的时候频频遇到这样的“抉择” 。 :）（主要还是面试的时候）

久而久之，也就有了一点点的心得体会，写出来以供大家讨论。

总的说来，Java API中所用的集合类，都是实现了Collection接口，他的一个类继承结构如下：

Collection<--List<--Vector

Collection<--List<--ArrayList

Collection<--List<--LinkedList

Collection<--Set<--HashSet

Collection<--Set<--HashSet<--LinkedHashSet

Collection<--Set<--SortedSet<--TreeSetVector : 基于Array的List，其实就是封装了Array所不具备的一些功能方便我们使用，它不可能走入Array的限制。性能也就不可能超越Array。所 以，在可能的情况下，我们要多运用Array。另外很重要的一点就是Vector“sychronized”的，这个也是Vector和 ArrayList的唯一的区别。

ArrayList：同Vector一样是一个基于Array上的链表，但是不同的是ArrayList不是同步的。所以在性能上要比Vector优越一些，但是当运行到多线程环境中时，可需要自己在管理线程的同步问题。

LinkedList：LinkedList不同于前面两种List，它不是基于Array 的，所以不受Array性能的限制。它每一个节点（Node）都包含两方面的内容：1.节点本身的数据（data）；2.下一个节点的信息 （nextNode）。所以当对LinkedList做添加，删除动作的时候就不用像基于Array的List一样，必须进行大量的数据移动。只要更改 nextNode的相关信息就可以实现了。这就是LinkedList的优势。

List总结：

1. 所有的List中只能容纳单个不同类型的对象组成的表，而不是Key－Value键值对。例如：[ tom,1,c ]；

2. 所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]；

3. 所有的List中可以有null元素，例如[ tom,null,1 ]；

4. 基于Array的List（Vector，ArrayList）适合查询，而LinkedList（链表）适合添加，删除操作。

HashSet：虽然Set同List都实现了Collection接口，但是他们的实现方式 却大不一样。List基本上都是以Array为基础。但是Set则是在HashMap的基础上来实现的，这个就是Set和List的根本区别。 HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。看看HashSet的add（Object obj）方法的实现就可以一目了然了。

public boolean add(Object obj)

{

return map.put(obj, PRESENT) == null;

}

这个也是为什么在Set中不能像在List中一样有重复的项的根本原因，因为HashMap的key是不能有重复的。

LinkedHashSet：HashSet的一个子类，一个链表。

TreeSet：SortedSet的子类，它不同于HashSet的根本就是TreeSet是有序的。它是通过SortedMap来实现的。

Set总结：

1. Set实现的基础是Map（HashMap）；

2. Set中的元素是不能重复的，如果使用add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象；

3.Java基本概念：集合类 List/Set/Map... 的区别和联系

Collection：List、Set

Map：HashMap、HashTable

如何在它们之间选择

一、Array ， Arrays

Java所有“存储及随机访问一连串对象”的做法，array是最有效率的一种。

1、

效率高，但容量固定且无法动态改变。

array还有一个缺点是，无法判断其中实际存有多少元素，length只是告诉我们array的容量。

2、Java中有一个Arrays类，专门用来操作array。

arrays中拥有一组static函数，

equals()：比较两个array是否相等。array拥有相同元素个数，且所有对应元素两两相等。

fill()：将值填入array中。

sort()：用来对array进行排序。

binarySearch()：在排好序的array中寻找元素。

System.arraycopy()：array的复制。

二、Collection ， Map

若撰写程序时不知道究竟需要多少对象，需要在空间不足时自动扩增容量，则需要使用容器类库，array不适用。

1、Collection 和 Map 的区别

容器内每个为之所存储的元素个数不同。

Collection类型者，每个位置只有一个元素。

Map类型者，持有 key-value pair，像个小型数据库。

2、各自旗下的子类关系

Collection --List： 将以特定次序存储元素。所以取出来的顺序可能和放入顺序不同。

--ArrayList / LinkedList / Vector --Set ： 不能含有重复的元素

--HashSet / TreeSet

Map

--HashMap

--HashTable

--TreeMap

3、其他特征

* List，Set，Map将持有对象一律视为Object型别。

* Collection、List、Set、Map都是接口，不能实例化。

继承自它们的 ArrayList, Vector, HashTable, HashMap是具象class，这些才可被实例化。

* vector容器确切知道它所持有的对象隶属什么型别。vector不进行边界检查。

三、Collections

Collections是针对集合类的一个帮助类。提供了一系列静态方法实现对各种集合的搜索、排序、线程完全化等操作。

相当于对Array进行类似操作的类——Arrays。

如，Collections.max(Collection coll); 取coll中最大的元素。

Collections.sort(List list); 对list中元素排序

四、如何选择？

1、容器类和Array的区别、择取

* 容器类仅能持有对象引用（指向对象的指针），而不是将对象信息copy一份至数列某位置。

* 一旦将对象置入容器内，便损失了该对象的型别信息。

2、

* 在各种Lists中，最好的做法是以ArrayList作为缺省选择。当插入、删除频繁时，使用LinkedList()；

Vector总是比ArrayList慢，所以要尽量避免使用。

* 在各种Sets中，HashSet通常优于HashTree（插入、查找）。只有当需要产生一个经过排序的序列，才用TreeSet。

HashTree存在的唯一理由：能够维护其内元素的排序状态。

* 在各种Maps中

HashMap用于快速查找。

* 当元素个数固定，用Array，因为Array效率是最高的。

结论：最常用的是ArrayList，HashSet，HashMap，Array。

注意：

1、Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素。

2、Set和Collection拥有一模一样的接口。

3、List，可以通过get()方法来一次取出一个元素。使用数字来选择一堆对象中的一个，get(0)...。(add/get)

4、一般使用ArrayList。用LinkedList构造堆栈stack、队列queue。

5、Map用 put(k,v) / get(k)，还可以使用containsKey()/containsValue()来检查其中是否含有某个key/value。

HashMap会利用对象的hashCode来快速找到key。

* hashing 哈希码就是将对象的信息经过一些转变形成一个独一无二的int值，这个值存储在一个array中。

我们都知道所有存储结构中，array查找速度是最快的。所以，可以加速查找。

发生碰撞时，让array指向多个values。即，数组每个位置上又生成一个梿表。

6、Map中元素，可以将key序列、value序列单独抽取出来。使用keySet()抽取key序列，将map中的所有keys生成一个Set。

使用values()抽取value序列，将map中的所有values生成一个Collection。

为什么一个生成Set，一个生成Collection？那是因为，key总是独一无二的，value允许重复。