您的位置 首页 java

Java之集合

在许多应用场合,一组数据的长度不是固定的,比如一个单位的员工数目是变化的,有老员工跳槽,也有新员工进来。

为了使程序能够方便的存储和操纵数目不固定的一组数据,JDK类库提供了 java 集合,位于java.util包中。与Java数组不同,Java集合中不能存放基本类型数据,而只能存放对象的引用。

Java集合主要包含4种类型:

  • Set(集): 集合中的对象不按特定方式排序,并且没有重复的对象。它的有些实现类能对集合中的对象按特定方式排序 。

  • List(列表): 集合中的对象按照 索引 位置排序,可以有重复的对象,允许按照对象在集合中的索引位置检索对象。这与数组有些相似。

  • Queue(队列): 集合中的对象按照先进先出的规则来排列。在队列的末尾添加元素,在队列的头部删除元素,可以有重复对象。双向队列则允许在队列的头部和尾部添加和删除元素。

  • Map(映射): 集合中的每个元素包含一对键(Key)对象和值(vlaue)对象,集合中没有重复的键对象,值对象可以重复。它的有些实现类能对集合中的键对象进行排序。

上面说的Set集合与数学中的集合最接近,两者都不允许有重复的元素。Set、List和Queue都是 Collection 接口的子接口,Map接口没有继承Collection接口。

主要集合类的类框图

Collection和Iterator接口

在Collection接口中声明了如下的方法:

Set接口、List接口和Queue接口都继承了Collection接口,因此可以对Set对象、List对象和Queue对象调用以上方法。

Collection接口的Iterator()方法返回一个Iterator对象,不同的集合返回各自实现的Iterator接口实例。Iterator接口中声明了如下方法:

  • hasNext(): 判断集合中的元素是否遍历完毕,如果没有返回true。
  • next(): 返回下一个元素。
  • remove(): 从集合中删除由next()方法返回的当前元素。

当通过Collection集合的iterator()方法得到一个 Iterator对象 后,如果当前 线程 或其他线程接着又通过Collection集合的某些方法对集合进行了修改操作(排除当前 Iterator对象 的remove()方法),接下来调用这个 Iterator对象 的next()方法会导致java.util.ConcurrentModificatonException运行时异常。

Iterator对象运用了快速失败机制(fail-fast),一旦监测到集合已被修改,就会抛出ConcurrentModificationException运行时异常,而不是显示修改后的当前内容,这可以避免潜在的由于共享资源竞争而导致的并发问题。

Set集合

其实Set是最简单的一种集合,内部的元素不按照特定的方式排序,并且没有重复对象。Set接口主要由两个实现类:HashSet类和TreeSet类。

  • HashSet

HashSet按照哈希算法来存取集合中的对象,存取速度比较快。HashSet还有一个子类LinkedHashSet类,它不仅实现了哈希算法,还实现了链表数据结构。链表数据结构能提高插入和删除元素的性能。

当向集合中加入一个对象时,HashSet会调用对象的hashCode()方法获得哈希码,然后根据这个哈希码进一步计算出对象在集合中的存放位置。

那hashCode()方法如何计算哈希的呢?在Object类中定义了hashCode()和equals()方法,equals()方法按照内存地址比较两个对象是否相等,同样的hashCode()方法也是按照内存地址进行计算哈希值的。

为了保证能正常工作,要求当两个对象用equals()方法比较结果为true时,它们的哈希码也相等。否则会导致HashSet无法正常工作,因为两个对象的哈希码不一样,HashSet计算出不同的位置,两个对象会存在不同位置,不会发生equals判断。

反过来,两个对象的equals方法比较不相等,却并不要求两个对象的哈希码也不相等。不过尽量保证用有不同的哈希码,可以减少哈希冲突,提高hashSet的性能。

  • TreeSet

TreeSet实现了SortedSet接口,具有排序功能。下面代码演示了这一功能:

运行结果

那么TreeSet是如何对对象进行排序的呢?TreeSet支持两种排序方式:自然排序和客户化排序,默认情况下TreeSet采用自然排序方式。

  • 自然排序

使用自然排序时,向TreeSet集合中加入的对象的类必须实现了Comparable接口。在JDK中有一部分类实现了Comparable接口,如Integer、Double和String等。

Comparable接口有一个compareTo(Object o)的方法,返回整型。对于表达式x.compareTo(y),如果返回值为0,表示x和y相等;如果返回值大于0,表示x大于y;如果返回值小于0,表示x小于y。

  • 客户化排序

