Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5d72fd3

Browse files
author
jsquared21
committed
Add Ex_27.4
1 parentfa2160f commit5d72fd3

File tree

7 files changed

+369
-0
lines changed

7 files changed

+369
-0
lines changed
2.53 KB
Binary file not shown.
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
/*********************************************************************************
2+
* (Modify MyHashMap with duplicate keys) Modify MyHashMap to allow duplicate *
3+
* keys for entries. You need to modify the implementation for the put(key,value) *
4+
* method. Also add a new method named getAll(key) that returns a set of values *
5+
* that match the key in the map. *
6+
*********************************************************************************/
7+
publicclassExercise_27_04 {
8+
publicstaticvoidmain(String[]args) {
9+
// Create a map
10+
MyMap<String,Integer>map =newMyHashMap<>();
11+
map.put("Smith",30);
12+
map.put("Anderson",31);
13+
map.put("Lewis",29);
14+
map.put("Cook",29);
15+
map.put("Tom",21);
16+
map.put("Mark",21);
17+
map.put("Smith",65);
18+
map.put("William",21);
19+
20+
System.out.println("Entries in map: " +map);
21+
22+
System.out.println("The age of Lewis is " +
23+
map.get("Lewis"));
24+
25+
System.out.println("The age of William is " +
26+
map.get("William"));
27+
28+
System.out.println("The age of all Smith entries " +
29+
map.getAll("Smith"));
30+
31+
System.out.println("Is Smith in the map? " +
32+
map.containsKey("Smith"));
33+
34+
System.out.println("Is jay in the map? " +
35+
map.containsKey("Jay"));
36+
37+
System.out.println("Is age 33 in the map? " +
38+
map.containsValue(33));
39+
40+
System.out.println("Is age 31 in the map? " +
41+
map.containsValue(31));
42+
43+
System.out.print("Keys in map: ");
44+
for (Stringkey :map.keySet()) {
45+
System.out.print(key +" ");
46+
}
47+
System.out.println();
48+
49+
System.out.print("Values in map: ");
50+
for (intvalue :map.values()) {
51+
System.out.print(value +" ");
52+
}
53+
System.out.println();
54+
55+
56+
map.remove("Smith");
57+
System.out.println("Entries in map " +map);
58+
59+
map.clear();
60+
System.out.println("Entries in map " +map);
61+
}
62+
}
4.42 KB
Binary file not shown.
Lines changed: 246 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,246 @@
1+
importjava.util.ArrayList;
2+
3+
publicclassMyHashMap<K,V>implementsMyMap<K,V> {
4+
// Define the default hash-table size. Must be power of 2
5+
privatestaticintDEFAULT_INITIAL_CAPACITY =4;
6+
7+
// Define the maximum hash-table size. 1 << 30 is same as 2 ^ 30
8+
privatestaticintMAXIMUM_CAPACITY =1 <<30;
9+
10+
// Current hash-table capacity. Capacity is a power of 2
11+
privateintcapacity;
12+
13+
// Define default load factor
14+
privatestaticfloatDEFAULT_MAX_LOAD_FACTOR =0.5f;
15+
16+
// Specify a load factor used in the hash table
17+
privatefloatloadFactorThreshold;
18+
19+
// The number of entries in the map
20+
privateintsize =0;
21+
22+
// Hash table is an ArrayList
23+
privateArrayList<MyMap.Entry<K,V>>table;
24+
25+
/** Construct a map with the default capacity and load factor */
26+
publicMyHashMap() {
27+
this(DEFAULT_INITIAL_CAPACITY,DEFAULT_MAX_LOAD_FACTOR);
28+
}
29+
30+
/** Construct a map with the specified initial capacity and
31+
* default load factor */
32+
publicMyHashMap(intinitialCapacity) {
33+
this(initialCapacity,DEFAULT_MAX_LOAD_FACTOR);
34+
}
35+
36+
/** Construct a map with the specified initial capacity
37+
* and load factor */
38+
publicMyHashMap(intinitialCapacity,floatloadFactorThreshold) {
39+
if (initialCapacity >MAXIMUM_CAPACITY)
40+
this.capacity =MAXIMUM_CAPACITY;
41+
else
42+
this.capacity =trimToPowerOf2(initialCapacity);
43+
44+
this.loadFactorThreshold =loadFactorThreshold;
45+
table =newArrayList<>();
46+
for (inti =0;i <capacity;i++) {
47+
table.add(null);
48+
}
49+
}
50+
51+
@Override/** Remove all the entries from this map */
52+
publicvoidclear() {
53+
size =0;
54+
removeEntries();
55+
}
56+
57+
@Override/** Return true if the specified key is in the map */
58+
publicbooleancontainsKey(Kkey) {
59+
if (get(key) !=null)
60+
returntrue;
61+
else
62+
returnfalse;
63+
}
64+
65+
@Override/** Return true if this map contains the value */
66+
publicbooleancontainsValue(Vvalue) {
67+
for (Entry<K,V>entry :table) {
68+
if (entry !=null &&entry.getValue() ==value) {
69+
returntrue;
70+
}
71+
}
72+
73+
returnfalse;
74+
}
75+
76+
@Override/** Return a set of entries in the map */
77+
publicjava.util.Set<Entry<K,V>>entrySet() {
78+
java.util.Set<Entry<K,V>>set =newjava.util.HashSet<>();
79+
80+
for (Entry<K,V>entry:table) {
81+
if (entry !=null)
82+
set.add(entry);
83+
}
84+
85+
returnset;
86+
}
87+
88+
@Override/** Return the value that matched the specified key */
89+
publicVget(Kkey) {
90+
intindex =hash(key.hashCode());
91+
inti =index -1;
92+
93+
while (i !=index && (table.get(index) ==null ||
94+
table.get(index).getKey() !=key)) {
95+
index++;
96+
index %=capacity;
97+
}
98+
99+
if (table.get(index).getKey() ==key) {
100+
returntable.get(index).getValue();
101+
}
102+
103+
returnnull;
104+
}
105+
106+
@Override/** Return a set of values that match the key in the map */
107+
publicjava.util.Set<V>getAll(Kkey) {
108+
java.util.Set<V>set =newjava.util.HashSet<>();
109+
intindex =hash(key.hashCode());
110+
inti =index -1;
111+
112+
while (i !=index) {
113+
if (table.get(index) !=null &&table.get(index).getKey() ==key) {
114+
set.add(table.get(index).getValue());
115+
}
116+
index++;
117+
index %=capacity;
118+
}
119+
120+
returnset;
121+
}
122+
123+
@Override/** Return true if this map contains no entries */
124+
publicbooleanisEmpty() {
125+
returnsize ==0;
126+
}
127+
128+
@Override/** Return a set consisting of the keys in this map */
129+
publicjava.util.Set<K>keySet() {
130+
java.util.Set<K>set =newjava.util.HashSet<>();
131+
132+
for (Entry<K,V>entry:table) {
133+
if (entry !=null)
134+
set.add(entry.getKey());
135+
}
136+
137+
returnset;
138+
}
139+
140+
@Override/** Add an entry (key, value) into the map */
141+
publicVput(Kkey,Vvalue) {
142+
intindex =hash(key.hashCode());
143+
144+
while (table.get(index) !=null) {
145+
index++;
146+
index %=capacity;
147+
}
148+
149+
if (size >=capacity *loadFactorThreshold) {
150+
if (capacity ==MAXIMUM_CAPACITY) {
151+
thrownewRuntimeException("Exceeding maximum capacity");
152+
}
153+
rehash();
154+
}
155+
156+
// Add a new entry (key, value) to hash table
157+
table.set(index,newMyMap.Entry<K,V>(key,value));
158+
159+
size++;// Increase size
160+
161+
returnvalue;
162+
}
163+
164+
@Override/** Remove the entry for the specified key */
165+
publicvoidremove(Kkey) {
166+
intindex =hash(key.hashCode());
167+
inti =index -1;
168+
169+
while (i !=index && (table.get(index) ==null ||
170+
table.get(index).getKey() !=key)) {
171+
index++;
172+
index %=capacity;
173+
}
174+
175+
if (table.get(index).getKey() ==key) {
176+
table.remove(index);
177+
}
178+
}
179+
180+
@Override/** Return the number of entries in this map */
181+
publicintsize() {
182+
returnsize;
183+
}
184+
185+
@Override/** Return a set consisting of all the values in this map */
186+
publicjava.util.Set<V>values() {
187+
java.util.Set<V>set =newjava.util.HashSet<>();
188+
189+
for (Entry<K,V>entry :table) {
190+
if (entry !=null) {
191+
set.add(entry.getValue());
192+
}
193+
}
194+
195+
returnset;
196+
}
197+
198+
/** Hash function */
199+
privateinthash(inthashCode) {
200+
returnsupplementalHash(hashCode) & (capacity -1);
201+
}
202+
203+
/** Ensure the hashing is evenly distributed */
204+
privateintsupplementalHash(inth) {
205+
h ^= (h >>>20) ^ (h >>>12);
206+
returnh ^ (h >>>7) ^ (h >>>4);
207+
}
208+
209+
/** Return a power of 2 for initialCapacity */
210+
privateinttrimToPowerOf2(intinitialcapacity) {
211+
intcapacity =1;
212+
while (capacity <initialcapacity) {
213+
capacity <<=1;
214+
}
215+
216+
returncapacity;
217+
218+
}
219+
220+
/** Remove all entries from map */
221+
privatevoidremoveEntries() {
222+
table.clear();
223+
}
224+
225+
/** Rehash the map */
226+
privatevoidrehash() {
227+
capacity <<=1;// Same as *= 2. <= is more efficient
228+
for (inti =size +1;i <capacity;i++) {
229+
table.add(null);
230+
}
231+
}
232+
233+
@Override
234+
publicStringtoString() {
235+
StringBuilderbuilder =newStringBuilder("[");
236+
237+
for (Entry<K,V>entry :table) {
238+
if (entry !=null &&size >0) {
239+
builder.append(entry);
240+
}
241+
}
242+
243+
builder.append("]");
244+
returnbuilder.toString();
245+
}
246+
}
970 Bytes
Binary file not shown.
909 Bytes
Binary file not shown.
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
publicinterfaceMyMap<K,V> {
2+
/** Remove all of the entries from this map */
3+
publicvoidclear();
4+
5+
/** Return true if the specified key is in the map */
6+
publicbooleancontainsKey(Kkey);
7+
8+
/** Return true if this map contains the specified value */
9+
publicbooleancontainsValue(Vvalue);
10+
11+
/** Return a set of entries in the map */
12+
publicjava.util.Set<Entry<K,V>>entrySet();
13+
14+
/** Return the value that matches the specified key */
15+
publicVget(Kkey);
16+
17+
/** Return a set of values that match the key in the map */
18+
publicjava.util.Set<V>getAll(Kkey);
19+
20+
/** Return true if this map doesn't contain any entries */
21+
publicbooleanisEmpty();
22+
23+
/** Return a set consisting of the keys in this map */
24+
publicjava.util.Set<K>keySet();
25+
26+
/** Add an entry (key, value) into the map */
27+
publicVput(Kkey,Vvalue);
28+
29+
/** Remove entry for the specified key */
30+
publicvoidremove(Kkey);
31+
32+
/** Return the number of mappings in this map */
33+
publicintsize();
34+
35+
/** Return a set consisting of the values in this map */
36+
publicjava.util.Set<V>values();
37+
38+
/** Define an inner class for Entry */
39+
publicclassEntry<K,V> {
40+
Kkey;
41+
Vvalue;
42+
43+
publicEntry(Kkey,Vvalue) {
44+
this.key =key;
45+
this.value =value;
46+
}
47+
48+
publicKgetKey() {
49+
returnkey;
50+
}
51+
52+
publicVgetValue() {
53+
returnvalue;
54+
}
55+
56+
@Override
57+
publicStringtoString() {
58+
return"[" +key +", " +value +"]";
59+
}
60+
}
61+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp