13.2 具体的集合

  • Set(集):集合中的元素不按特定方式排序,并且没有重复对象。他的有些实现类能对集合中的对象按特定方式排序。
  • List(列表):集合中的元素按索引位置排序,可以有重复对象,允许按照对象在集合中的索引位置检索对象。
  • Map(映射):集合中的每一个元素包含一对键对象和值对象,集合中没有重复的键对象,值对象可以重复。他的有些实现类能对集合中的键对象进行排序。

1、collection接口

  Collection是整个类集中单值保存的最大父接口。

1

Public boolean add(E e)

普通

向集合中添加

2

Public boolean addAll(Collection<? extends E> c)

追加一个集合

3

Public void clear()

4

Public boolean contains(Object o)

5

Public boolean isEmpty

6

Public boolean remove(Object o)

7

Pulic int size()

8

Public Object[] toArray()

将集合变为字符数组

9

Public Iterator<E> iterator()

只有add和Iterator会常常使用,但是要记住contains和remove方法需要Object的支持。

现在基本不使用collection接口,而是使用list和set这两个接口。

13.2.1 链表

从数组的中间位置删除一个元素要付出很大的代价,因为数组中处于被删除元素之后的元素都要向数组的前端移动,在数组中间的位置插入一个元素也是如此。

  从链表中删除一个元素是一个非常轻松操作,急需要对被删除元素附近的节点更新一下即可。

List<String> staff = new LinkList<>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
Iterator iter = staff.iterator();
String first = iter.next();
String second = iter.next();
iter.remove();

  链表是一个有序集合,每个对象的位置十分重要。LinkList.add方法将对象添加到链表的尾部,但是,常常需要将元素添加到链表的中间。由于迭代器是描述集合中位置的,所以这种依赖于位置的add方法将由迭代器负责。只有对自然有序的集合使用迭代器添加元素才有实际意义。例如,下一节中讨论的集(set)类型,其中的元素完全无序。因此,在Iterator接口中就没有add方法,相反的,集合类库提供了子接口ListIterator,其中包含add方法。

  Collection接口中声明了很多对链表操作的有用方法,其中大部分方法都是在LinkList类的超类AbstractCollection中实现的。例如,toString方法调用了所有元素的toString,并产生了一个很长的格式为[A,B,C]的字符串。这为调试工作提供了便利。可以使用contaions方法检测某个元素是否出现在链表中。例如,如果链表中包含一个等于“Harry”的字符串,调用staff.contains("Harry")后将会返回true。

链表不支持快速地随机访问

  如果要查看链表的第n个元素,就必须从头开始,超过n-1个元素,没有捷径可走,所以在采用整数索引访问元素的时候,一般不选用链表。

  尽管如此,LinkList中提供了一个用来访问某个特定元素的get方法:

LinkList<String> list = ... ;
String obj = list.get(n);

  get方法的效率不高,而且非常不建议使用get方法对链表进行遍历。

  列表迭代器接口中有一种方法,可以告知当前位置的索引。实际上,Java迭代器指向两个元素之间的位置,所以可以 同时产生两个索引:nextIndex方法返回下一次调用next时返回元素的整数索引;previousIndex方法返回下一次调用previous方法时返回元素的整数索引。当然,这个索引只比nextIndex返回的索引值小1.这两个方法的效率非常高,因为迭代器保持着当前位置的计数值,

  如果一个整数索引是n,则list。listIterator(n)将返回一个迭代器,这个迭代器指向索引为n的元素前面的位置,也就是说,调用next与调用list.get(n)会产生同一个元素,只是get方法效率比较低。

  如果链表中只有很少的几个元素,就完全不必担心get方法和set方法的开销带来的烦恼。

  为什么优先使用链表?唯一的理由是尽可能减少在列表中间插入或删除元素所付出的代价。如果列表中只有少数几个元素,就完全可以使用ArrayList。

