Array(数组)和集合的区别:
(1)数组是大小固定的,并且同一个数组只能存放类型一样的数据(基本类型/引用类型)
(2)JAVA集合可以存储和操作数目不固定的一组数据。
(3)若编程时不知道究竟需要多少对象,需要在空间不足时自动扩增容量,则需要使用容器类库,array不适用。  
FYI:使用相应的toArray()和Arrays.asList()方法可以相互转换。

java容器类类库(Collection和Map)

Java容器类类库的作用是保存对象,并将其划分为两个不同的概念:
1)Collection(接口) 一个独立元素的序列,这些元素都服从一条或多条规则。
List必须按照插入的顺序保存元素,而Set不能有重复的元素,Queue按照排队规则来确定对象产生的顺序(通常与它们被插入的顺序相同)
主要方法:add,equals,hashCode,remove,clear ,size,iterator等
2)Map(接口) 又称为关联数组,是一组成对的“键值对”对象,使用键对象来查找值对象。
主要方法:get,equals,clear,hashCode,put,remove,size等
四种容器:List,Set,Map,Queue,均为接口,除Map外,都继承了Collection接口,所以都拥有Collection中的方法
一、List
1、List的实现:ArrayList,LinkedList
ArrayList:主要用于随机访问大量元素,但是在List的中间插入和移除元素时较慢,按照插入的顺序保存元素,其底层实现是数组
LinkedList:可以以较低的代价在List中间进行插入和删除操作,按照插入的顺序保存元素,其底层实现是链表
List的主要方法:除继承了Colloction内的方法还扩展了get,set等方法。
2、List的选择
在LinkedList的插入和移除代价相当低廉,并且不随列表尺寸发生变化,这是因为在LinkedList中插入元素时只需链接新的元素,而不必修改链表中剩余的元素,
但在ArrayList中插入元素时代价特别高,并且其代价随链表尺寸的增加而增加,这是因为在ArrayList插入元素时,必须创建空间并将它的所有引用向前移动。
二、Set
1、Set的实现:HashSet, TreeSet, LinkedHashSet
HashSet:为快速查找而定义的Set,存入Hash Set的元素必须定义hashCode(),即散列函数。
TreeSet:保持次序的Set,底层为红-黑数结构,使用它可以从Set中提取有序的序列,元素必须实现Comparable接口。
LinkedHashSet:拥有HashSet的查询速度,所以也使用了散列函数,内部使用了链表来维护元素的插入顺序,所以在使用迭代器遍历Set时,结果会按元素的插入的次序显
示。元素也必须定义hashCode()方法。
Set的主要方法:除了继承了Collection内的方法,没有额外功能。
2、Set的选择
HashSet的性能基本上总是比TreeSet好,特别是在添加和查询元素时。TreeSet存在的唯一原因是它可以维持元素的排序状态,所以只有当需要一个排好序的Set时,才应该
使用TreeSet.因为TreeSet内部结构支持排序,并且因为迭代是我们更有可能执行的操作,所以用TreeSet迭代通常比HashSet要快。对于插入操作,LinkedHashSet比
HashSet的代价更高,这是由维护链表所带来的额外开销造成的。
3、SortedSet:其中的元素可以保证处于排序状态,按对象的比较函数对元素进行排序而不是插入顺序,TreeSet是其实现。
三、Map
1、Map的实现:HashMap , TreeMap, LinkedHashMap, WeakHashMap,ConcurrentHashMap,IdentityHashMap
HashMap:提供了最快的查找技术,基于散列表的实现,取代了HashTable,插入和查询“键值对”的开销是固定的。可以通过构造器设置容量和负载因子,以调整容
器的性能。必须有hashCode()和equals()方法。
TreeMap:基于红-黑树的实现,查看“键”或“键值对”时,它们会被排序(次序由Comparable或Comparator决定)。按照比较结果的升序保存键,所得到的结果是
经过排序的。TreeMap是唯一的带有subMap()方法的Map,它可以返回一个子树。必须实现Comparable接口。
LinkedHashMap:类似于HashMap,但是迭代遍历是时取得“键值对”的顺序是其插入次序,或者是最近最少使用(LRU)的次序,只比HashMap慢一点,而在
而在迭代访问时反而更快,因为它使用链表维护内部次序。必须实现hashCode()和equals()。
WeakHashMap:弱键映射,允许释放映射所指向的对象,这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”,则此键可以被垃圾收集器回收
ConcurrentHashMap:一种线程安全的Map,它不涉及同步加锁。
IdentityHashMap:使用==代替equals()对“键”进行比较的散列映射。专为解决特殊问题而设计的。
2、Map的选择
使用Map时,第一选择应该是HashMap,只有在要求Map始终保持有序时,才需要使用TreeMap。
LinkedHashMap在插入时比HashMap慢一点,因为它维护散列数据结构的同时还要维护链表(以保持插入顺序),正是由于这个链表,使其迭代速度更快。
3、SortedMap:TreeMap是其唯一实现,可以确保键处于排序状态。
四、Queue:
1、队列是先进先出(FIFO)的容器,只能从一端放入,从另一端取出。由于LinkedList添加了可以使其用作栈、队列或双端队列的方法,所以可以用LinkedList实现Queue
接口,
Queue接口中的方法:offer(),peek()和element()在不移除的情况下返回队头,poll()和remove()将移除并返回队头。
2、PriorityQueue:优先级队列声明下一个弹出元素是最需要的元素(具有最高的优先级)。
3、双向队列:可以在任何一端添加或移除。
五、Java 1.0/1.1的容器(尽量避免使用以下容器)
1、Vector:唯一可以自我扩展的序列,但缺点过多
2、Enumeration:迭代器的新名字–枚举,它比Iterator接口小。
3、HashTable:用HashMap代替。
4、Stack:继承了Vector。
六、散列和散列码
散列的价值在于速度,散列使得查询得以快速进行。存储一组元素最快的数据结构是数组,所以使用数组来存储键的信息。数组并不保存键本身,而是通过键对象生成一个数字,
将其作为数组的下标,这个数字就是散列码,由定义在Object中的、且可能由你的类覆盖的hashCode()方法生成。不同的键可以产生相同的下标,所以解决了数组容量被固定
的问题,但同时可能会由冲突。通常,冲突由外部链接处理:数组并不直接保存值,而是保存值的list,然后队list中的值使用equals()方法进行线性查询。默认的hashCode
产生的散列码是对象的地址,而在实际程序中不一定是将地址作为散列码,所以需要覆盖hashCode()方法,同时需要覆盖equals()方法来比较当前的键与表中的键是否相
同,因为equals()默认比较的是对象的地址,而键不一定总是由地址构成。**