使用客户化排序时,向TreeSet集合中加入的对象的类必须实现了java.util.Comparator<T>接口或Comparable接口,两个接口的作用是相同的,只是前者必须指定被比较对象类型。

如果加入的对象的类没有实现Comparable/Comparator<T>接口,会抛出异常“该类 cannot be cast to java.lang.Comparable”:

public class Demo {

public static void main(String[] args) {

Set<A> set=new TreeSet<>();

set.add(new A(8));

set.add(new A(7));

set.add(new A(6));

set.add(new A(9));

for(A a:set)

System.out.print(a.num+” “);

}

}

class A{

public int num;

public A(int num){

this.num=num;

}

}

值得注意的是对于已经存在于TreeSet中的对象,修改其中会引起compareTo()方法返回值改变的属性后,TreeSet不会对集合进行排序。例如如下代码:

class A implements Comparable{

public int num;

public A(int num){

this.num=num;

}

@Override

public int compareTo(Object o) {

A b=(A)o;

if(this.num>b.num){

return 1;

}else if(this.num<b.num){

return -1;

}else{

return 0;

}

}

}

public static void main(String[] args) {

Set<A> set=new TreeSet<>();

A a1=new A(8);

set.add(a1);

set.add(new A(7));

set.add(new A(6));

set.add(new A(9));

System.out.print(“n排序后的结果:”);

for(A a:set)

System.out.print(a.num+” “);

a1.num=100;

System.out.print(“n修改一个元素的属性后的结果:”);

for(A a:set)

System.out.print(a.num+” “); //不会改变已经排好的顺序

set.add(new A(99));

System.out.print(“n再新增元素后的结果:”);

for(A a:set)

System.out.print(a.num+” “);

}

可见TreeSet修改了元素的某个属性后,TreeSet不会重新排序。最适合TreeSet排序的是不可变类(即创建对象后,它们属性不能被修改)。

List(列表)

List的特征是其元素按照线性方式存储(即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的),集合中允许存放重复对象。主要的实现类:

ArrayList:

代表长度可变的数组。允许对元素进行快速的随机访问,但是向其中插入和删除元素的速度较慢。实现了RandomAccess接口,RandomAccess接口仅仅是标识该类具有良好的快速随机访问的性能。

LinkedList:

在实现中采用链表数据结构。对顺序访问做了优化,向List中插入和删除元素的速度较快,随机访问则相对较慢。LinkedList独有addFirst()、addLast()、getFirst()、getLast()、removeFirst()和removeLast()方法,这些方式可以将其作为堆栈、队列和双向队列使用。

  • 访问列表的元素

客户程序可以按照对象在集合中的索引位置来检索对象,如下代码:

List<Integer> list=new ArrayList<>();

list.add(3);

list.add(4);

list.add(3);

list.add(2);

for(int i=0;i<list.size();i++)

System.out.print(list.get(i)+” “);

运行结果

List的iterator()方法和Set的一样,也能返回Iterator对象,例如:

Iterator<Integer> it=list.iterator();

while(it.hasNext()){

System.out.print(it.next()+” “);

}

同样也可以用foreach,例如:

for(Integer i:list){

System.out.print(i+” “);

}

  • 为列表排序

List只能对加入其中的对象按照索引位置(即元素在List中的位置)进行排序,如果希望对List中的对象按照客户指定的方式排序,可以借助Comparator接口和Collections类。Collections类是Java集合类库中的辅助类,它提供的sort()静态方法用于对List中的对象进行排序:

  1. sort(List list):对list中的对象进行自然排序
  2. sort(List list,Comparator comparator):对List中的对象进行客户化排序,comparator参数指定排序方式。

List<Integer> list=new ArrayList<>();

list.add(3);

list.add(4);

list.add(3);

list.add(2);

Collections.sort(list);

for(Integer i:list)

System.out.print(i+” “);

排序后结果

  • ListIterator接口

List的listIterator()方法返回一个ListIterator对象,ListIterator接口继承了Iterator接口,此外还提供了专门操纵列表的方法:

  1. add():向列表中插入一个元素
  2. hasNext():判断列表中是否还有下一个元素
  3. hasPrevious():判断列表中是否还有上一个元素
  4. next():返回列表中的下一个元素
  5. previous():返回列表的上一个元素
  • 获得固定长度的List对象

java.util.Arrays类的asList()方法能够把一个Java数组包装为一个List对象,这个List对象代表固定长度的数组。所有对List对象的操作都会被作用到包装前的Java数组。看Arrays类的源码可以知道返回的List对象其实是Arrays类自定义的一个List集合实现类

Arrays的asList方法

由于数组的长度不能改变,因此调用该List对象的add()和remove()方法,会抛出java.lang.UnsupportedOperationException运行时异常:

  • 比较Java数组和各种List实现类的性能

除了ArrayList、LinkedList外,在JDK1.0时候有个Vector类,在JDK2.0时候也把其改为实现了List接口。可以写一个程序分别对数组、ArrayList、LinkedList和Vector进行随机访问、遍历操作和增删操作,比较这几种集合的性能,可以得出类似下图的表格:

可以看出,对Java数组进行随机访问和遍历操作具有最快速度;对LinkedList进行插入和删除操作具有最快的速度;对ArrayList进行随机访问也具有较快的速度。Vector类在各方面都没有突出的性能,属于历史集合类,已经不建议使用。

Queue(队列)

火车站售票大厅排队等待购票的现象就是队列的表现,后加入的人排在队列的末尾,排在队列头部的人优先购票后离开队列。Java中,java.util.Queue接口表示队列,特点是向末尾添加元素,从队列头部删除元素,队列中允许有重复元素。

  • 向Queue加入元素的方法
  1. boolean add(E e) ,向队列末尾添加元素,如果队列已满,会抛出IllegalStateException
  2. boolean offer(E e) ,向队列末尾添加元素,如果队列已满,会返回false
  • 从Queue中删除元素的方法
  1. E remove(),删除头部的元素,如果队列为空,抛出NoSuchElementException
  2. E poll(),删除头部的元素,如果队列为空,返回null
  • 从Queue中获取元素
  1. E element(),返回队列头部的元素,不删除它。如果队列为空,抛出NoSuchElementException
  2. E peek(),返回队列头部的元素,不删除它。如果队列为空,返回null

Deque(双向队列)

Deque接口是Queue接口的子接口,特点是在队列的头部或尾部都可以添加或删除元素。LinkedList类就实现了Deque接口。

  • 向Deque头部或尾部添加元素
  1. void addFirst(E e)
  2. void addLast(E e)
  3. void offerFirst(E e)
  4. void offerLast(E e)

如果队列已满,前两个方法抛出IllegalStateException,而后两个方法返回false。

  • 从Deque头部或尾部删除元素
  1. E removeFirst()
  2. E removeLast()
  3. E pollFirst()
  4. E pollLast()

如果队列为空,前两个方法抛出NoSuchElementException,后两个方法返回null。

  • 从Deque头部或尾部获取元素

E getFirst()

E getLast()

E peekFirst()

E peekLast()

如果队列为空,前两个方法抛出NoSuchElementException,后两个方法返回null。

PriorityQueue(优先级队列)

它会按照排序的方式对对了中元素进行排序和检索。因此加入到PriorityQueue中的对象必须实现Comparable接口。

值的注意的是,优先级队列使用Iterator遍历时,输出结果没有进行排序,而调用针对队列首尾的方法会进行排序。

Map(映射)

Map是一种把键对象和值对象进行映射的集合,它的每一个元素都包含一对键对象和值对象,而且值对象仍可以是Map类型,依此类推,可以形成多级映射。

向Map集合中加入元素时,必须提供一对键对象和值对象,从Map集合中检索对象时,只要给出键对象,就会返回对应的值对象。

加入和检索对象

Map集合中的键对象不允许重复,也就是说,任意两个键对象通过equals()方法比较的结果都是false。对于值对象则没有唯一性的要求。因此,可以将任意多个键对象映射到同一个值对象上:

Map<String,String> map=new HashMap<>();

map.put(“1″,”one”);

map.put(“1″,”Monday”);

map.put(“one”,”Monday”);

Set<Map.Entry<String,String>> set=map.entrySet();

for(Map.Entry entry:set)

System.out.println(entry.getKey()+”:”+entry.getValue());

上面代码由于第一次和第二次加入Map中的对象都为“1”,因此第一次加入的值对象将别覆盖,Map集合中最后只有两个元素,输出结果为

大家注意到上面代码中调用了Map的entrySet()方法,返回了一个Set集合,其中的元素类型为Map.Entry,每个元素代表Map中的一对键与值。Map.Entry对象的getKey()方法返回键,getValue()方法返回值。

Map集合有两个实现类:HashMap和TreeMap。

  • HashMap

按照哈希算法来存取键对象,有很好的存取性能,和HashSet一样,为了保证HashMap能正常工作,要求当两个键对象通过equals()方法比较为true时,这两个键对象的hashCode()方法返回的哈希码也一样。

  • TreeMap

实现了SortedMap接口,能对键对象进行排序。和TreeSet一样,TreeMap也支持自然排序和客户化排序两种方式。

  • HashSet和HashMap的负载因子

它们都是运用了哈希算法来存取元素。 哈希表 中每个位置也被称为桶(bucket),在发生哈希冲突的时候,在桶中以链表的形式存放多个元素。

HashSet和HashMap存放数据时采用的数据结构

HashSet和HashMap都具有以下特性:

容量(capacity):哈希表中桶的数量。例如上图中共有6个桶,容量为6。

  1. 初始容量(initial capacity):创建HashSet和HashMap对象时桶的数量。在HashSet和HashMap都提供了设置初始容量的构造方法。
  2. 大小(size):元素的数目。上图中共有13个元素,因此size为13。
  3. 负载因子(load factor):等于size/capacity。负载因子为0,表示空的哈希表;负载因子为0.5,表示半满的哈希表,以此类推。轻负载的哈希表具有哈希冲突少,适合插入和查找的优点(使用Iterator遍历的速度较慢)。当哈希表的负载达到用户设定的负载因子时,HashSet和HashMap会自动成倍的增加容量(即桶的数量),并且重新分配原有元素的位置,这是耗性能的操作。

HashSet和HashMap的默认负载因子时0.75,表示当哈希表有3/4被填满,会自动成倍的增加哈希表的容量。这个默认值很好的权衡了时间和空间成本,因为负载因子过高的话,虽然会降低对内存空间的需求,但是会提高查找数据的时间开销,而查找是最频繁的操作,在HashMap的get()和put()方法中都涉及查找操作;负载因子设的过低,也会有相反的问题。

集合实用类:Collections

java.util.Collections的一部分方法专门用于操纵List类型集合,还有一部分静态方法可用于操纵所有的Collection类型或Map类型集合。

适用于List的方法:

  • copy(List dest,List src): 把一个List中的元素复制动另一个List。
  • fill(List list,Object o): 向列表中添加元素。
  • sort(List list): 把List中的元素进行自然排序。
  • binarySearch(List list,Object key): 查找List中与给定对象相同的元素。在调用该方法时,必须保证List中的元素已经自然排序,这样才能找到正确的结果。
  • binarySearch(List list,Object key,Comparator c): 查找List中与给定对象Key相同的元素,Comparator类型的参数指定比较规则。在调用该方法时,必须保证List中的元素已经按照Comparator类型的参数的比较规则排序,这样才能得到正确结果。
  • shufle(List list): 对List中的元素进行随机排序。

适用于Collection类型和Map类型的方法:

  • Object max(Collection coll): 返回集合中最大的元素,采用自然排序的规则。
  • Object max(Collection coll,Comparator comp): 返回集合中的最大元素,Comparator类型的参数指定比较规则。
  • Object min(Collection coll): 返回集合中的最小元素,采用自然排序的比较规则。
  • Object min(Collection coll,Comparator comp): 返回集合中的最小元素,Comparator类型的参数指定比较规则。
  • Set singleton(Object o): 返回一个不可改变的Set集合,它只包含一个方法参数指定的对象。
  • List singletonList(Object o): 返回一个不可改变的List集合,它只包含一个方法参数指定的对象。
  • Map singletonMap(Object key,Object value): 返回一个不可改变的Map集合,它只包含方法参数指定的一对键和值。
  • Collection synchronizedCollection(Collection c): 在原来集合的基础上,返回支持同步的(即 线程安全 的)集合。
  • List synchronizedList(List list): 在原来List的基础上,返回支持同步的(即线程安全的)List集合。
  • Map synchronizedMap(Map map): 在原来Map的基础上,返回支持同步的(即线程安全的)Map集合。
  • Set synchronizedSet(Set set): 在原来Set的基础上,返回支持同步的(即线程安全的)Set集合。
  • Collection unmodifiableCollection(Collection c): 在原来集合的基础上,返回不允许修改的集合视图。
  • List unmodifiableList(List list): 在原来List集合的基础上,返回不允许修改的List集合视图。
  • Map unmodifiableMap(Map map): 在原来Map集合的基础上,返回不允许修改的Map集合视图。
  • Set unmodifiableSet(Set set): 在原来Set集合的基础上,返回不允许修改的set集合视图。

线程安全的集合

在Java集合框架中,Set、List、Queue和Map的实现类都没有采用同步机制。在单线程中,这种操作方式会提高操作集合的效率,虚拟机不必因为管理同步锁而产生额外的开销。在多线程环境中,可能会有多个线程同时操作一个集合,比如一个线程在为集合排序,而另一个线程在不断的往里加入元素。这就会产生并发问题,为了避免,可以采用如下方法:

  • 在程序中对可能产生并发问题的代码进行同步
  • 利用Collections的synchronizedXXX()方法获得原始集合的同步版本。需要注意的是,如果一个线程操作集合的同步版本,另一个线程操纵原始的集合,那么还会导致并发问题。为了避免这种情况,可以使用java.util.concurrent并发包提供的线程安全集合,如ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListSet和ConcurrentLinkedQueue。
  • 如果集合的元素不允许被修改,可以用Collections的unmodifiableXXX()方法来生成原始的集合视图,让线程只访问这个视图,可以避免集合被线程错误的修改,而且由于不用采用同步措施,可以提高并发性能。

集合与数组的互换

集合和数组都用来存放多个元素,它们之间可以通过特定的方式互换。

  • 把数组转换为集合

java.util.Arrays类是一个数组使用类,它的asLit()方法能把数组转换为一个List对象,例如:

Integer [] array={11,12,13};

List<Integer> list=Arrays.asList(array);

此外,在通过Arrays.asList()方法得到一个List对象后,还可以把其转换为其他类型的集合。因为大多数集合都如下形式的构造方法,可以将参数c指定的集合中元素复制到新集合中:

HashSet(Collection<? extends E> c)

TreeSet(Collection<? extends E> c)

ArrayList(Collection<? extends E> c)

LinkedLit(Collection<? extends E> c)

  • 把集合转换为数组

java.util.Collection接口定义了toArray()方法,能把集合转换为数组,它有两种重载形式:

  1. Object [] toArray(): 返回Object[]类型数组
  2. <T> T[] toArray(T[] a): 返回泛型标记<T>指定类型的数组,该方法参数的数组个数并无意义,仅仅用来指定返回数组的类型,如“list.toArray(new Integer[0])”表明toArray()方法会返回一个Integer[]类型的数组

集合的批量操作

如果需要一次处理大批量的数据,可以调用集合的支持批量操作的方法。在Collection接口中定义了如下方法:

  • boolean retainAll(Collection<?> c): 修改当前集合,在集合中保留那些同时位于参数c集合中的元素,删除其余。如果集合最终做了改动,返回true。
  • boolean removeAll(Coolection<?> c): 删除当前集合中那些同时位于c集合中的元素。
  • boolean addAll(Collection<? extends E> c): 把参数c集合中的元素加入到当前集合中。
  • boolean containsAll(Collection<?> c): 判断当前集合中是否存在参数c集合中的元素。

此外,List接口还有一个用于获得子列表视图的方法:

  • List<E> subList(int fromIndex,int toIndex): fromIndex参数和toIndex参数分别指定元素的起始索引和结束索引。索引是含头不含尾的。值的注意的是,删除子列表视图中的元素,原集合中的元素也会被删除。

历史集合类

在早期的JDK1.0版本中,代表集合的类只有Vector、Stack、Enumeration、Hashtable、Properties和BitSet类。直到JDK2.0版本开始,才出现了Collection、Set、Map接口,以及各种实现类,它们构成了比较完整的Java集合框架,在JDK1.5版本中,又增加了Queue接口及各种实现类。我们把JDK1.0版本中的集合类称为历史集合类。

枚举类型的适配器EnumSet类和EnumMap类

  • java.util.EnumSet类: 把枚举类型转换为集合类型。它的静态的allOf()方法能把枚举类所有的常量实例存放到一个EnumSet类型集合中,然后返回这个集合

enum Colour{RED,BLUE,YELLOW,GREEN}

public static void main(String[] args) {

EnumSet<Colour> enumSet=EnumSet.allOf(Colour.class);

System.out.println(enumSet);

}

运行结果:

  • java.util.EnumMap类: 把枚举类型转换为映射类型。

public class Demo {

enum Colour{RED,BLUE,YELLOW,GREEN}

public static void main(String[] args) {

EnumMap<Colour,String> enumMap=new EnumMap<Colour, String>(Colour.class);

System.out.println(enumMap);

enumMap.put(Colour.RED,”red”);

enumMap.put(Colour.BLUE,”blue”);

System.out.println(enumMap);

}

}

运行结果:

目录:

文章来源:智云一二三科技

文章标题:Java之集合

文章地址:https://www.zhihuclub.com/169437.shtml

关于作者: 智云科技

热门文章

评论已关闭

2条评论

  1. If so, cerebrovascular concentrations of sex steroids may be different from circulating levels, thus confounding interpretations based on plasma measurements

  2. In the racehorse, a major player is the Enterobacteria phage PhiX174, which is a bacterial virus that protects the horse against E coli

网站地图