《Java语言程序设计基础篇》第10版 梁勇 著第二十七章练习题答案.docx

《Java语言程序设计基础篇》第10版 梁勇 著第二十七章练习题答案.docx

《《Java语言程序设计基础篇》第10版 梁勇 著第二十七章练习题答案.docx》由会员分享，可在线阅读，更多相关《《Java语言程序设计基础篇》第10版 梁勇 著第二十七章练习题答案.docx（104页珍藏版）》请在冰点文库上搜索。

《Java语言程序设计基础篇》第10版梁勇著第二十七章练习题答案

《Java语言程序设计（基础篇）》（第10版梁勇著）

第二十七章练习题答案

27.1

publicclassExercise27_01{

/**Mainmethod*/

publicstaticvoidmain（String[]args）{

MyHashMapmap=newMyHashMap<>（）;

map.put（2,2）;

System.out.println（"Iskey2inthemap?

"+map.containsKey

（2））;

map.remove

（2）;

System.out.println（"Iskey2inthemap?

"+map.containsKey

（2））;

}

staticclassMyHashMapimplementsMyMap{

//Definethedefaulthashtablesize.

privatestaticintDEFAULT_INITIAL_CAPACITY=4;

//Definethemaximumhashtablesize.1<<30issameas2^30

privatestaticintMAXIMUM_CAPACITY=1<<30;

//Currenthashtablecapacity.

privateintcapacity;

//Definedefaultloadfactor

privatestaticfloatDEFAULT_MAX_LOAD_FACTOR=0.5f;

//Specifyaloadfactorusedinthehashtable

privatefloatloadFactorThreshold;

//Thenumberofentriesinthemap

privateintsize=0;

//Hashtableisanarraywitheachcellthatisalinkedlist

MyMap.Entry[]table;

/**Constructamapwiththedefaultcapacityandloadfactor*/

publicMyHashMap（）{

this（DEFAULT_INITIAL_CAPACITY,DEFAULT_MAX_LOAD_FACTOR）;

}

/**Constructamapwiththespecifiedinitialcapacityand

*defaultloadfactor*/

publicMyHashMap（intinitialCapacity）{

this（initialCapacity,DEFAULT_MAX_LOAD_FACTOR）;

}

/**Constructamapwiththespecifiedinitialcapacity

*andloadfactor*/

publicMyHashMap（intinitialCapacity,floatloadFactorThreshold）{

this.capacity=initialCapacity;

this.loadFactorThreshold=loadFactorThreshold;

table=newMyMap.Entry[capacity];

}

/**Removealloftheentriesfromthismap*/

publicvoidclear（）{

size=0;

removeEntries（）;

}

/**Returntrueifthespecifiedkeyisinthemap*/

publicbooleancontainsKey（Kkey）{

if（get（key）!

=null）

returntrue;

else

returnfalse;

}

/**Returntrueifthismapcontainsthespecifiedvalue*/

publicbooleancontainsValue（Vvalue）{

for（inti=0;i

if（table[i]!

=null&&table[i].value.equals（value））

returntrue;

returnfalse;

}

/**Returnasetofentriesinthemap*/

publicjava.util.Set>entrySet（）{

java.util.Set>set=

newjava.util.HashSet>（）;

for（inti=0;i

if（table[i]!

=null）

set.add（table[i]）;

returnset;

}

/**Returnthefirstvaluethatmatchesthespecifiedkey*/

publicVget（Kkey）{

//Performlinearprobing

inti=hash（key.hashCode（））;

while（table[i]!

=null）{

if（table[i].key!

=null&&table[i].key.equals（key））

returntable[i].value;

i=（i+1）%table.length;

}

returnnull;

}

/**Returnallvaluesforthespecifiedkeyinthismap*/

publicjava.util.SetgetAll（Kkey）{

java.util.Setset=newjava.util.HashSet（）;

for（inti=0;i

if（table[i]!

=null&&table[i].key.equals（key））

set.add（table[i].value）;

returnset;

}

/**Returntrueifthismapcontainsnoentries*/

publicbooleanisEmpty（）{

returnsize==0;

}

/**Returnasetconsistingofthekeysinthismap*/

publicjava.util.SetkeySet（）{

java.util.Setset=newjava.util.HashSet（）;

for（inti=0;i

if（table[i]!

=null）

set.add（table[i].key）;

returnset;

}

/**Addanentry（key,value）intothemap*/

publicVput（Kkey,Vvalue）{

if（size>=capacity*loadFactorThreshold）{

if（capacity==MAXIMUM_CAPACITY）

thrownewRuntimeException（"Exceedingmaximumcapacity"）;

rehash（）;

}

inti=hash（key.hashCode（））;

while（table[i]!

=null&&table[i].key!

=null）

i=（i+1）%table.length;

//Addanentry（key,value）tothetable

table[i]=newMyMap.Entry（key,value）;

size++;//Increasesize

returnvalue;

}

/**Removetheelementforthespecifiedkey*/

publicvoidremove（Kkey）{

inti=hash（key.hashCode（））;

while（table[i]!

=null&&（table[i].key==null||!

table[i].key.equals（key）））

i=（i+1）%table.length;

if（table[i]!

=null&&table[i].key.equals（key））{

//AspecialmarkerEntry（null,null）isplacedforthedeletedentry

table[i]=newMyMap.Entry（null,null）;

size--;

}

}

/**Returnthenumberofmappingsinthismap*/

publicintsize（）{

returnsize;

}

/**Returnasetconsistingofthevaluesinthismap*/

publicjava.util.Setvalues（）{

java.util.Setset=newjava.util.HashSet（）;

for（inti=0;i

if（table[i]!

=null）

set.add（table[i].value）;

returnset;

}

/**Hashfunction*/

privateinthash（inthashCode）{

returnhashCode%capacity;

//returnsupplementalHash（hashCode）&（capacity-1）;

}

/**Ensurethehashingisevenlydistributed*/

privatestaticintsupplementalHash（inth）{

h^=（h>>>20）^（h>>>12）;

returnh^（h>>>7）^（h>>>4）;

}

/**Removeallentriesfromeachbucket*/

privatevoidremoveEntries（）{

for（inti=0;i

table[i]=null;

}

/**Rehashthemap*/

privatevoidrehash（）{

java.util.Set>set=entrySet（）;//Getentries

capacity<<=1;//Doublecapacity

table=newEntry[capacity];//Createanewhashtable

size=0;//Clearsize

for（Entryentry:

set）{

put（entry.getKey（）,entry.getValue（））;//Storetonewtable

}

}

@Override/**Returnastringrepresentationforthismap*/

publicStringtoString（）{

StringBuilderbuilder=newStringBuilder（"["）;

for（inti=0;i

if（table[i]!

=null&&table[i].key!

=null）

builder.append（table[i].toString（））;

}

returnbuilder.append（"]"）.toString（）;

}

}