一、集合

集合类存放于java.util包中。
  集合类存放的都是对象的引用,而非对象本身,出于表达上的便利,我们称集合中的对象就是指集合中对象的引用(reference)。
  集合类型主要有3种:set(集)、list(列表)和map(映射)。

一、这三者什么关系呢

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap

在这里插入图片描述
1.Collection接口
  Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set。
  所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个空的Collection,有一个 Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。
  如何遍历Collection中的每一个元素?不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下:

  Iterator it = collection.iterator(); // 获得一个迭代子
    while(it.hasNext()) {
  	Object obj = it.next(); // 得到下一个元素
} 

iterator接口:
在这里插入图片描述 由Collection接口派生的两个接口是List和Set。
2.Set

Set接口同样是Collection接口的一个子接口,它表示数学意义上的集合概念。Set中不包含重复的元素,即Set中不存两个这样的元素e1和e2,使得e1.equals(e2)为true。由于Set接口提供的数据结构是数学意义上集合概念的抽象,因此它需要支持对象的添加、删除,而不需提供随机访问。故Set接口与Collection的接口相同。

Set接口继承Collection接口,而且它不允许集合中存在重复项。所有原始方法都是现成的,没有引入新方法。具体的Set实现类依赖添加的对象的equals()方法来检查等同性。

HashSet: 使用HashMap的一个集的实现。虽然集定义成无序,但必须存在某种方法能相当高效地找到一个对象。使用一个HashMap对象实现集的存储和检索操作是在固定时间内实现的.

TreeSet: 在集中以升序对对象排序的集的实现。这意味着从一个TreeSet对象获得第一个迭代器将按升序提供对象。TreeSet类使用了一个TreeMap.

