一.完整的容器分类法
二.collection接口
1.boolean add（T）确保容器持有具有泛型类型T的参数，如果没有将此参数添加进容器，则返回false
2.boolean addAll（Collection <? extends T>）添加参数中的所有元素，只要添加了任意元素就返回true
3.void clear（） 移除容器中的所有元素
4.boolean contains（T） 如果容器中已经持有泛型类型T此参数，则返回true
5.Boolean containsAll（Collection<?>）如果容器持有此参数中的所有元素,则返回true
6.boolean isEmpty() 容器中没有元素时返回true
7.Iterator<T> iterator() 返回一个Iterator<T> , 可以用来遍历容器中的元素
8.Boolean remove(Object) 如果参数在容器中,则移除此元素的一个实例,如果做了一处操作,则返回true
9.boolean removeAll(Collection<?>) 移除参数中的所有元素,只要有移除动作就返回true
11.Boolean retainAll(Collection<?>) 只保存参数中的元素,只要Collection发生了改变就返回true
12.int size() 返回容器中元素的数目
13.Object[] toArray() 返回一个数组,该数组包含容器中的所有元素
14.<T> T[] toArray(T[] a)返回一个数组该数组包含容器中的所有元素,返回结果的运行时类型参数与参数数组a的类型相同,而不是单纯的Object
三.UnsupportedOperationException(未获支持的操作) 异常
List list = Arrays.asList(array) 当对list 进行增删操作时 就会抛出UnsupportedOperationException异常
对于UnsupportedOperationException 异常：
1.它必须是一个罕见的事件
2.如果一个操作时未获支持的,那么在实现接口的时候可以抛出这个异常
3.它只能在运行时才能被检测到
四.List功能方法
五.Set和存储顺序
| 集合名称 | 集合说明 |
|---|---|
| Set(interface) | 存入Set的每个元素必须是惟一的，因为Set不保存重复的元素，加入Set的元素必须定义equals()方法一确保对象的唯一性。Set接口不保证维护元素的次序 |
| HashSet | 为快速查找而设计的Set，存入的HashSet的元素必须定义hashCode()，保持次序的Set，底层为树结构。使用它可以从Set中提取有序的序列，元素必须实现Comparable接口 |
| LinkedHashSet | 具有HashSet的查询速度，且内部使用链表维护元素的顺序，于是在使用迭代遍历Set时，结果会按元素插入的次序显示。元素必须定义hashCode()方法 |
public class SetType {
int i;
public SetType(int n){
this.i = n;
}
public boolean equals(Object obj){
return obj instanceof SetType && (i == ((SetType)obj).i);
}
public String toString(){
return Integer.toString(i);
}
}
public class HashType extends SetType{
public HashType(int n){ super(n);}
public int hashCode(){return i;}
}
public class TreeType extends SetType implements Comparable<TreeType>{
public TreeType(int n) {
super(n);
}
@Override
public int compareTo(TreeType type) {
return (type.i < i ? -1 : (type.i == i ? 0 : 1));
}
}
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class TypesForSet {
static <T>Set<T> fill(Set<T> set,Class<T> type){
try{
for(int i=0;i<10;i++){
set.add(type.getConstructor(int.class).newInstance(i));
}
}catch(Exception ex){
throw new RuntimeException();
}
return set;
}
static <T> void test(Set<T> set,Class<T> type){
fill(set, type);
fill(set, type);
fill(set, type);
System.out.println(set);
}
public static void main(String[] args) {
test(new HashSet<HashType>(), HashType.class);
test(new LinkedHashSet<HashType>(), HashType.class);
test(new TreeSet<TreeType>(), TreeType.class);
test(new HashSet<SetType>(), SetType.class);
test(new HashSet<TreeType>(), TreeType.class);
test(new LinkedHashSet<SetType>(), SetType.class);
test(new LinkedHashSet<TreeType>(), TreeType.class);
}
}
从输出可以看出，HashSet以某种神秘的顺序白痴所有的元素，LinkedHashSet按照元素的插入顺序保存元素，而TreeSet按照排序顺序维护顺序(按照CompareTo()的实现形式，这里维护的 降序)
- SortedSet：
1.Comparator comparator（）返回当前set使用的Comparator，或者返回null，表示自然方式排序
2.Object first（）返回容器总的第一个元素
3.Object last（）返回容器中的最末一个元素
4.SortedSet subSet（fromElement， toElement）生成此Set的自己，范围从fromElement（包含）到toElement（不包含）
5.SortedSet headSet（toElement）生成此Set的子集，由小于toElement的元素组成
6.SortedSet tailSet（fromElement）生成此Set的子集，由大于或等于fromElement的元素组成
六.队列
- Queue在java se5中只有两个实现，LinkedList和PriorityQueue，他们的差异在排序行为
PriorityQueue的排序也是通过Comparable而进行控制 - 双向队列：
就像是一个队列，但是可以在任何一段添加或移除元素，在LinkedList中包含支持双向队列的方法，但是在java标准类库中没有任何显式地用于双向队列的接口。因此可以使用组合来创建一个Deque类，并直接从LinkedList中暴露
七.Map
- 实现一个简单的Map
package com.zlb.map;
public class AssociativeArray<K,V>{
private Object pairs[][];
private int index;
public AssociativeArray(int length){
pairs = new Object[length][2];
}
public void put(K key,V value){
if(index >= pairs.length)
throw new ArrayIndexOutOfBoundsException();
pairs[index++] = new Object[]{key,value};
}
@SuppressWarnings("unchecked")
public V get(K key){
for(int i=0;i<index;i++){
if(key.equals(pairs[i][0])){
return (V)pairs[i][1];
}
}
return null;
}
public String toString(){
StringBuffer stu = new StringBuffer();
for(int i=0;i<index;i++){
stu.append(pairs[i][0].toString());
stu.append(" ： ");
stu.append(pairs[i][1].toString());
if(i < index - 1)
stu.append("\n");
}
return stu.toString();
}
public static void main(String[] args) {
AssociativeArray<String,String> map = new AssociativeArray<String,String>(6);
map.put("name", "zhoulibin");
map.put("age", "22");
map.put("sex", "man");
System.out.println(map);
System.out.println(map.get("name"));
}
}
| 集合名称 | 集合说明 |
|---|---|
| HashMap* | Map基于散列表的实现(他取代了HashTable)，插入和查询"键值对"的开销是固定的。可以通过构造器设置容量和负载因子，已调整容器的性能 |
| LinkedHashMap | 类似于HashMap,但是迭代遍历它时，取得"键值对"的顺序是器插入次序，或者是最近少使用(LRU)的次序。只比HashMap慢点;而在迭代访问时更快，因为它使用链表维护内部次序 |
| TreeMap | 基于红黑树的实现。查看"键"或"键值对"时，他们会被排序(次序由Comparable或Comparator决定)。TreeMap的特点在于，所得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map |
| WeakHashMap | 弱键映射，允许释放映射所指向的对象 |
| CurrentHashMap | 一种线程安全的Map,它不涉及同步加锁，并发用的较多 |
| IdentityHashMap | 使用==代替equals()对"键"进行比较的散列映射 |
对Map中使用的键的要求与对Set中的元素的要求一样，任务键都必须具有一个equals()方法，如果键被用于散列Map，那么他必须还具有恰当的hashCode()方法，如果键被用于TreeMap,那么他必须实现Comparable
八.散列与散列码
package com.zlb.hashcode;
public class Groundhog {
protected int number;
public Groundhog(int n){number = n;}
public String toString(){
return "Groundhod # "+ number;
}
}
package com.zlb.hashcode;
import java.util.Random;
public class Prediction {
private static Random random = new Random(47);
private boolean shadow = random.nextDouble() > 0.5;
public String toString(){
if(shadow)
return "Six more weeks";
else
return "Spring";
}
}
package com.zlb.hashcode;
import java.lang.reflect.Constructor;
import java.util.HashMap;
import java.util.Map;
public class SpringDector {
public static <T extends Groundhog> void detectSpring(Class<T> type) throws Exception{
Constructor<T> ghog = type.getConstructor(int.class);
Map<Groundhog,Prediction> map = new HashMap<Groundhog,Prediction>();
for(int i=0;i<10;i++){
map.put(ghog.newInstance(i), new Prediction());
}
System.out.println("map："+map);
Groundhog gh = ghog.newInstance(3);
System.out.println("looke up f or："+gh);
if(map.containsKey(gh)){
System.out.println(map.get(gh));
}else{
System.out.println("key not found：" + gh);
}
}
public static void main(String[] args) throws Exception {
detectSpring(Groundhog.class);
}
}
从输出的结果看，数字3的键无法找到，因为Groundhog自动继承Object类，使用了Object累的hashCode()方法生成了散列码，而它默认使用对象的地址计算散列码，因此，由Groundhog(3)生成的第一个实例的散列码与由Groundhog(3)生成的散列码是不同的，所以找不到
HashMap使用equals()判断当前的键是否与表中存在的键相同
正确的equals()方法必须满足下列5个条件：
1.自反性。对任意x,x.equals(x)一定返回true
2.对称性。对任意x和y，如果y.equals(x)返回true,则x.equals(y)也返回true
3.传递性。对任意的x,y.z 如果有x.equals(y)返回true,y.equals(z)返回true,则x.equals(z)一定返回true
4.一致性。
5.对任何不是null的x,x.equals(null)一定返回false
理解hashCode()
hashCode()特点：
1.无论何时，对同一个对象调用hashCode()都应该生成同样的值。
2.hashCode()不能依赖于具有唯一性的对象信息，应该使用对象内有意义的识别信息。
3.对于String类，hashCode()是基于String的内容的；
4.散列码不必是独一无二的，应该更关注速度，而不是唯一性，通过hashCode()和equals()，必须能够完全确定对象的身份。
5.好的hashCode()应该产生分布均匀的散列码。为速度而散列
1.散列的价值在于速度：散列使得查询得以快速进行。由于瓶颈位于键的查询速度，因此解决方案之一就是保持键的排序状态。
2.存储一组元素最快的数据结构是数组，因此用数组保存键的信息。数组并不保证键的本身，而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码
3.查询一个值的过程就是首先计算散列码，然后使用散列码查询数组，如果能保证没有冲突，那可就有了一个完美的散列函数，但是这种情况只是特例。通常情况下，冲突由**外部链接
**处理：数组并不保存值，而是保存值的list。然后对list中的值使用equals（）方法进行线性查询。这部分的查询会比较慢，如果散列函数好的话，数组的每个位置就只有很少的值。因此，不是查询整个list,而是快速跳转到数组的某个位置，对很少的元素进行比较，这就是HashMap会如此快的原因
以下实现一个简单的HashMap:
package com.zlb.hashcode;
import java.util.AbstractMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
static final int SIZE = 997;
@SuppressWarnings("unchecked")
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
@Override
public Set<Map.Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();
for (LinkedList<MapEntry<K, V>> bucket : buckets) {
if (bucket == null) {
continue;
}
for (MapEntry<K, V> mpair : bucket) {
set.add(mpair);
}
}
return set;
}
public V put(K key, V value) {
V oldValue = null;
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null) {
buckets[index] = new LinkedList<MapEntry<K, V>>();
}
LinkedList<MapEntry<K, V>> bucket = buckets[index];
MapEntry<K, V> pair = new MapEntry<K, V>(key, value);
boolean found = false;
ListIterator<MapEntry<K, V>> it = bucket.listIterator();
while (it.hasNext()) {
MapEntry<K, V> iPair = it.next();
if (iPair.getKey().equals(key)) {
oldValue = iPair.getValue();
it.set(pair);
found = true;
break;
}
}
if (!found) {
buckets[index].add(pair);
}
return oldValue;
}
public V get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null)
return null;
for (MapEntry<K, V> iPair : buckets[index])
if (iPair.getKey().equals(key))
return iPair.getValue();
return null;
}
public static void main(String[] args) {
SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();
m.put("firstName", "zhou");
m.put("lastName", "libin");
System.out.println(m);
System.out.println(m.get("lastName"));
System.out.println(m.entrySet());
}
}
