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

Commit8c2cbd3

Browse files
author
jsquared21
committed
Add Ex_27_02
1 parent90d8a24 commit8c2cbd3

File tree

7 files changed

+357
-0
lines changed

7 files changed

+357
-0
lines changed
Binary file not shown.
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
/*******************************************************************************
2+
* (Implement MyMap using open addressing with quadratic probing) Create a new *
3+
* concrete class that implements MyMap using open addressing with quadratic *
4+
* probing. For simplicity, use f(key) = key % size as the hash function, where *
5+
* size is the hash-table size. Initially, the hash-table size is 4. The table *
6+
* size is doubled whenever the load factor exceeds the threshold (0.5). *
7+
*******************************************************************************/
8+
publicclassExercise_27_02 {
9+
publicstaticvoidmain(String[]arg) {
10+
// Create a map
11+
MyMap<String,Integer>map =newMyHashMap<>();
12+
map.put("Smith",30);
13+
map.put("Anderson",31);
14+
map.put("Lewis",29);
15+
map.put("Cook",29);
16+
map.put("Tom",21);
17+
map.put("Mark",21);
18+
map.put("Smith",65);
19+
map.put("William",21);
20+
21+
System.out.println("Entries in map: " +map);
22+
23+
System.out.println("The age of Lewis is " +
24+
map.get("Lewis"));
25+
26+
System.out.println("The age of William is " +
27+
map.get("William"));
28+
29+
System.out.println("Is Smith in the map? " +
30+
map.containsKey("Smith"));
31+
32+
System.out.println("Is Jay in the map? " +
33+
map.containsKey("Jay"));
34+
35+
System.out.println("Is age 33 in the map? " +
36+
map.containsValue(33));
37+
38+
System.out.println("Is age 31 in the map? " +
39+
map.containsValue(31));
40+
41+
System.out.print("Keys in map: ");
42+
for (Stringkey :map.keySet()) {
43+
System.out.print(key +" ");
44+
}
45+
System.out.println();
46+
47+
System.out.print("Values in map: ");
48+
for (intvalue :map.values()) {
49+
System.out.print(value +" ");
50+
}
51+
System.out.println();
52+
53+
map.remove("Smith");
54+
System.out.println("Entries in map " +map);
55+
56+
map.clear();
57+
System.out.println("Entries in map " +map);
58+
}
59+
}
4.41 KB
Binary file not shown.
Lines changed: 239 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,239 @@
1+
importjava.util.ArrayList;
2+
3+
publicclassMyHashMap<K,V>implementsMyMap<K,V> {
4+
// Define the default hash-table size. Must be a 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+
ArrayList<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 of 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 (inti =0;i <capacity;i++) {
68+
if (table.get(i) !=null &&table.get(i).getValue() ==value)
69+
returntrue;
70+
}
71+
72+
returnfalse;
73+
}
74+
75+
@Override/** Return a set of entries in the map */
76+
publicjava.util.Set<MyMap.Entry<K,V>>entrySet() {
77+
java.util.Set<MyMap.Entry<K,V>>set =
78+
newjava.util.HashSet<>();
79+
80+
for (inti =0;i <capacity;i++) {
81+
if (table.get(i) !=null) {
82+
set.add(table.get(i));
83+
}
84+
}
85+
86+
returnset;
87+
}
88+
89+
@Override/** Return the value that matches the specified key */
90+
publicVget(Kkey) {
91+
intindex =hash(key.hashCode());
92+
inti =index -1;// One cycle of the arraylist
93+
intj =0;
94+
95+
while (index !=i && (table.get(index) ==null ||
96+
table.get(index).getKey() !=key)) {
97+
index +=Math.pow(j++,2);
98+
index %=capacity;
99+
}
100+
101+
if (table.get(index).getKey() ==key)
102+
returntable.get(index).getValue();
103+
104+
returnnull;
105+
}
106+
107+
@Override/** Return true if this map contains no entries */
108+
publicbooleanisEmpty() {
109+
returnsize ==0;
110+
}
111+
112+
@Override/** Return a set consisting of the keys in this map */
113+
publicjava.util.Set<K>keySet() {
114+
java.util.Set<K>set =newjava.util.HashSet<>();
115+
116+
for (inti =0;i <capacity;i++) {
117+
if (table.get(i) !=null) {
118+
set.add(table.get(i).getKey());
119+
}
120+
}
121+
122+
returnset;
123+
}
124+
125+
@Override/** Add an entry (key, value) into the map */
126+
publicVput(Kkey,Vvalue) {
127+
intindex =hash(key.hashCode());
128+
intj =0;
129+
130+
while (table.get(index) !=null) {
131+
// Add a new entry (key, value)
132+
if (table.get(index).getKey() ==key) {
133+
Entry<K,V>entry =table.get(index);
134+
VoldValue =entry.getValue();
135+
// Replace old value with new value
136+
entry.value =value;
137+
table.set(index,entry);
138+
// Return the old value for the key
139+
returnoldValue;
140+
}
141+
142+
index +=Math.pow(j++,2);
143+
index %=capacity;
144+
}
145+
146+
// Check load factor
147+
if (size >=capacity *loadFactorThreshold) {
148+
if (capacity ==MAXIMUM_CAPACITY)
149+
thrownewRuntimeException("Exceeding maximum capacity");
150+
rehash();
151+
}
152+
153+
// Add a new entry(key, value) to hashtable
154+
table.set(index,newMyMap.Entry<K,V>(key,value));
155+
156+
size++;// Increase size
157+
158+
returnvalue;
159+
}
160+
161+
@Override/** Remove the entry for the specified key */
162+
publicvoidremove(Kkey) {
163+
intindex =hash(key.hashCode());
164+
inti =index -1;// One cycle of the arraylist
165+
intj =0;
166+
167+
while ((table.get(index) ==null ||
168+
table.get(index).getKey() !=key) &&i !=index) {
169+
index +=Math.pow(j++,2);
170+
index %=capacity;
171+
}
172+
173+
if (table.get(index).getKey() ==key)
174+
table.remove(index);
175+
}
176+
177+
@Override/** Return the number of entries in this map */
178+
publicintsize() {
179+
returnsize;
180+
}
181+
182+
@Override/** Return a set consisting of values in this map */
183+
publicjava.util.Set<V>values() {
184+
java.util.Set<V>set =newjava.util.HashSet<>();
185+
186+
for (inti =0;i <capacity;i++) {
187+
if (table.get(i) !=null)
188+
set.add(table.get(i).getValue());
189+
}
190+
191+
returnset;
192+
}
193+
/** Hash function */
194+
privateinthash(inthashCode) {
195+
returnsupplementalHash(hashCode) & (capacity -1);
196+
}
197+
198+
/** Ensure the hashing is evenly distributed */
199+
privatestaticintsupplementalHash(inth) {
200+
h ^= (h >>>20) ^ (h >>>12);
201+
returnh ^ (h >>>7) ^ (h >>>4);
202+
}
203+
204+
/** Return a power of 2 for initialCapacity */
205+
privateinttrimToPowerOf2(intinitialCapacity) {
206+
intcapacity =1;
207+
while (capacity <initialCapacity) {
208+
capacity <<=1;
209+
}
210+
211+
returncapacity;
212+
}
213+
214+
/** Remove all entries from map */
215+
privatevoidremoveEntries() {
216+
table.clear();
217+
}
218+
219+
/** Rehash the map */
220+
privatevoidrehash() {
221+
capacity <<=1;// Same as capacity *= 2. <= is more efficient
222+
for (inti = (size +1);i <capacity;i++) {
223+
table.add(null);
224+
}
225+
}
226+
227+
@Override/** Return a string repersentation for this map */
228+
publicStringtoString() {
229+
StringBuilderbuilder =newStringBuilder("[");
230+
231+
for (Entry<K,V>entry:table) {
232+
if (entry !=null &&table.size() >0)
233+
builder.append(entry);
234+
}
235+
236+
builder.append("]");
237+
returnbuilder.toString();
238+
}
239+
}
970 Bytes
Binary file not shown.
818 Bytes
Binary file not shown.

‎Exercise_27/Exercise_27_02/MyMap.java

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
publicinterfaceMyMap<K,V> {
2+
/** Remove all of the entries form 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 sontains 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 true if this map doesn't contain any entries */
18+
publicbooleanisEmpty();
19+
20+
/** Return a set consisting of the keys in this map */
21+
publicjava.util.Set<K>keySet();
22+
23+
/** Add an entry (key, value) into the map */
24+
publicVput(Kkey,Vvalue);
25+
26+
/** Remove entry for the specified key */
27+
publicvoidremove(Kkey);
28+
29+
/** Return the number of mappings in this map */
30+
publicintsize();
31+
32+
/** Return a set consisting of the values in this map */
33+
publicjava.util.Set<V>values();
34+
35+
/** Define an inner class for Entry */
36+
publicstaticclassEntry<K,V> {
37+
Kkey;
38+
Vvalue;
39+
40+
publicEntry(Kkey,Vvalue) {
41+
this.key =key;
42+
this.value =value;
43+
}
44+
45+
publicKgetKey() {
46+
returnkey;
47+
}
48+
49+
publicVgetValue() {
50+
returnvalue;
51+
}
52+
53+
@Override
54+
publicStringtoString() {
55+
return"[" +key +", " +value +"]";
56+
}
57+
}
58+
59+
}

0 commit comments

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