如果需要对集合进行随机访问,就使用数组或者ArrayList,而不是使用链表。

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class list_13_1 {
	public static void main(String args[])
	{
		List<String> a = new LinkedList<>();
		a.add("Amy");
		a.add("Carl");
		a.add("Erica");
		
		List<String> b = new LinkedList<>();
		b.add("Bob");
		b.add("Doug");
		b.add("Frances");
		b.add("Gloria");
		
		ListIterator<String> aIter = a.listIterator();
		Iterator<String> bIter = b.listIterator();
		
		//b非空
		while(bIter.hasNext())
		{
			//跳过一个
			if(aIter.hasNext()) aIter.next();
			//每隔一个,将b中的元素加入到a中
			aIter.add(bIter.next());
		}
		
		System.out.println(a);
		
		bIter = b.iterator();
		while(bIter.hasNext())
		{
			bIter.next();
			if(bIter.hasNext())
			{
				//每隔一个,删除一个b中的元素
				bIter.next();
				bIter.remove();
			}
		}
		
		System.out.println(b);
		
		a.removeAll(b);
		
		System.out.println(a);
	}

}

   创建两个链表,将他们合并在一起,然后从第二个链表中每隔一个元素删除一个元素,最后测试removeAll方法。 

13.2.3 散列表

链表和数组可以按照人们的意愿排列元素的次序。但如果要查询某个元素,却又忘记了位置,就必须访问所有的元素,直到找到为止。如果集合中的元素较多,就会消耗较长的时间。如果不在意元素的顺序,可以有几种快速查找元素的数据结构,缺点就是无法控制元素的位置。他们将按照有利于操作目的的原则组织数据。

散列表(hash table)可以快速查找所需要的对象,散列表为每一个对象计算一个整数,称为散列码(hash code)。散列码是由对象的实例域产生的一个整数,更准确的说,具有不同数据域的对象产生不同的散列码。

  如果自己定义类,就需要负责实现这个类的hashCode方法,自己实现的hashCode方法应该与equals方法兼容,即如果a.equals(b)为true,则a与b必须具有相同的散列码。

  在Java中,散列表用链表数组实现,每个列表称为桶(bucket)。要想查找表中对象的位置,就需要计算它的散列码,然后与桶中的总数取余,所得到的结果就是保存这个元素的桶的索引。例如,若对象的散列码是76268,并且有128个桶,对象应该保存在第108号桶中(76268除以128余108)。如果这个桶中没有其他元素,可以直接将这个元素插入到桶中,有时候可能遇到桶被占满的情况,这种现象称为散列冲突(hash collision)。如果散列码是合理且随机分布的,桶的数目也足够大,需要比较的次数就会很少。

  如果大致知道需要插入多少个元素到散列表中,就可以设置桶的数量,通常将桶的数量设置为预计元素个数的75%~150%。

  如果散列表太满,就需要再散列(rehashed)。如果要对散列表再散列,就需要创建一个桶更多的表,并将所有的元素都插入到这个表中,然后丢弃原来的表。这个装填因子决定了在什么时候对散列表进行再散列。

  散列表可以实现几个重要的数据结构,其中最简单的是set类型。set是没有重复元素的元素集合。set的add方法首先在集合中查找要添加的对象,如果不存在,就将这个对象添加进去。

  java集合类库提供了一个HashSet库,它实现了基于散列表的集。可以用add方法添加元素。contains方法被重新定义了,用来快速地查看是否某个元素已经出现在集中。它只是在某个桶中查找元素,而不必查看集合中的所有元素。

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

public class set_13_2 {
	public static void main(String args[])
	{
		Set<String> words = new HashSet();
		long totalTime = 0;
		
		Scanner in = new Scanner(System.in);
		while(in.hasNext())
		{
			String word = in.next();
			long callTime = System.currentTimeMillis();
			words.add(word);
			callTime = System.currentTimeMillis() - callTime;
			totalTime += callTime;
			
		}
		
		Iterator<String> iter = words.iterator();
		for(int i = 0; i <= 20 && iter.hasNext(); i++)
		{
			System.out.println(iter.next());
		}
		System.out.println("...");
		System.out.println(words.size() + " distinct words" + totalTime + "milliseconds");
		
	}