为优化 HashSet 空间的使用,您可以调优初始容量和负载因子。TreeSet 不包含调优选项,因为树总是平衡的,保证了插入、删除、查询的性能为log(n)。

HashSet 和 TreeSet 都实现 Cloneable 接口。

当您要从集合中以有序的方式抽取元素时,TreeSet实现会有用处。为了能顺利进行,添加到TreeSet的元素必须是可排序的。    Set的演示:

 import java.util.*;
public class SetExample {
      public static void main(String args[]) {
          Set set = new HashSet();
          set.add("Bernadine");
          set.add("Elizabeth");
          set.add("Gene");
          set.add("Elizabeth");
          set.add("Clara");
          System.out.println(set);

          Set sortedSet = new TreeSet(set);
          System.out.println(sortedSet);
      }
}

运行程序产生了以下输出。请注意重复的条目只出现了一次,列表的第二次输出已按字母顺序排序。

[Gene, Clara, Bernadine, Elizabeth]
[Bernadine, Clara, Elizabeth, Gene]

3.List

List接口继承了Collection 接口以定义一个允许重复项的有序集合。该接口不但能够对列表的一部分进行处理,还添加了面向位置的操作。

实际上有两种List: 一种是基本的ArrayList,其优点在于随机访问元素,另一种是更强大的LinkedList,它并不是为快速随机访问设计的,而是具有一套更通用的方法。

List : 次序是List最重要的特点:它保证维护元素特定的顺序。List为Collection添加了许多方法,使得能够向List中间插入与移除元素(这只推荐LinkedList使用。)一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和移除元素。    ArrayList : 由数组实现的List。允许对元素进行快速随机访问,但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList,而不是用来插入和移除元素。因为那比LinkedList开销要大很多。

LinkedList : 对顺序访问进行了优化,向List中间插入与删除的开销并不大,随机访问则相对较慢。(使用ArrayList代替。)还具有下列方法:addFirst(), addLast(), getFirst(), getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用。

Vector:实现一个类似数组一样的表,自动增加容量来容纳你所需的元素。使用下标存储和检索对象就象在一个标准的数组中一样。你也可以用一个迭代器从一个Vector中检索对象。Vector是唯一的同步容器类!!当两个或多个线程同时访问时也是性能良好的。

Stsck: 这个类从Vector派生而来,并且增加了方法实现栈!一种后进先出的存储结构。

面向位置的操作包括插入某个元素或 Collection 的功能,还包括获取、除去或更改元素的功能。在 List 中搜索元素可以从列表的头部或尾部开始,如果找到元素,还将报告元素所在的位置。

void add(int index, Object element) 
boolean addAll(int index, Collection collection) 
Object get(int index) 
int indexOf(Object element) 
int lastIndexOf(Object element) 
Object remove(int index) 
Object set(int index, Object element)

List 接口不但以位置友好的方式遍历整个列表,还能处理集合的子集:

ListIterator listIterator()
ListIterator listIterator(int startIndex)
List subList(int fromIndex, int toIndex) 

处理subList()时,位于fromIndex的元素在子列表中,而位于toIndex的元素则不是,提醒这一点很重要。以下for-loop 测试案例大致反映了这一点:

for (int i=fromIndex; i<toIndex; i++) {
    // process element at position i
}

List用法示例:
在这里插入图片描述
其中set方法返回的是被替换的内容。
在这里插入图片描述
4.List和Set对比

Linked 改快读慢

Array 读快改慢

Hash 两都之间

Collection是集合接口
|————Set子接口:无序,不允许重复。
|————List子接口:有序,可以有重复元素。

区别:Collections是集合类

Set和List对比:
  Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。
List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变。

Set和List具体子类:
Set
 |————HashSet:以哈希表的形式存放元素,插入删除速度很快。

List
 |————ArrayList:动态数组
 |————LinkedList:链表、队列、堆栈。

Array和java.util.Vector
Vector是一种老的动态数组,是线程同步的,效率很低,一般不赞成使用。

5.Map

Map接口不是Collection接口的继承。而是从自己的用于维护键-值关联的接口层次结构入手。按定义,该接口描述了从不重复的键到值的映射。

