读Core Java 第二章

一、集合2.0

1、相关知识
（1）面向对象的编程（OOP）通常将数据封装在各个类中
（2）数据结构

二、集合2.1

1、概述
（1）Enumeration接口提供了一种抽象机制，用于访问任意一个容器中的各个元素
（2）例如：Vector、Stack、Hashtable、BitSet、Enumeration接口等

2、将集合接口与实现分离
（1）队列接口，实现队列的方法通常有两种：一种是“循环数组”，另一种是“链表”
（2）从JDK 5.0开始，集合类是带类型参数的泛型类
（3）循环数组总是比链表更加高效，循环数组是有界集合，容量有限

3、Java类库中的集合接口和迭代器接口
（1）Java类库中用于集合类的基本接口是Collection接口
（2）Collection包含的方法add，iterator等
（3）add方法用于向集合中添加元素，如果添加元素后，该集合发生改变，返回true；如果添加元素后，集合无任何变化，返回false
（4）iterator方法用于返回一个实现了Iterator接口的对象

4、迭代器
（1）

public interface Iterator<E>{
	E next();	//到达末尾，抛出一个NoSuchElementException异常
	boolean hasNext();
	void remove();
	}

（2）for each循环
for(String element:c){ } //编译器直接将for each循环转化成包含迭代器的一个循环
（3）在ArrayList进行迭代，迭代器从索引零开始，每迭代一步索引加一
（4）访问HashSet中的元素，索引基本上是最忌排列的，迭代过程中遍历集合中的所有元素，但是无法确定这些元素被访问的顺序
（5）next方法和remove方法调用是互相依赖的，如果调用remove方法之前没调用next方法，不合法，抛出illegalStateException异常
（6）由于Collection和Iterator接口都属于泛型接口，可以编写在任何种类的集合上运行的实用方法

5、java.util.Collection<E>