  这个程序将读入输入的所有单词,并且将它们添加到散列集中,然后遍历散列集中的不同单词,最后打印出单词的数量,单词以随机的顺序出现。

13.2.4 树集

TreeSet类与散列表十分类似,不过,它比散列表有所改进。树集是一个有序集合(sorted collection)。可以以任意顺序将元素插入到集合中。在对集合进行遍历的时候,每个值将自动地按照排序后的顺序呈现。

SortedSet<String> sorter = new TreeSet<>();
sorter.add("Bob");
sorter.add("Amy");
sorter.add("Carl");
for(String s:sorter)
{
      System.out.println(s);  
}

  这时候,每个值都会按照顺序打印出来:Amy、Bob、Carl。排序是按照树结构来实现的(在这里使用的是红黑树red-black tree),每次讲一个数据添加到树中,都被放置在正确的排序位置上,因此,迭代器总是以排好序的顺序访问每个元素。

13.2.5 对象的比较

  TreeSet如何知道希望元素怎样排列呢?在默认情况下,树集假定插入的元素实现了Comparable接口。

public interface Comparable<T>
{
    int compareTo(T other);
}

  如果a和b相等,调用a.compareTo(b)一定返回0;

  如果排序后a位于b之前,则返回负值;

  如果排序后a位于b之后,则返回正值。

  有些标准的java平台类实现了Comparable接口,例如,String类。这个类的compareTo方法依据字典序对字符串进行比较。

  如果要插入自定义的对象,就必须通过实现Comparable接口自定义排列顺序,在Object类中,没有提供任何compareTo接口的默认实现。

  如下代码展示了如何使用部件编号对Item对象进行排序:

class Item implements Comparable<Item>
{
    public int compareTo(Item other)
    {
        return partNumber - other.partNumber;    
    }  
}

  如果对两个正整数进行比较,可以直接返回它们的差。

  如果第一项位于第二项之前,就返回负值;

  如果第一项位于第二项之后,就返回正值。

只有两个正整数进行比较的时候,才能使用上述的方法进行,直接返回它们的差值,如果x是一个较大的正整数,而y是一个绝对值较大的负整数,x - y可能会溢出。

  然而,使用Comparable接口定义排列顺序显然有局限性,对于一个给定的类,只能实现这个接口一次。如果在一个集合中需要按照部件编号进行排序,在另一个集合中却要按照描述信息进行排序,该怎么办?

  在这种情况下,可以通过将Comparator对象传递给TreeSet构造器来告诉树集使用不同的比较方法。Comparator接口声明了一个带有两个显式参数的compare方法。

13.2.8 映射表

  集是一个集合,它可以快速查找现在的元素,但是,要查看一个元素,需要有要查找元素的精确地副本,这不是一种非常通用的查找方式。通常,我们知道某些键的信息,并想要查找与之对应的元素。映射表(map)数据结构就是为此设计的。映射表用来存放键/值对。如果提供键。就能够查到值。例如,键为员工ID,值为Employee对象。

  Java类库为映射表提供了两个通用的实现:HashMap和TreeMap,这两个类都实现了Map接口。

  散列映射表对键进行散列,树映射表用键的整体顺序对元素进行排序,并将其组织成搜索树。散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。

与集一样,散列稍微快一些,如果不需要按照排列顺序访问键,就最好选用散列。

  每当往映射表中添加对象的时候,必须同时提供一个键。在这里,键是一个字符串,对应的值是Employee对象。

  要搜索一个对象,必须提供一个键。

String s = "987-98-9996";
e = staff.get(s);

  如果在映射表中没有与给定键对应的信息,get将返回null。

键必须是唯一的。

如果对同一个键两次调用put方法,第二个值就会取代第一个值。实际上,put将返回这个键参数存储的上一个值。