我们可以把这个接口方法分成三组操作:改变、查询和提供可选视图。

改变操作允许您从映射中添加和除去键-值对。键和值都可以为null。但是,您不能把Map作为一个键或值添加给自身。

Object put(Object key, Object value)返回值是被替换的值。
Object remove(Object key)
void putAll(Map mapping)
void clear()

查询操作允许您检查映射内容:

 Object get(Object key)
    boolean containsKey(Object key)
    boolean containsValue(Object value)
    int size()
    boolean isEmpty()

提供可选视图方法允许您把键或值的组作为集合来处理。

  public Set keySet()
    public Collection values()
    public Set entrySet()

因为映射中键的集合必须是唯一的,您用Set支持。因为映射中值的集合可能不唯一,您用Collection支持。最后一个方法返回一个实现Map.Entry接口的元素Set。

Map.Entry 接口

Map的entrySet()方法返回一个实现Map.Entry接口的对象集合。集合中每个对象都是底层Map中一个特定的键-值对。

通过这个集合迭代,您可以获得每一条目的键或值并对值进行更改。但是,如果底层Map在Map.Entry接口的setValue()方法外部被修改,此条目集就会变得无效,并导致迭代器行为未定义。

HashMap 类和 TreeMap 类

“集合框架”提供两种常规的Map实现:HashMap和TreeMap。和所有的具体实现一样,使用哪种实现取决于您的特定需要。在Map中插入、删除和定位元素,HashMap是最好的选择。但如果您要按顺序遍历键,那么TreeMap会更好。根据集合大小,先把元素添加到HashMap,再把这种映射转换成一个用于有序键遍历的TreeMap可能更快。使用HashMap要求添加的键类明确定义了hashCode()实现。有了TreeMap实现,添加到映射的元素一定是可排序的。

为了优化HashMap空间的使用,您可以调优初始容量和负载因子。这个TreeMap没有调优选项,因为该树总处于平衡状态。

HashMap和TreeMap都实现Cloneable接口。

Hashtable类和Properties类是Map接口的历史实现。

HashTable: 实现一个映象,所有的键必须非空。为了能高效的工作,定义键的类必须实现hashcode()方法和equal()方法。这个类是前面java实现的一个继承,并且通常能在实现映象的其他类中更好的使用。

HashMap: 实现一个映象,允许存储空对象,而且允许键是空(由于键必须是唯一的,当然只能有一个)。

WeakHashMap: 实现这样一个映象:通常如果一个键对一个对象而言不再被引用,键/对象对将被舍弃。这与HashMap形成对照,映象中的键维持键/对象对的生命周期,尽管使用映象的程序不再有对键的引用,并且因此不能检索对象。

TreeMap: 实现这样一个映象,对象是按键升序排列的。

映射的使用示例:

以下程序演示了具体Map类的使用。该程序对自命令行传递的词进行频率计数。HashMap起初用于数据存储。后来,映射被转换为TreeMap以显示有序的键列列表。

import java.util.*;

public class MapExample {
  public static void main(String args[]) {
    Map map = new HashMap();
    Integer ONE = new Integer(1);
    for (int i=0, n=args.length; i<n; i++) {
      String key = args[i];
      Integer frequency = (Integer)map.get(key);
      if (frequency == null) {
        frequency = ONE;
      } else {
        int value = frequency.intValue();
        frequency = new Integer(value + 1);
      }
      map.put(key, frequency);
    }
    System.out.println(map);
    Map sortedMap = new TreeMap(map);
    System.out.println(sortedMap);
  }
}

结果:
//无序输出:

{prescribed=1, a=1, time=2, any=1, no=1, shall=1, nor=1, peace=1, owner=1, soldier=1, to=1, the=2, law=1, but=1, manner=1, without=1, house=1, in=4, by=1, consent=1, war=1, quartered=1, be=2, of=3}
//有序输出:
{a=1, any=1, be=2, but=1, by=1, consent=1, house=1, in=4, law=1, manner=1, no=1, nor=1, of=3, owner=1, peace=1, prescribed=1, quartered=1, shall=1, soldier=1, the=2, time=2, to=1, war=1, without=1}

