第17章容器深入研究
MingCHEN 2012-02-02
1.List接口的相关方法
1）toArray
Object[]toArray()
Returnsanarraycontainingalloftheelementsinthislistinpropersequence.Obeysthe
generalcontractoftheCollection.toArraymethod.
2）toArray
<T>T[]toArray(T[]a)
Returnsanarraycontainingalloftheelementsinthislistinpropersequence;theruntime
typeofthereturnedarrayisthatofthespecifiedarray.Obeysthegeneralcontractofthe
Collection.toArray(Object[])method.
Parameters:
a-thearrayintowhichtheelementsofthislistaretobestored,ifitisbigenough;
otherwise,anewarrayofthesameruntimetypeisallocatedforthispurpose.
Returns:
anarraycontainingtheelementsofthislist.
3）set
Eset(intindex,
Eelement)
Replacestheelementatthespecifiedpositioninthislistwiththespecifiedelement
(optionaloperation).
Parameters:
index-indexofelementtoreplace.
element-elementtobestoredatthespecifiedposition.
Returns:
theelementpreviouslyatthespecifiedposition.
4）clear
voidclear()
Removesalloftheelementsfromthislist(optionaloperation).Thislistwillbeemptyafter
thiscallreturns(unlessitthrowsanexception).
5）removeAll
booleanremoveAll(Collection<?>c)
Removesfromthislistalltheelementsthatarecontainedinthespecifiedcollection
(optionaloperation).
Parameters:
c-collectionthatdefineswhichelementswillberemovedfromthislist.
Returns:
trueifthislistchangedasaresultofthecall.
2.HashSet为快速查找而设计的Set，存入HashSet的元素必须定义hashCode（）
TreeSet保持次序的Set，底层为树结构，必须实现Comparable接口
LinkedHashSet，具有HashSet的查询速度，且内部维护元素的出入次序。
3.Map的实现
publicclassAssociativeArray<K,V>{
privateObject[][]pairs;
privateintindex;
publicAssociativeArray(intlength){
pairs=newObject[length][2];
}
publicvoidput(Kkey,Vvalue){
if(index>=pairs.length)
thrownewArrayIndexOutOfBoundsException();
pairs[index++]=newObject[]{key,value};
}
@SuppressWarnings("unchecked")
publicVget(Kkey){
for(inti=0;i<index;i++)
if(key.equals(pairs[i][0]))
return(V)pairs[i][1];
returnnull;//Didnotfindkey
}
publicStringtoString(){
StringBuilderresult=newStringBuilder();
for(inti=0;i<index;i++){
result.append(pairs[i][0].toString());
result.append(":");
result.append(pairs[i][1].toString());
if(i<index-1)
result.append("\n");
}
returnresult.toString();
}
publicstaticvoidmain(String[]args){
AssociativeArray<String,String>map=newAssociativeArray<String,String>(
6);
map.put("sky","blue");
map.put("grass","green");
map.put("ocean","dancing");
map.put("tree","tall");
map.put("earth","brown");
map.put("sun","warm");
try{
map.put("extra","object");//Pasttheend
}catch(ArrayIndexOutOfBoundsExceptione){
System.out.println("Toomanyobjects!");
}
System.out.println(map);
System.out.println(map.get("ocean"));
}
}
上面的代码只是说明性的，而且大小还固定，要和真正的Map比起来效率差很多。
4.散列码与散列
Object的hashCode()方法生成的散列码，默认是根据对象的地址计算出的散列码。即，如果一个类不重写该方法
，那么由该类生成的不同对象的散列码是不同的。
Object的equals()方法默认比较的是对象的地址。且正确的equals方法必须满足5个条件
1)自反行。对任意x，x.equals(x)一定返回true
2)对称性。对任意的x.equals(y)那么y.equals(x)也成立
3)传递性。x.equals(y)，y.equals(z)，x.equals(z)
4)一致性。如果返回true，那么不管调用任意多次都返回true
5)对任何不是null的x，x.equals(null)一定返回false.
如果要使用自己创建的类作为Map的键，必须同时覆盖equals和hashCode方法。
5.线性查询方式是最忙的查询方式。
6.区别
1)、equals方法用于比较对象的内容是否相等（覆盖以后）
2)、hashcode方法只有在集合中用到
3)、当覆盖了equals方法时，比较对象是否相等将通过覆盖后的equals方法进行比较（判断对象的内容是否相等）。
4)、将对象放入到集合中时，首先判断要放入对象的hashcode值与集合中的任意一个元素的hashcode值是否相等，如果不相等直接将该对象放入集合中。如果hashcode值相等，然后再通过equals方法判断要放入对象与集合中的任意一个对象是否相等，如果equals判断不相等，直接将该元素放入到集合中，否则不放入
总结：同一个类不同对象的散列码可能相同，可能不同，相同对象的散列码一定相同
7.通过key对象生成一个数字，将其作为数组的下标，这个数字就是散列码。该散列码由hashCode方法自动生成。为了解决数组容量被固定的问题，不同的键对象可以生成相同的散列码，这样数组大小就不是问题了。如果散列码有冲突，再用线性方式比较，因为经过散列后，相同散列码上的线性序列已经很小了，这比一开始就用线性搜索要快的多，这就是HashMap速度快的原因。
publicclassSimpleHashMap<K,V>extendsAbstractMap<K,V>{
//Chooseaprimenumberforthehashtable
//size,toachieveauniformdistribution:
staticfinalintSIZE=997;
//Youcan'thaveaphysicalarrayofgenerics,
//butyoucanupcasttoone:
@SuppressWarnings("unchecked")
LinkedList<MapEntry<K,V>>[]buckets=newLinkedList[SIZE];
publicVput(Kkey,Vvalue){
VoldValue=null;
intindex=Math.abs(key.hashCode())%SIZE;
if(buckets[index]==null)
buckets[index]=newLinkedList<MapEntry<K,V>>();
LinkedList<MapEntry<K,V>>bucket=buckets[index];
MapEntry<K,V>pair=newMapEntry<K,V>(key,value);
booleanfound=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);//Replaceoldwithnew
found=true;
break;
}
}
if(!found)
buckets[index].add(pair);
returnoldValue;
}
publicVget(Objectkey){
intindex=Math.abs(key.hashCode())%SIZE;
if(buckets[index]==null)
returnnull;
for(MapEntry<K,V>iPair:buckets[index])
if(iPair.getKey().equals(key))
returniPair.getValue();
returnnull;
}
publicSet<Map.Entry<K,V>>entrySet(){
Set<Map.Entry<K,V>>set=newHashSet<Map.Entry<K,V>>();
for(LinkedList<MapEntry<K,V>>bucket:buckets){
if(bucket==null)
continue;
for(MapEntry<K,V>mpair:bucket)
set.add(mpair);
}
returnset;
}
publicstaticvoidmain(String[]args){
SimpleHashMap<String,String>m=newSimpleHashMap<String,String>();
m.putAll(Countries.capitals(25));
System.out.println(m);
System.out.println(m.get("ERITREA"));
System.out.println(m.entrySet());
}
}
8.由散列码组成的表称为散列表，每个散列码称为“槽为”或是“桶位”；
9.对于现代的处理器而言，除法和求余数是最慢的操作。java的散列函数都使用2的整数次方。
10.如果想让对象生成的散列码在某个范围内，比如在0到5直接，那么就在原来的散列码基础上对5求余数。
11.在设计Hashcode方法时，最重要的就是同一个对象生成的散列码应该相同，否则在get的时候就无法取到该值。因此，散列码得生成不能依赖易变的数组或者是唯一性的数据。
12.hashCode方法的编写规则
1）生成散列码得速度必须快，并且有意义（即必须基于对象内容生成散列码）；
2）散列码不必是独一无二的（重点关注速度，而不是唯一性）；
3）散列码分布必须均匀；
怎么样编写hashCode方法，JoshuaBlock给出了一个基本的指导
1）给int变量result赋值非零常量，例如17；
2）给对象内每个有意义的域f，计算出一个int散列码c；
3）把计算得出的散列码合并；
例如：
publicclassCountedString{
privatestaticList<String>created=newArrayList<String>();
privateStrings;
privateintid=0;
publicCountedString(Stringstr){
s=str;
created.add(s);
//idisthetotalnumberofinstances
//ofthisstringinusebyCountedString:
for(Strings2:created)
if(s2.equals(s))
id++;
}
publicStringtoString(){
return"String:"+s+"id:"+id+"hashCode():"+hashCode();
}
publicinthashCode(){
//Theverysimpleapproach:
//returns.hashCode()*id;
//UsingJoshuaBloch'srecipe:
intresult=17;
result=37*result+s.hashCode();
result=37*result+id;
returnresult;
}
}
依照上面的指导原则，大致可以生成一个均匀分布的散列码