  remove方法用于从映射表中删除给定键对应的元素;size方法用于返回映射表中的元素数。

  键集    Set<K> keySet()

  值集合     Collection<K> values()

  键/值对集   Set<Map.Entry<K,V>> entrySet()

  keySet既不是HashSet,也不是TreeSet,而是实现了Set接口的某个其他类的对象。Set接口扩展了Collection接口。因此,可以与任何集合一样使用了keySet。

Set<String> keys = map.keySet();
for(String key:keys)
{
     ...  
}

  如果要同时查看键和值,就可以通过枚举各个条目(entries)查看,以避免对值进行查找。

for(Map.Entry<String, Employee> entry:staff.entrySet())
{
    String key = entry.getKey();
    String value = entry.getValue();
    ...  
}

  如果调用迭代器的remove方法,实际上是从映射表中删除了键以及对应的值。但是,不能将元素添加到键集的视图中。如果只添加键而不添加值是毫无意义的。如果视图调用add方法,将会抛出UnsupportedOperationException异常。

package map_13_6;

import java.util.HashMap;
import java.util.Map;

public class MapTest {
	public static void main(String args[])
	{
		//String n, double s, int year, int month, int day
		Map<String, Employee> staff = new HashMap<>();
		staff.put("1", new Employee("Amy Lee", 20000, 1993, 12, 1));
		staff.put("2", new Employee("Allen Iverson", 30000, 1983, 12, 1));
		
		System.out.println(staff);
		staff.remove(1);
		
		//替换掉“1”
		staff.put("1", new Employee("Lebron James", 30000, 1983, 2, 23));
		
		System.out.println(staff);
		
		System.out.println(staff.get("2"));
		
		for(Map.Entry<String, Employee> entry:staff.entrySet())
		{
			String key = entry.getKey();
			Employee value = entry.getValue();
			
			System.out.println("key = " + key + ",value = " + value);
		}
	}
}

  首先将键值对添加到映射表中,然后从映射表中删除掉一个键值对,接下来修改某一个键对应的值,并调用get方法查看这个值。最后,对条目进行迭代输出。

{1=map_13_6.Employee@42a57993, 2=map_13_6.Employee@75b84c92}
{1=map_13_6.Employee@6bc7c054, 2=map_13_6.Employee@75b84c92}
map_13_6.Employee@75b84c92
key = 1,value = map_13_6.Employee@6bc7c054
key = 2,value = map_13_6.Employee@75b84c92

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【每日一题】 1673: 算法2-1:集合union

1231
来自专栏数据结构与算法

P1341 无序字母对

题目描述 给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。...

3508
来自专栏desperate633

LintCode 二分查找题目分析代码

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组...

892
来自专栏Coding迪斯尼

面试算法:在未知长度的排序数组中进行快速查找

1112
来自专栏Java帮帮-微信公众号-技术文章全总结

第十八天 集合-泛型&list接口&set接口【面试+工作】

泛型的使用:一般在创建对象时,将未知的类型确定具体的类型。当没有指定泛型时,默认类型为Object类型。

1092
来自专栏黑泽君的专栏

Java集合学习总结

863
来自专栏编程心路

在ArrayList的循环中删除元素,会不会出现问题?

在 ArrayList 的循环中删除元素,会不会出现问题?我开始觉得应该会有什么问题吧,但是不知道问题会在哪里。在经历了一番测试和查阅之后,发现这个“小”问题并...

3932
来自专栏kevindroid

StringBuilder,String与StringBuffer 的异同

1435
来自专栏Java技术栈

Java集合从菜鸟到大神演变

先来看一张集合概况图,这里从上到下列举了几个最经常用的集合 ? 1、集合接口 java.util.Collection 是一个集合接口。它提供了对集合对象进行基...

4256
来自专栏Python爱好者

Java基础笔记14

1143

扫码关注云+社区