interfaceMyMap{

/**Removealloftheentriesfromthismap*/

publicvoidclear（）;

/**Returntrueifthespecifiedkeyisinthemap*/

publicbooleancontainsKey（Kkey）;

/**Returntrueifthismapcontainsthespecifiedvalue*/

publicbooleancontainsValue（Vvalue）;

/**Returnasetofentriesinthemap*/

publicjava.util.Set>entrySet（）;

/**Returnthefirstvaluethatmatchesthespecifiedkey*/

publicVget（Kkey）;

/**Returnallvaluesforthespecifiedkeyinthismap*/

publicjava.util.SetgetAll（Kkey）;

/**Returntrueifthismapcontainsnoentries*/

publicbooleanisEmpty（）;

/**Returnasetconsistingofthekeysinthismap*/

publicjava.util.SetkeySet（）;

/**Addanentry（key,value）intothemap*/

publicVput（Kkey,Vvalue）;

/**Removetheentriesforthespecifiedkey*/

publicvoidremove（Kkey）;

/**Returnthenumberofmappingsinthismap*/

publicintsize（）;

/**Returnasetconsistingofthevaluesinthismap*/

publicjava.util.Setvalues（）;

/**DefineinnerclassforEntry*/

publicstaticclassEntry{

Kkey;

Vvalue;

publicEntry（Kkey,Vvalue）{

this.key=key;

this.value=value;

}

publicKgetKey（）{

returnkey;

}

publicVgetValue（）{

returnvalue;

}

@Override

publicStringtoString（）{

return"["+key+","+value+"]";

}

}

}

}

27.2

publicclassExercise27_02{

/**Mainmethod*/

publicstaticvoidmain（String[]args）{

MyHashMapmap=newMyHashMap<>（）;

map.put（2,2）;

System.out.println（"Iskey2inthemap?

"+map.containsKey

（2））;

map.remove

（2）;

System.out.println（"Iskey2inthemap?

"+map.containsKey

（2））;

}

staticclassMyHashMapimplementsMyMap{

//Definethedefaulthashtablesize.

privatestaticintDEFAULT_INITIAL_CAPACITY=4;

//Definethemaximumhashtablesize.1<<30issameas2^30

privatestaticintMAXIMUM_CAPACITY=1<<30;

//Currenthashtablecapacity.

privateintcapacity;

//Definedefaultloadfactor

privatestaticfloatDEFAULT_MAX_LOAD_FACTOR=0.4f;

//Specifyaloadfactorusedinthehashtable

privatefloatloadFactorThreshold;

//Thenumberofentriesinthemap

privateintsize=0;

//Hashtableisanarraywitheachcellthatisalinkedlist

MyMap.Entry[]table;

/**Constructamapwiththedefaultcapacityandloadfactor*/

publicMyHashMap（）{

this（DEFAULT_INITIAL_CAPACITY,DEFAULT_MAX_LOAD_FACTOR）;

}

/**Constructamapwiththespecifiedinitialcapacityand

*defaultloadfactor*/

publicMyHashMap（intinitialCapacity）{

this（initialCapacity,DEFAULT_MAX_LOAD_FACTOR）;

}

/**Constructamapwiththespecifiedinitialcapacity

*andloadfactor*/

publicMyHashMap（intinitialCapacity,floatloadFactorThreshold）{

this.capacity=initialCapacity;

this.loadFactorThreshold=loadFactorThreshold;

table=newMyMap.Entry[capacity];

}

/**Removealloftheentriesfromthismap*/

publicvoidclear（）{

size=0;

removeEntries（）;

}

/**Returntrueifthespecifiedkeyisinthemap*/

publicbooleancontainsKey（Kkey）{

if（get（key）!

=null）

returntrue;

else

returnfalse;

}

/**Returntrueifthismapcontainsthespecifiedvalue*/

publicbooleancontainsValue（Vvalue）{

for（inti=0;i

if（table[i]!

=null&&table[i].value.equals（value））

returntrue;

returnfalse;

}

/**Returnasetofentriesinthemap*/

publicjava.util.Set>entrySet（）{

java.util.Set>set=

newjava.util.HashSet>（）;

for（inti=0;i

if（table[i]!

=null）

set.add（table[i]）;

returnset;

}

/**Returnthefirstvaluethatmatchesthespecifiedkey*/

publicVget（Kkey）{

//Performlinearprobing

intk=hash（key.hashCo