Java基础教程

索迪教育Java编程技术基础第十一章Java集合框架索迪教育上章回顾了解多线程的概念掌握如何创建线程掌握实现线程同步的方法了解死锁的概念掌握使用wait和notify在线程之间进行通信索迪教育我们的目标解释集合框架的体系结构使用集合类和接口索迪教育Java2集合框架简介集合将多个元素组成一个单元的对象用于存储、检索、操纵和传输数据集合框架提供了一组精心设计的接口和类，它们以单个单元即集合的形式存储和操作数据组计算机数据结构的许多抽象数据类型如映射(map)、集(set)、列表(list)、树(tree)、数组(array)、散列表(hashtable)和其它集合，在框架中提供了方便的应用接口组件包括接口、实现和算法索迪教育集合接口的体系结构集合框架由一组用来操作集合对象的接口组成。不同接口描述不同类型的组集合接口的体系结构如下图所示：CollectionSetListSortedSetMapSortedMapIteratorListIterator索迪教育集合接口的特点Collection接口是一组允许重复的对象。Set接口继承Collection，但不允许重复。SortedSet接口继承Set，但升序排列List接口继承Collection，允许重复，并引入位置下标。Iterator接口是一组用于列举的对象ListIterator接口继承Iterator，引入位置下标，支持双向访问Map接口既不继承Set也不继承Collection，是键-值关联的实现SortedMap接口继承Map，但升序排列索迪教育Collection接口集合框架的根所有集合都通用的方法为：方法返回描述contains(Object)boolean判别当前集合是否包含指定对象equals(Object)boolean判别当前集合是否与指定对象相同iterator()Iterator返回一个可向后检索的迭代集合size()int返回元素总数hashcode()int返回hashcode（混列码）数clear()void清除所有元素add(Object)boolean添加元素addAll(Collection)boolean把指定集合所有元素加到当前集合索迪教育Iterator接口该接口定义了如下功能：通过调用next()方法，可以得到序列中的下一元素；如果序列处于初始状态则返回第一个元素通过调用hasNext()方法，可以查看序列的后面是否还有元素通过调用remove()方法，可以把序列上当前元素删除，如果序列不支持这一方法，会抛出下面的异常：Java.lang.UnsupportedOperationExceptionCollectioncollection=...;Iteratoriterator=collection.iterator();while(iterator.hasNext()){Objectelement=iterator.next();if(removalCheck(element)){iterator.remove();}}索迪教育Set接口扩展了Collection接口不允许重复元素未定义自己的任何方法必须对add()、equals()和hashcode()方法添加了限制HashSet和TreeSet是两个Set实现类HashSet实质上是Set对HashMap适配索迪教育SortedSet接口扩展了Set接口元素按升序排序抛出的重要异常为：ClassCastException不相容NullPointerException不能为空索迪教育List接口是具有顺序的集合扩展了Collection接口元素可以通过其整型下标插入列表中或从列表中访问可以包含重复元素List接口中的方法可分类为：定位方法get()、set()、add()、remove()、addAll()搜索方法indexOf()和lastindexOf()ListIterator方法listIterator()和subList()索迪教育Map接口将键映射至值的对象每个键最多都只能映射至一个值基本操作方法：put()、get()、remove()、containsKey()、containsValue()、size()、isEmpty()批操作方法：putAll()、clear()集合视图：keySet()方法获取的是Map中的关键字的一个Setvalues()方法返回映射中值的CollectionentrySet()返回一组实现了Map.Entry接口的对象的Set，Set中的每一个元素都代表了Map中的一个独立的关键字/值对索迪教育实现用于存储集合的实际数据对象重要集合类为：AbstractCollection类提供Collection接口的骨架实现AbstractList类提供List接口的骨架实现AbstractSequentialList类是List接口的实现LinkedList类提供多个方法，用于在列表开始处和结尾处获得、删除和插入元素ArrayList类是List接口的可调整大小数组实现AbstractSet类提供Set接口的骨架实现HashSet类为Set基本操作提供固定时间性能TreeSet类确保排序集将按元素升序实现了SortedSetHashMap类为Map基本操作提供固定时间性能TreeMap类确保排序集将按元素升序SortedMap索迪教育集合类与接口常用集合类VectorArrayListStackHashtableHashMap常用接口IteratorEnumeration索迪教育Vector实现可增加的对象数组组件可以使用整型下标访问维护容量和增量系数构造函数Vector()Vector(Collectionc)Vector(intcap)Vector(intcap,intinc)常用方法参见JDK帮助文档索迪教育ArrayList构造函数ArrayList()ArrayList(intinitialCapacity)常用方法参见JDK帮助文档索迪教育Vector与ArrayList的区别同步性Vector是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的，因此ArrayList中的对象并不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销。数据增长从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。索迪教育Vector与ArrayList的区别(续)使用模式在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。为什么会这样呢？以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。索迪教育Stack表示后进先出的对象堆栈包含一个构造器，即用于创建空堆栈的Stack()常用方法push(Object)pop()peek()Java类库中，Stack类是继承Vector类的这种继承合理吗？索迪教育Hashtable以键-值对的形式存储数据键被散列，然后散列码被用作存储值的位置的下标对象应覆盖Object类的hashCode()和equals()方法构造函数Hashtable()Hashtable(intcap)Hashtable(intcap,floatload)常用方法参见JDK帮助文档索迪教育HashMap构造函数HashMap()HashMap(intinitialCapacity)HashMap(intinitialCapacity,floatloadFactor)常用方法参见JDK帮助文档索迪教育关于哈希表散列表，又称为哈希表，是线性表中一种重要的存储方式和检索方法。在散列表中，可以对节点进行快速检索。散列表算法的基本思想是：由结点的关键码值决定结点的存储地址，即以关键码值k为自变量，通过一定的函数关系h（称为散列函数），计算出对应的函数值h(k)来，将这个值解释为结点的存储地址，将结点存入该地址中，检索时，根据要检索的关键码值，用同样的散列函数计算出地址，然后，到相应的地址中去获取要找的结点数据。因此，散列表有一个重要特征：平均检索的长度不直接依赖于表中元素的个数。散列表最重要的一个指标是负载因子，即散列表中结点数目与表中能容纳的总结点数的比值，它描述了散列表的饱和程度，负载因子越接近1.0，内存的使用效率越高，元素的寻找时间越长，同样，负载因子越接近0.0，元素的寻找时间越短，但内存的浪费越大。Hashtable类缺省的负载因子为0.75索迪教育Hashtable与HashMap的区别1.HashTable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。2.HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。3.HashTable有一个contains(Objectvalue)，功能和containsValue(Objectvalue)功能一样。4.HashTable使用Enumeration，HashMap使用Iterator。以上只是表面的不同，它们的实现也有很大的不同。5.HashTable中hash数组默认大小是11，增加的方式是old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。6.哈希值的使用不同，HashTable直接使用对象的hashCode，而HashMap重新计算hash值，而且用与代替求模索迪教育Iterator与Enumeration的区别Iterator模式Iterator模式用来规格化对某一数据结构的遍历接口。其实在老版本的JDK中也有类似的概念，被称为Enumeration。Iterator其实与Enmeration功能上很相似，只是多了删除的功能。用Iterator不过是在名字上变得更为贴切一些。模式的另外一个很重要的功用，就是能够形成一种交流的语言（或者说文化）。有时候，你说Enumeration大家都不明白，说Iterator就都明白了。索迪教育算法类CollectionsCollections类中的静态方法包括用于排序、搜索、混排和数据操纵的方法这些方法的第一个参数是要在其中执行操作的集合抛出的重要异常为ClassCastExceptionUnSupportedOperationException索迪教育只读集合把所有必要的元素都添加到集合后，为避免意外的修改集合，以只读方式处理该集合会比较方便。Collections类提供了六种工厂方法支持该功能，Collection、List、Map、Set、SortedMap和SortedSet每个一种。Collectionunmodifiab