（1）Iterator<E> iterator()：返回一个迭代器，用于访问集合中的各种元素
（2）int size（）：返回当前存放在集合中的元素的数量
（3）boolean isEmpty（）： 如果该集合中没有任何元素，则返回true
（4）boolean contains(Object obj）：如果该集合中包含一个与obj相等的对象，返回true
（5）boolean containsAll(Collection<?> other)：如果该集合包含了other集合中的所有元素，则返回true
（6）boolean add(Object element)：将一个元素添加到该集合中，如果由于调用而使集合发生了变化，则返回true
（7）boolean allAll(Collection<? extends E> other)：将来自other集合中的所有元素添加到该集合中，如果由于该调用而使集合发生了变化，则返回true
（8）boolean remove（Object obj）：移除该集合中与obj相等的对象，如果有匹配的对象被成功移除，则返回true
（9）void clear（）：移除该集合中所有元素
（10）Object[] toArray():返回该集合的对象数组

6、Java类库中具体的集合

三、集合2.2

1、链表linked list
（1）将每个对象存放在独立的结点中，每个结点还存放着序列中下一个结点的引用
（2）在Java编程语言中，所有链表实际上是双重链接，每个结点中存放着对它的前面结点的引用
（3）链表是一个有序集合
（4）LinkedListadd方法用于将对象添加到列表的尾部
（5）如果一个迭代器发现它的集合已经被另一个迭代器修改了，或者被该集合自身的方法修改了，那么就会抛出一个ConcurrentModificationException异常
（6）对于并发修改列表的探测，链表只负责跟踪对列表的结构性修改，比如添加或移除结点，而set方法并不被视为结构性修改，可以将多个迭代器附加给一个链表，所有的迭代器都调用set方法来修改现有结点的内容
（7）链表不支持快速随机访问，如果要查看链表中的第n个元素，必须从头开始，然后跳过前面的n-1个元素
（8）在元素必须用整数索引来访问的编程情形中，通常不适用链表
（9）不可靠的随机访问方法遍历链表

for(int i=0; i<list.size() ;i++)   do something with list.get(i);

运行效率极低，每次查找一个元素，都必须从列表头部重新开始搜索，LinkedList对象根本不作任何缓存位置信息的操作
（10）get方法稍微做了下优化，如果索引比size()/2大，那么对元素的索引将从列表尾部开始进行

2、数组列表
（1）List用于描述一个有序的集合，集合中的各个元素位置很重要
（2）数组列表ArrayList类，实现了List接口，封装了一个动态再分配的对象数组
（3）Vector类对象的方法是同步的，ArrayList方法不同步的

3、散列集
（1）快速查找所需要的对象，为每个对象计算出一个整数，称为散列码
（2）具有不同数据字段的对象会产生不同的散列码，由String类的hashCode方法产生
（3）实现的hashCode方法必须与equals方法兼容，如果a.equals(b)为true，则a与b必须具有相同的散列码
（4）散列表是链表的数组，每个列表称为一个散列单元
（5）如果一个对象的散列码是76268，共有128个散列单元，那么该对象将放在散列表元108中，因为76268除以128的余数为108
（6）散列集：hashset不存在重复元素的集合，add方法首先查找是否存在要添加的元素，如果不存在则添加
（7）Java集合类库提供了一个HashSet类，是基于散列表的散列集
（8）常用方法
4、树集
（1）TreeSet是一个有序集合，可以按照任何顺序将元素插入该集合
（2）如果一个树集有1000元素，添加一个新元素大约需要进行10次比较，因为2的10次幂大于1000
（3）Comparator接口声明了两个方法：compare和equals
（4）每个类其实都有一个equals方法

5、优先级队列
（1）Priority Queue是一种能够再以任意顺序插入元素后，再按排序顺序读取这些元素的数据结构
（2）remove方法，返回当前优先级队列中的最小元素
（3）利用堆，堆是一个可以进行自我调整的二叉树，调用add和remove方法将会使最小的元素移动到根
（4）任务调度，每个任务有一个优先级，任务以随机顺序添加到队列中，每当启动一个新任务，总是最高优先级的任务从队列中被移除出来去执行，1是最高优先级，所以，先把最小的元素移除
（5）java.util.PriorityQueue

6、映射表
（1）映射表数据结构存放许多键/值对，如果提供了键，就能够找到与它对应的值
（2）Java类库为映射表提供了两个通用的实现：散列映射表HashMap和树状映射表TreeMap，都实现了Map接口
（3）常用方法

（4）只添加键，不添加值的add方法，会抛出一个UnsupportedOperationException异常
（5）java.util.Map<K,V>

V get(K key)：获取与该键向关联的值，并且返回与该键相关联的对象，如果没有在该映射表中找打该键，则返回null
V put(K key,V value）：将相互关联的一个键和一个值插入到该映射表中，如果该键已经存在了，那么新对象将取代与该键相关联的旧对象，本方法返回键的旧值，如果键原先并不存在，则返回null，键可能会是null，但值不一定会是null
Set<Map.Entry<K,V>>entrySet()：返回Map.Entry对象的视图集，即映射表中的键/值对，可以移除，无法添加
Set<K> keySet()：返回该映射表中的所有键的视图集，可以移除，并且移除的键和相关联的值都会被移除，但是不能向其中添加任何元素
Collection<V> values()：返回该映射表中的所有值的视图集合，可以移除，并且关联的键也移除，不同添加任何元素

（6）java.util.Map.Entry<K,V>

K getKey（）：获取键
V getValue()  ：返回该元素项的值
V setValue(V newValue)：将相关联的映射表中的值更新为新值，并且返回旧值

7、枚举集和枚举映射表
（1）EnumSet是一个包含枚举类型元素的集
（2）使用位序列实现

四、集合2.3

1、集合框架
（1）框架，是一个类集合
（2）两个用于集合的基本接口，即Collection和Map
（3）图示

（4）集合框架中的各个类以及相互关系

五、算法

1、排序与混排
（1）sort方法默认元素实现了Comparable接口，直接将所有的元素转入到一个数组，再使用归并排序的一种变体对数组进行排序，然后将排序后的元素重新复制到列表中
（2）归并排序算法比较稳定，不需要交换相同的元素
（3）混排：随机混排列表中各个元素的顺序，体哦国内要混排的列表和一个随机数生成器
（4）java.utils.Collections

2、二分查找
（1）如果数组包含1024个元素，将在10次二分查找后找到匹配的元素
（2）如果使用线性查找算法，平均需要进行512次比较才能找到该元素
（3）Collections类的binarySearch方法可以实现这个算法，前提是集合有序，否则将会返回错误的结果
（4）如果binarySearch方法返回的值大于等于零，那表示的是匹配对象的索引，如果该值是负值，则没有任何匹配元素
（5）对于链表查找，binarySearch算法便成了一个线性查找

3、简单算法

六、集合2.5

1、Hashtable类
（1）方法是同步的

2、枚举
（1）枚举Enumeration接口有两个方法：hasMoreElements和nextElement
（2）静态方法Collections.enumeration产生一个枚举对象，用于枚举集合中的各个元素
（3）常用方法

3、属性集
（1）Property Set是类型特殊的映射表结构
（2）键和值都是字符串，表可以保存到一个文件中，也可从一个文件中加载，使用一个默认的辅助表
（3）用于实现一个属性集的Java平台类称为Properties
（4）常用方法

4、栈
（1）栈Stack继承Vector类
（2）常用方法

E push(E item)：将item压入栈中，然后返回item
E pop（）：弹出和返回栈顶项，如果栈是空的，不可使用
E peek（）：返回栈顶项而不弹出，栈空不可使用

5、位集
（1）BitSet存放一个位序列，存储如标志序列，将各个位包装在字节中
（2）可以对各个位进行读取、设置或者清除等操作
（3）常用方法