解疑:

1、什么是Iterator

一些集合类提供了内容遍历的功能,通过java.util.Iterator接口。这些接口允许遍历对象的集合。依次操作每个元素对象。当使用 Iterators时,在获得Iterator的时候包含一个集合快照。通常在遍历一个Iterator的时候不建议修改集合本省。

2、Iterator与ListIterator有什么区别?

Iterator:只能正向遍历集合,适用于获取移除元素。ListIerator:继承Iterator,可以双向列表的遍历,同样支持元素的修改。

3、什么是HaspMap和Map?

Map是接口,Java 集合框架中一部分,用于存储键值对,HashMap是用哈希算法实现Map的类。

4、HashMap与HashTable有什么区别?对比Hashtable VS HashMap

两者都是用key-value方式获取数据。Hashtable是原始集合类之一(也称作遗留类)。HashMap作为新集合框架的一部分在Java2的1.2版本中加入。它们之间有一下区别:

● HashMap和Hashtable大致是等同的,除了非同步和空值(HashMap允许null值作为key和value,而Hashtable不可以)。

● HashMap没法保证映射的顺序一直不变,但是作为HashMap的子类LinkedHashMap,如果想要预知的顺序迭代(默认按照插入顺序),你可以很轻易的置换为HashMap,如果使用Hashtable就没那么容易了。

● HashMap不是同步的,而Hashtable是同步的。

● 迭代HashMap采用快速失败机制,而Hashtable不是,所以这是设计的考虑点。

5、在Hashtable上下文中同步是什么意思?

同步意味着在一个时间点只能有一个线程可以修改哈希表,任何线程在执行hashtable的更新操作前需要获取对象锁,其他线程等待锁的释放。

6、什么叫做快速失败特性

从高级别层次来说快速失败是一个系统或软件对于其故障做出的响应。一个快速失败系统设计用来即时报告可能会导致失败的任何故障情况,它通常用来停止正常的操作而不是尝试继续做可能有缺陷的工作。当有问题发生时,快速失败系统即时可见地发错错误告警。在Java中,快速失败与iterators有关。如果一个iterator在集合对象上创建了,其它线程欲“结构化”的修改该集合对象,并发修改异常 (ConcurrentModificationException) 抛出。

7、怎样使Hashmap同步?

HashMap可以通过Map m = Collections.synchronizedMap(hashMap)来达到同步的效果。

8、什么时候使用Hashtable,什么时候使用HashMap

基本的不同点是Hashtable同步HashMap不是的,所以无论什么时候有多个线程访问相同实例的可能时,就应该使用Hashtable,反之使用HashMap。非线程安全的数据结构能带来更好的性能。

如果在将来有一种可能—你需要按顺序获得键值对的方案时,HashMap是一个很好的选择,因为有HashMap的一个子类 LinkedHashMap。所以如果你想可预测的按顺序迭代(默认按插入的顺序),你可以很方便用LinkedHashMap替换HashMap。反观要是使用的Hashtable就没那么简单了。同时如果有多个线程访问HashMap,Collections.synchronizedMap()可以代替,总的来说HashMap更灵活。

9、为什么Vector类认为是废弃的或者是非官方地不推荐使用?或者说为什么我们应该一直使用ArrayList而不是Vector

你应该使用ArrayList而不是Vector是因为默认情况下你是非同步访问的,Vector同步了每个方法,你几乎从不要那样做,通常有想要同步的是整个操作序列。同步单个的操作也不安全(如果你迭代一个Vector,你还是要加锁,以避免其它线程在同一时刻改变集合).而且效率更慢。当然同样有锁的开销即使你不需要,这是个很糟糕的方法在默认情况下同步访问。你可以一直使用Collections.sychronizedList来装饰一个集合。

事实上Vector结合了“可变数组”的集合和同步每个操作的实现。这是另外一个设计上的缺陷。Vector还有些遗留的方法在枚举和元素获取的方法,这些方法不同于List接口,如果这些方法在代码中程序员更趋向于想用它。尽管枚举速度更快,但是他们不能检查如果集合在迭代的时候修改了,这样将导致问题。尽管以上诸多原因,Oracle也从没宣称过要废弃Vector。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