一.完整的容器分類法
二.collection接口
1.boolean add（T）確保容器持有具有泛型類型T的參數(shù)剩燥，如果沒有將此參數(shù)添加進(jìn)容器嗦嗡，則返回false
2.boolean addAll（Collection <? extends T>）添加參數(shù)中的所有元素柱衔，只要添加了任意元素就返回true
3.void clear（） 移除容器中的所有元素
4.boolean contains（T） 如果容器中已經(jīng)持有泛型類型T此參數(shù)楔壤，則返回true
5.Boolean containsAll（Collection<?>）如果容器持有此參數(shù)中的所有元素,則返回true
6.boolean isEmpty() 容器中沒有元素時(shí)返回true
7.Iterator<T> iterator() 返回一個(gè)Iterator<T> , 可以用來遍歷容器中的元素
8.Boolean remove(Object) 如果參數(shù)在容器中,則移除此元素的一個(gè)實(shí)例,如果做了一處操作,則返回true
9.boolean removeAll(Collection<?>) 移除參數(shù)中的所有元素,只要有移除動(dòng)作就返回true
11.Boolean retainAll(Collection<?>) 只保存參數(shù)中的元素,只要Collection發(fā)生了改變就返回true
12.int size() 返回容器中元素的數(shù)目
13.Object[] toArray() 返回一個(gè)數(shù)組,該數(shù)組包含容器中的所有元素
14.<T> T[] toArray(T[] a)返回一個(gè)數(shù)組該數(shù)組包含容器中的所有元素,返回結(jié)果的運(yùn)行時(shí)類型參數(shù)與參數(shù)數(shù)組a的類型相同,而不是單純的Object
三.UnsupportedOperationException(未獲支持的操作) 異常
List list = Arrays.asList(array) 當(dāng)對(duì)list 進(jìn)行增刪操作時(shí) 就會(huì)拋出UnsupportedOperationException異常
對(duì)于UnsupportedOperationException 異常：
1.它必須是一個(gè)罕見的事件
2.如果一個(gè)操作時(shí)未獲支持的,那么在實(shí)現(xiàn)接口的時(shí)候可以拋出這個(gè)異常
3.它只能在運(yùn)行時(shí)才能被檢測(cè)到
四.List功能方法
五.Set和存儲(chǔ)順序
| 集合名稱 | 集合說明 |
|---|---|
| Set(interface) | 存入Set的每個(gè)元素必須是惟一的氓扛，因?yàn)镾et不保存重復(fù)的元素瀑晒，加入Set的元素必須定義equals()方法一確保對(duì)象的唯一性算墨。Set接口不保證維護(hù)元素的次序 |
| HashSet | 為快速查找而設(shè)計(jì)的Set宵荒，存入的HashSet的元素必須定義hashCode()，保持次序的Set净嘀，底層為樹結(jié)構(gòu)报咳。使用它可以從Set中提取有序的序列，元素必須實(shí)現(xiàn)Comparable接口 |
| LinkedHashSet | 具有HashSet的查詢速度挖藏，且內(nèi)部使用鏈表維護(hù)元素的順序暑刃，于是在使用迭代遍歷Set時(shí)，結(jié)果會(huì)按元素插入的次序顯示膜眠。元素必須定義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按照排序順序維護(hù)順序(按照CompareTo()的實(shí)現(xiàn)形式架谎，這里維護(hù)的 降序)
- SortedSet：
1.Comparator comparator（）返回當(dāng)前set使用的Comparator，或者返回null柄驻，表示自然方式排序
2.Object first（）返回容器總的第一個(gè)元素
3.Object last（）返回容器中的最末一個(gè)元素
4.SortedSet subSet（fromElement狐树， toElement）生成此Set的自己，范圍從fromElement（包含）到toElement（不包含）
5.SortedSet headSet（toElement）生成此Set的子集鸿脓，由小于toElement的元素組成
6.SortedSet tailSet（fromElement）生成此Set的子集抑钟，由大于或等于fromElement的元素組成
六.隊(duì)列
- Queue在java se5中只有兩個(gè)實(shí)現(xiàn)涯曲，LinkedList和PriorityQueue，他們的差異在排序行為
PriorityQueue的排序也是通過Comparable而進(jìn)行控制 - 雙向隊(duì)列：
就像是一個(gè)隊(duì)列在塔，但是可以在任何一段添加或移除元素幻件，在LinkedList中包含支持雙向隊(duì)列的方法，但是在java標(biāo)準(zhǔn)類庫中沒有任何顯式地用于雙向隊(duì)列的接口蛔溃。因此可以使用組合來創(chuàng)建一個(gè)Deque類绰沥，并直接從LinkedList中暴露
七.Map
- 實(shí)現(xiàn)一個(gè)簡(jiǎn)單的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基于散列表的實(shí)現(xiàn)(他取代了HashTable)，插入和查詢"鍵值對(duì)"的開銷是固定的贺待』涨可以通過構(gòu)造器設(shè)置容量和負(fù)載因子，已調(diào)整容器的性能 |
| LinkedHashMap | 類似于HashMap,但是迭代遍歷它時(shí)麸塞，取得"鍵值對(duì)"的順序是器插入次序秃臣，或者是最近少使用(LRU)的次序。只比HashMap慢點(diǎn);而在迭代訪問時(shí)更快哪工，因?yàn)樗褂面湵砭S護(hù)內(nèi)部次序 |
| TreeMap | 基于紅黑樹的實(shí)現(xiàn)奥此。查看"鍵"或"鍵值對(duì)"時(shí)，他們會(huì)被排序(次序由Comparable或Comparator決定)雁比。TreeMap的特點(diǎn)在于稚虎，所得到的結(jié)果是經(jīng)過排序的。TreeMap是唯一的帶有subMap()方法的Map |
| WeakHashMap | 弱鍵映射偎捎，允許釋放映射所指向的對(duì)象 |
| CurrentHashMap | 一種線程安全的Map,它不涉及同步加鎖蠢终，并發(fā)用的較多 |
| IdentityHashMap | 使用==代替equals()對(duì)"鍵"進(jìn)行比較的散列映射 |
對(duì)Map中使用的鍵的要求與對(duì)Set中的元素的要求一樣，任務(wù)鍵都必須具有一個(gè)equals()方法茴她，如果鍵被用于散列Map蜕径，那么他必須還具有恰當(dāng)?shù)膆ashCode()方法，如果鍵被用于TreeMap,那么他必須實(shí)現(xiàn)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);
}
}
從輸出的結(jié)果看败京，數(shù)字3的鍵無法找到兜喻，因?yàn)镚roundhog自動(dòng)繼承Object類，使用了Object累的hashCode()方法生成了散列碼赡麦，而它默認(rèn)使用對(duì)象的地址計(jì)算散列碼朴皆，因此，由Groundhog(3)生成的第一個(gè)實(shí)例的散列碼與由Groundhog(3)生成的散列碼是不同的泛粹，所以找不到
HashMap使用equals()判斷當(dāng)前的鍵是否與表中存在的鍵相同
正確的equals()方法必須滿足下列5個(gè)條件：
1.自反性遂铡。對(duì)任意x,x.equals(x)一定返回true
2.對(duì)稱性。對(duì)任意x和y晶姊，如果y.equals(x)返回true,則x.equals(y)也返回true
3.傳遞性扒接。對(duì)任意的x,y.z 如果有x.equals(y)返回true,y.equals(z)返回true,則x.equals(z)一定返回true
4.一致性。
5.對(duì)任何不是null的x,x.equals(null)一定返回false
理解hashCode()
hashCode()特點(diǎn)：
1.無論何時(shí)，對(duì)同一個(gè)對(duì)象調(diào)用hashCode()都應(yīng)該生成同樣的值钾怔。
2.hashCode()不能依賴于具有唯一性的對(duì)象信息碱呼，應(yīng)該使用對(duì)象內(nèi)有意義的識(shí)別信息。
3.對(duì)于String類宗侦，hashCode()是基于String的內(nèi)容的愚臀；
4.散列碼不必是獨(dú)一無二的，應(yīng)該更關(guān)注速度矾利，而不是唯一性姑裂，通過hashCode()和equals()，必須能夠完全確定對(duì)象的身份男旗。
5.好的hashCode()應(yīng)該產(chǎn)生分布均勻的散列碼舶斧。為速度而散列
1.散列的價(jià)值在于速度：散列使得查詢得以快速進(jìn)行。由于瓶頸位于鍵的查詢速度察皇，因此解決方案之一就是保持鍵的排序狀態(tài)捧毛。
2.存儲(chǔ)一組元素最快的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，因此用數(shù)組保存鍵的信息让网。數(shù)組并不保證鍵的本身，而是通過鍵對(duì)象生成一個(gè)數(shù)字师痕，將其作為數(shù)組的下標(biāo)溃睹。這個(gè)數(shù)字就是散列碼
3.查詢一個(gè)值的過程就是首先計(jì)算散列碼，然后使用散列碼查詢數(shù)組胰坟，如果能保證沒有沖突因篇，那可就有了一個(gè)完美的散列函數(shù)，但是這種情況只是特例笔横。通常情況下竞滓，沖突由**外部鏈接
**處理：數(shù)組并不保存值，而是保存值的list吹缔。然后對(duì)list中的值使用equals（）方法進(jìn)行線性查詢商佑。這部分的查詢會(huì)比較慢，如果散列函數(shù)好的話厢塘，數(shù)組的每個(gè)位置就只有很少的值茶没。因此，不是查詢整個(gè)list,而是快速跳轉(zhuǎn)到數(shù)組的某個(gè)位置晚碾，對(duì)很少的元素進(jìn)行比較抓半，這就是HashMap會(huì)如此快的原因
以下實(shí)現(xiàn)一個(gè)簡(jiǎn)單的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());
}
}
