索迪教育
Java编程技术基础第十一章 Java 集合框架索迪教育上章回顾
了解多线程的概念
掌握如何创建线程
掌握实现线程同步的方法
了解死锁的概念
掌握使用 wait 和 notify 在线程之间进行通信索迪教育我们的目标
解释集合框架的体系结构
使用集合类和接口索迪教育
Java2 集合框架简介
集合
将多个元素组成一个单元的对象
用于存储、检索、操纵和传输数据
集合框架
提供了一组精心设计的接口和类，它们以单个单元即集合的形式存储和操作数据组
计算机数据结构的许多抽象数据类型如映射 (map)、
集 (set)、列表 (list)、树 (tree)、数组 (array)、散列表 (hashtable)和其它集合，在框架中提供了方便的应用接口
组件包括接口、实现和算法索迪教育集合接口的体系结构
集合框架由一组用来操作集合对象的接口组成。不同接口描述不同类型的组
集合接口的体系结构如下图所示：
Collection
Set List
SortedSet
Map
SortedMap
Iterator
ListIterator
索迪教育集合接口的特点
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 返回 hash code（混列码）数
clear() void 清除所有元素
add(Object) boolean 添加元素
addAll(Collection) boolean 把指定集合所有元素加到当前集合索迪教育
Iterator 接口
该接口定义了如下功能：
通过调用 next() 方法，可以得到序列中的下一元素；如果序列处于初始状态则返回第一个元素
通过调用 hasNext() 方法，可以查看序列的后面是否还有元素
通过调用 remove() 方法，可以把序列上当前元素删除，如果序列不支持这一方法，会抛出下面的异常：
Java.lang.UnsupportedOperationException
Collectioncollection=...;
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(Collection c)
Vector(int cap)
Vector(int cap,int inc)
常用方法
参见 JDK帮助文档索迪教育
ArrayList
构造函数
ArrayList()
ArrayList(int initialCapacity)
常用方法
参见 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(int cap)
Hashtable(int cap,float load)
常用方法
参见 JDK帮助文档索迪教育
HashMap
构造函数
HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity,float loadFactor)
常用方法
参见 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(Object value)，功能和
containsValue(Object value)功能一样。
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 每个一种。
Collection unmodifiableCollection(Collection collection)
List unmodifiableList(List list)
Map unmodifiableMap(Map map)
Set unmodifiableSet(Set set)
SortedMap unmodifiableSortedMap(SortedMap map)
SortedSet unmodifiableSortedSet(SortedSet set)
一旦您填充完集合，用只读引用替代原始引用。如果不替代原始引用，那么集合就不是只读的，因为您仍然可以使用原始引用修改集合。
索迪教育线程安全集合
早期集合类和集合框架中新的实现的差别在于新类不是线程安全的。
设计者采用这种线程安全方法是让您只在需要时才使用同步，
使每项工作快得多。
但如果，您正将集合用于多个线程能够同步修改集合的多线程环境，修改就必须同步进行。
Collections 类有能力用另一组的六个方法把现有的集合包装成同步集合：
Collection synchronizedCollection(Collection collection)
List synchronizedList(List list)
Map synchronizedMap(Map map)
Set synchronizedSet(Set set)
SortedMap synchronizedSortedMap(SortedMap map)
SortedSet synchronizedSortedSet(SortedSet set)
索迪教育集合框架的优点
提高程序速度和质量
允许无关 API 之间的互操作性
减少编程工作
方便扩展或改写集合
减少设计新 API 的工作索迪教育本章小结
解释集合框架的体系结构
使用集合类和接口
Java编程技术基础第十一章 Java 集合框架索迪教育上章回顾
了解多线程的概念
掌握如何创建线程
掌握实现线程同步的方法
了解死锁的概念
掌握使用 wait 和 notify 在线程之间进行通信索迪教育我们的目标
解释集合框架的体系结构
使用集合类和接口索迪教育
Java2 集合框架简介
集合
将多个元素组成一个单元的对象
用于存储、检索、操纵和传输数据
集合框架
提供了一组精心设计的接口和类，它们以单个单元即集合的形式存储和操作数据组
计算机数据结构的许多抽象数据类型如映射 (map)、
集 (set)、列表 (list)、树 (tree)、数组 (array)、散列表 (hashtable)和其它集合，在框架中提供了方便的应用接口
组件包括接口、实现和算法索迪教育集合接口的体系结构
集合框架由一组用来操作集合对象的接口组成。不同接口描述不同类型的组
集合接口的体系结构如下图所示：
Collection
Set List
SortedSet
Map
SortedMap
Iterator
ListIterator
索迪教育集合接口的特点
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 返回 hash code（混列码）数
clear() void 清除所有元素
add(Object) boolean 添加元素
addAll(Collection) boolean 把指定集合所有元素加到当前集合索迪教育
Iterator 接口
该接口定义了如下功能：
通过调用 next() 方法，可以得到序列中的下一元素；如果序列处于初始状态则返回第一个元素
通过调用 hasNext() 方法，可以查看序列的后面是否还有元素
通过调用 remove() 方法，可以把序列上当前元素删除，如果序列不支持这一方法，会抛出下面的异常：
Java.lang.UnsupportedOperationException
Collectioncollection=...;
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(Collection c)
Vector(int cap)
Vector(int cap,int inc)
常用方法
参见 JDK帮助文档索迪教育
ArrayList
构造函数
ArrayList()
ArrayList(int initialCapacity)
常用方法
参见 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(int cap)
Hashtable(int cap,float load)
常用方法
参见 JDK帮助文档索迪教育
HashMap
构造函数
HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity,float loadFactor)
常用方法
参见 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(Object value)，功能和
containsValue(Object value)功能一样。
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 每个一种。
Collection unmodifiableCollection(Collection collection)
List unmodifiableList(List list)
Map unmodifiableMap(Map map)
Set unmodifiableSet(Set set)
SortedMap unmodifiableSortedMap(SortedMap map)
SortedSet unmodifiableSortedSet(SortedSet set)
一旦您填充完集合，用只读引用替代原始引用。如果不替代原始引用，那么集合就不是只读的，因为您仍然可以使用原始引用修改集合。
索迪教育线程安全集合
早期集合类和集合框架中新的实现的差别在于新类不是线程安全的。
设计者采用这种线程安全方法是让您只在需要时才使用同步，
使每项工作快得多。
但如果，您正将集合用于多个线程能够同步修改集合的多线程环境，修改就必须同步进行。
Collections 类有能力用另一组的六个方法把现有的集合包装成同步集合：
Collection synchronizedCollection(Collection collection)
List synchronizedList(List list)
Map synchronizedMap(Map map)
Set synchronizedSet(Set set)
SortedMap synchronizedSortedMap(SortedMap map)
SortedSet synchronizedSortedSet(SortedSet set)
索迪教育集合框架的优点
提高程序速度和质量
允许无关 API 之间的互操作性
减少编程工作
方便扩展或改写集合
减少设计新 API 的工作索迪教育本章小结
解释集合框架的体系结构
使用集合类和接口
