jaroslav@597
|
1 |
/*
|
jaroslav@597
|
2 |
* Copyright (c) 1994, 2011, Oracle and/or its affiliates. All rights reserved.
|
jaroslav@597
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
jaroslav@597
|
4 |
*
|
jaroslav@597
|
5 |
* This code is free software; you can redistribute it and/or modify it
|
jaroslav@597
|
6 |
* under the terms of the GNU General Public License version 2 only, as
|
jaroslav@597
|
7 |
* published by the Free Software Foundation. Oracle designates this
|
jaroslav@597
|
8 |
* particular file as subject to the "Classpath" exception as provided
|
jaroslav@597
|
9 |
* by Oracle in the LICENSE file that accompanied this code.
|
jaroslav@597
|
10 |
*
|
jaroslav@597
|
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT
|
jaroslav@597
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
jaroslav@597
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
jaroslav@597
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that
|
jaroslav@597
|
15 |
* accompanied this code).
|
jaroslav@597
|
16 |
*
|
jaroslav@597
|
17 |
* You should have received a copy of the GNU General Public License version
|
jaroslav@597
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation,
|
jaroslav@597
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
jaroslav@597
|
20 |
*
|
jaroslav@597
|
21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
|
jaroslav@597
|
22 |
* or visit www.oracle.com if you need additional information or have any
|
jaroslav@597
|
23 |
* questions.
|
jaroslav@597
|
24 |
*/
|
jaroslav@597
|
25 |
|
jaroslav@597
|
26 |
package java.util;
|
jaroslav@597
|
27 |
import java.io.*;
|
jaroslav@597
|
28 |
|
jaroslav@597
|
29 |
/**
|
jaroslav@597
|
30 |
* This class implements a hash table, which maps keys to values. Any
|
jaroslav@597
|
31 |
* non-<code>null</code> object can be used as a key or as a value. <p>
|
jaroslav@597
|
32 |
*
|
jaroslav@597
|
33 |
* To successfully store and retrieve objects from a hashtable, the
|
jaroslav@597
|
34 |
* objects used as keys must implement the <code>hashCode</code>
|
jaroslav@597
|
35 |
* method and the <code>equals</code> method. <p>
|
jaroslav@597
|
36 |
*
|
jaroslav@597
|
37 |
* An instance of <code>Hashtable</code> has two parameters that affect its
|
jaroslav@597
|
38 |
* performance: <i>initial capacity</i> and <i>load factor</i>. The
|
jaroslav@597
|
39 |
* <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
|
jaroslav@597
|
40 |
* <i>initial capacity</i> is simply the capacity at the time the hash table
|
jaroslav@597
|
41 |
* is created. Note that the hash table is <i>open</i>: in the case of a "hash
|
jaroslav@597
|
42 |
* collision", a single bucket stores multiple entries, which must be searched
|
jaroslav@597
|
43 |
* sequentially. The <i>load factor</i> is a measure of how full the hash
|
jaroslav@597
|
44 |
* table is allowed to get before its capacity is automatically increased.
|
jaroslav@597
|
45 |
* The initial capacity and load factor parameters are merely hints to
|
jaroslav@597
|
46 |
* the implementation. The exact details as to when and whether the rehash
|
jaroslav@597
|
47 |
* method is invoked are implementation-dependent.<p>
|
jaroslav@597
|
48 |
*
|
jaroslav@597
|
49 |
* Generally, the default load factor (.75) offers a good tradeoff between
|
jaroslav@597
|
50 |
* time and space costs. Higher values decrease the space overhead but
|
jaroslav@597
|
51 |
* increase the time cost to look up an entry (which is reflected in most
|
jaroslav@597
|
52 |
* <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
|
jaroslav@597
|
53 |
*
|
jaroslav@597
|
54 |
* The initial capacity controls a tradeoff between wasted space and the
|
jaroslav@597
|
55 |
* need for <code>rehash</code> operations, which are time-consuming.
|
jaroslav@597
|
56 |
* No <code>rehash</code> operations will <i>ever</i> occur if the initial
|
jaroslav@597
|
57 |
* capacity is greater than the maximum number of entries the
|
jaroslav@597
|
58 |
* <tt>Hashtable</tt> will contain divided by its load factor. However,
|
jaroslav@597
|
59 |
* setting the initial capacity too high can waste space.<p>
|
jaroslav@597
|
60 |
*
|
jaroslav@597
|
61 |
* If many entries are to be made into a <code>Hashtable</code>,
|
jaroslav@597
|
62 |
* creating it with a sufficiently large capacity may allow the
|
jaroslav@597
|
63 |
* entries to be inserted more efficiently than letting it perform
|
jaroslav@597
|
64 |
* automatic rehashing as needed to grow the table. <p>
|
jaroslav@597
|
65 |
*
|
jaroslav@597
|
66 |
* This example creates a hashtable of numbers. It uses the names of
|
jaroslav@597
|
67 |
* the numbers as keys:
|
jaroslav@597
|
68 |
* <pre> {@code
|
jaroslav@597
|
69 |
* Hashtable<String, Integer> numbers
|
jaroslav@597
|
70 |
* = new Hashtable<String, Integer>();
|
jaroslav@597
|
71 |
* numbers.put("one", 1);
|
jaroslav@597
|
72 |
* numbers.put("two", 2);
|
jaroslav@597
|
73 |
* numbers.put("three", 3);}</pre>
|
jaroslav@597
|
74 |
*
|
jaroslav@597
|
75 |
* <p>To retrieve a number, use the following code:
|
jaroslav@597
|
76 |
* <pre> {@code
|
jaroslav@597
|
77 |
* Integer n = numbers.get("two");
|
jaroslav@597
|
78 |
* if (n != null) {
|
jaroslav@597
|
79 |
* System.out.println("two = " + n);
|
jaroslav@597
|
80 |
* }}</pre>
|
jaroslav@597
|
81 |
*
|
jaroslav@597
|
82 |
* <p>The iterators returned by the <tt>iterator</tt> method of the collections
|
jaroslav@597
|
83 |
* returned by all of this class's "collection view methods" are
|
jaroslav@597
|
84 |
* <em>fail-fast</em>: if the Hashtable is structurally modified at any time
|
jaroslav@597
|
85 |
* after the iterator is created, in any way except through the iterator's own
|
jaroslav@597
|
86 |
* <tt>remove</tt> method, the iterator will throw a {@link
|
jaroslav@597
|
87 |
* ConcurrentModificationException}. Thus, in the face of concurrent
|
jaroslav@597
|
88 |
* modification, the iterator fails quickly and cleanly, rather than risking
|
jaroslav@597
|
89 |
* arbitrary, non-deterministic behavior at an undetermined time in the future.
|
jaroslav@597
|
90 |
* The Enumerations returned by Hashtable's keys and elements methods are
|
jaroslav@597
|
91 |
* <em>not</em> fail-fast.
|
jaroslav@597
|
92 |
*
|
jaroslav@597
|
93 |
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
|
jaroslav@597
|
94 |
* as it is, generally speaking, impossible to make any hard guarantees in the
|
jaroslav@597
|
95 |
* presence of unsynchronized concurrent modification. Fail-fast iterators
|
jaroslav@597
|
96 |
* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
|
jaroslav@597
|
97 |
* Therefore, it would be wrong to write a program that depended on this
|
jaroslav@597
|
98 |
* exception for its correctness: <i>the fail-fast behavior of iterators
|
jaroslav@597
|
99 |
* should be used only to detect bugs.</i>
|
jaroslav@597
|
100 |
*
|
jaroslav@597
|
101 |
* <p>As of the Java 2 platform v1.2, this class was retrofitted to
|
jaroslav@597
|
102 |
* implement the {@link Map} interface, making it a member of the
|
jaroslav@597
|
103 |
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
|
jaroslav@597
|
104 |
*
|
jaroslav@597
|
105 |
* Java Collections Framework</a>. Unlike the new collection
|
jaroslav@597
|
106 |
* implementations, {@code Hashtable} is synchronized. If a
|
jaroslav@597
|
107 |
* thread-safe implementation is not needed, it is recommended to use
|
jaroslav@597
|
108 |
* {@link HashMap} in place of {@code Hashtable}. If a thread-safe
|
jaroslav@597
|
109 |
* highly-concurrent implementation is desired, then it is recommended
|
jaroslav@597
|
110 |
* to use {@link java.util.concurrent.ConcurrentHashMap} in place of
|
jaroslav@597
|
111 |
* {@code Hashtable}.
|
jaroslav@597
|
112 |
*
|
jaroslav@597
|
113 |
* @author Arthur van Hoff
|
jaroslav@597
|
114 |
* @author Josh Bloch
|
jaroslav@597
|
115 |
* @author Neal Gafter
|
jaroslav@597
|
116 |
* @see Object#equals(java.lang.Object)
|
jaroslav@597
|
117 |
* @see Object#hashCode()
|
jaroslav@597
|
118 |
* @see Hashtable#rehash()
|
jaroslav@597
|
119 |
* @see Collection
|
jaroslav@597
|
120 |
* @see Map
|
jaroslav@597
|
121 |
* @see HashMap
|
jaroslav@597
|
122 |
* @see TreeMap
|
jaroslav@597
|
123 |
* @since JDK1.0
|
jaroslav@597
|
124 |
*/
|
jaroslav@597
|
125 |
public class Hashtable<K,V>
|
jaroslav@597
|
126 |
extends Dictionary<K,V>
|
jaroslav@597
|
127 |
implements Map<K,V>, Cloneable, java.io.Serializable {
|
jaroslav@597
|
128 |
|
jaroslav@597
|
129 |
/**
|
jaroslav@597
|
130 |
* The hash table data.
|
jaroslav@597
|
131 |
*/
|
jaroslav@597
|
132 |
private transient Entry[] table;
|
jaroslav@597
|
133 |
|
jaroslav@597
|
134 |
/**
|
jaroslav@597
|
135 |
* The total number of entries in the hash table.
|
jaroslav@597
|
136 |
*/
|
jaroslav@597
|
137 |
private transient int count;
|
jaroslav@597
|
138 |
|
jaroslav@597
|
139 |
/**
|
jaroslav@597
|
140 |
* The table is rehashed when its size exceeds this threshold. (The
|
jaroslav@597
|
141 |
* value of this field is (int)(capacity * loadFactor).)
|
jaroslav@597
|
142 |
*
|
jaroslav@597
|
143 |
* @serial
|
jaroslav@597
|
144 |
*/
|
jaroslav@597
|
145 |
private int threshold;
|
jaroslav@597
|
146 |
|
jaroslav@597
|
147 |
/**
|
jaroslav@597
|
148 |
* The load factor for the hashtable.
|
jaroslav@597
|
149 |
*
|
jaroslav@597
|
150 |
* @serial
|
jaroslav@597
|
151 |
*/
|
jaroslav@597
|
152 |
private float loadFactor;
|
jaroslav@597
|
153 |
|
jaroslav@597
|
154 |
/**
|
jaroslav@597
|
155 |
* The number of times this Hashtable has been structurally modified
|
jaroslav@597
|
156 |
* Structural modifications are those that change the number of entries in
|
jaroslav@597
|
157 |
* the Hashtable or otherwise modify its internal structure (e.g.,
|
jaroslav@597
|
158 |
* rehash). This field is used to make iterators on Collection-views of
|
jaroslav@597
|
159 |
* the Hashtable fail-fast. (See ConcurrentModificationException).
|
jaroslav@597
|
160 |
*/
|
jaroslav@597
|
161 |
private transient int modCount = 0;
|
jaroslav@597
|
162 |
|
jaroslav@597
|
163 |
/** use serialVersionUID from JDK 1.0.2 for interoperability */
|
jaroslav@597
|
164 |
private static final long serialVersionUID = 1421746759512286392L;
|
jaroslav@597
|
165 |
|
jaroslav@597
|
166 |
/**
|
jaroslav@597
|
167 |
* Constructs a new, empty hashtable with the specified initial
|
jaroslav@597
|
168 |
* capacity and the specified load factor.
|
jaroslav@597
|
169 |
*
|
jaroslav@597
|
170 |
* @param initialCapacity the initial capacity of the hashtable.
|
jaroslav@597
|
171 |
* @param loadFactor the load factor of the hashtable.
|
jaroslav@597
|
172 |
* @exception IllegalArgumentException if the initial capacity is less
|
jaroslav@597
|
173 |
* than zero, or if the load factor is nonpositive.
|
jaroslav@597
|
174 |
*/
|
jaroslav@597
|
175 |
public Hashtable(int initialCapacity, float loadFactor) {
|
jaroslav@597
|
176 |
if (initialCapacity < 0)
|
jaroslav@597
|
177 |
throw new IllegalArgumentException("Illegal Capacity: "+
|
jaroslav@597
|
178 |
initialCapacity);
|
jaroslav@597
|
179 |
if (loadFactor <= 0 || Float.isNaN(loadFactor))
|
jaroslav@597
|
180 |
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
|
jaroslav@597
|
181 |
|
jaroslav@597
|
182 |
if (initialCapacity==0)
|
jaroslav@597
|
183 |
initialCapacity = 1;
|
jaroslav@597
|
184 |
this.loadFactor = loadFactor;
|
jaroslav@597
|
185 |
table = new Entry[initialCapacity];
|
jaroslav@597
|
186 |
threshold = (int)(initialCapacity * loadFactor);
|
jaroslav@597
|
187 |
}
|
jaroslav@597
|
188 |
|
jaroslav@597
|
189 |
/**
|
jaroslav@597
|
190 |
* Constructs a new, empty hashtable with the specified initial capacity
|
jaroslav@597
|
191 |
* and default load factor (0.75).
|
jaroslav@597
|
192 |
*
|
jaroslav@597
|
193 |
* @param initialCapacity the initial capacity of the hashtable.
|
jaroslav@597
|
194 |
* @exception IllegalArgumentException if the initial capacity is less
|
jaroslav@597
|
195 |
* than zero.
|
jaroslav@597
|
196 |
*/
|
jaroslav@597
|
197 |
public Hashtable(int initialCapacity) {
|
jaroslav@597
|
198 |
this(initialCapacity, 0.75f);
|
jaroslav@597
|
199 |
}
|
jaroslav@597
|
200 |
|
jaroslav@597
|
201 |
/**
|
jaroslav@597
|
202 |
* Constructs a new, empty hashtable with a default initial capacity (11)
|
jaroslav@597
|
203 |
* and load factor (0.75).
|
jaroslav@597
|
204 |
*/
|
jaroslav@597
|
205 |
public Hashtable() {
|
jaroslav@597
|
206 |
this(11, 0.75f);
|
jaroslav@597
|
207 |
}
|
jaroslav@597
|
208 |
|
jaroslav@597
|
209 |
/**
|
jaroslav@597
|
210 |
* Constructs a new hashtable with the same mappings as the given
|
jaroslav@597
|
211 |
* Map. The hashtable is created with an initial capacity sufficient to
|
jaroslav@597
|
212 |
* hold the mappings in the given Map and a default load factor (0.75).
|
jaroslav@597
|
213 |
*
|
jaroslav@597
|
214 |
* @param t the map whose mappings are to be placed in this map.
|
jaroslav@597
|
215 |
* @throws NullPointerException if the specified map is null.
|
jaroslav@597
|
216 |
* @since 1.2
|
jaroslav@597
|
217 |
*/
|
jaroslav@597
|
218 |
public Hashtable(Map<? extends K, ? extends V> t) {
|
jaroslav@597
|
219 |
this(Math.max(2*t.size(), 11), 0.75f);
|
jaroslav@597
|
220 |
putAll(t);
|
jaroslav@597
|
221 |
}
|
jaroslav@597
|
222 |
|
jaroslav@597
|
223 |
/**
|
jaroslav@597
|
224 |
* Returns the number of keys in this hashtable.
|
jaroslav@597
|
225 |
*
|
jaroslav@597
|
226 |
* @return the number of keys in this hashtable.
|
jaroslav@597
|
227 |
*/
|
jaroslav@597
|
228 |
public synchronized int size() {
|
jaroslav@597
|
229 |
return count;
|
jaroslav@597
|
230 |
}
|
jaroslav@597
|
231 |
|
jaroslav@597
|
232 |
/**
|
jaroslav@597
|
233 |
* Tests if this hashtable maps no keys to values.
|
jaroslav@597
|
234 |
*
|
jaroslav@597
|
235 |
* @return <code>true</code> if this hashtable maps no keys to values;
|
jaroslav@597
|
236 |
* <code>false</code> otherwise.
|
jaroslav@597
|
237 |
*/
|
jaroslav@597
|
238 |
public synchronized boolean isEmpty() {
|
jaroslav@597
|
239 |
return count == 0;
|
jaroslav@597
|
240 |
}
|
jaroslav@597
|
241 |
|
jaroslav@597
|
242 |
/**
|
jaroslav@597
|
243 |
* Returns an enumeration of the keys in this hashtable.
|
jaroslav@597
|
244 |
*
|
jaroslav@597
|
245 |
* @return an enumeration of the keys in this hashtable.
|
jaroslav@597
|
246 |
* @see Enumeration
|
jaroslav@597
|
247 |
* @see #elements()
|
jaroslav@597
|
248 |
* @see #keySet()
|
jaroslav@597
|
249 |
* @see Map
|
jaroslav@597
|
250 |
*/
|
jaroslav@597
|
251 |
public synchronized Enumeration<K> keys() {
|
jaroslav@597
|
252 |
return this.<K>getEnumeration(KEYS);
|
jaroslav@597
|
253 |
}
|
jaroslav@597
|
254 |
|
jaroslav@597
|
255 |
/**
|
jaroslav@597
|
256 |
* Returns an enumeration of the values in this hashtable.
|
jaroslav@597
|
257 |
* Use the Enumeration methods on the returned object to fetch the elements
|
jaroslav@597
|
258 |
* sequentially.
|
jaroslav@597
|
259 |
*
|
jaroslav@597
|
260 |
* @return an enumeration of the values in this hashtable.
|
jaroslav@597
|
261 |
* @see java.util.Enumeration
|
jaroslav@597
|
262 |
* @see #keys()
|
jaroslav@597
|
263 |
* @see #values()
|
jaroslav@597
|
264 |
* @see Map
|
jaroslav@597
|
265 |
*/
|
jaroslav@597
|
266 |
public synchronized Enumeration<V> elements() {
|
jaroslav@597
|
267 |
return this.<V>getEnumeration(VALUES);
|
jaroslav@597
|
268 |
}
|
jaroslav@597
|
269 |
|
jaroslav@597
|
270 |
/**
|
jaroslav@597
|
271 |
* Tests if some key maps into the specified value in this hashtable.
|
jaroslav@597
|
272 |
* This operation is more expensive than the {@link #containsKey
|
jaroslav@597
|
273 |
* containsKey} method.
|
jaroslav@597
|
274 |
*
|
jaroslav@597
|
275 |
* <p>Note that this method is identical in functionality to
|
jaroslav@597
|
276 |
* {@link #containsValue containsValue}, (which is part of the
|
jaroslav@597
|
277 |
* {@link Map} interface in the collections framework).
|
jaroslav@597
|
278 |
*
|
jaroslav@597
|
279 |
* @param value a value to search for
|
jaroslav@597
|
280 |
* @return <code>true</code> if and only if some key maps to the
|
jaroslav@597
|
281 |
* <code>value</code> argument in this hashtable as
|
jaroslav@597
|
282 |
* determined by the <tt>equals</tt> method;
|
jaroslav@597
|
283 |
* <code>false</code> otherwise.
|
jaroslav@597
|
284 |
* @exception NullPointerException if the value is <code>null</code>
|
jaroslav@597
|
285 |
*/
|
jaroslav@597
|
286 |
public synchronized boolean contains(Object value) {
|
jaroslav@597
|
287 |
if (value == null) {
|
jaroslav@597
|
288 |
throw new NullPointerException();
|
jaroslav@597
|
289 |
}
|
jaroslav@597
|
290 |
|
jaroslav@597
|
291 |
Entry tab[] = table;
|
jaroslav@597
|
292 |
for (int i = tab.length ; i-- > 0 ;) {
|
jaroslav@597
|
293 |
for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
|
jaroslav@597
|
294 |
if (e.value.equals(value)) {
|
jaroslav@597
|
295 |
return true;
|
jaroslav@597
|
296 |
}
|
jaroslav@597
|
297 |
}
|
jaroslav@597
|
298 |
}
|
jaroslav@597
|
299 |
return false;
|
jaroslav@597
|
300 |
}
|
jaroslav@597
|
301 |
|
jaroslav@597
|
302 |
/**
|
jaroslav@597
|
303 |
* Returns true if this hashtable maps one or more keys to this value.
|
jaroslav@597
|
304 |
*
|
jaroslav@597
|
305 |
* <p>Note that this method is identical in functionality to {@link
|
jaroslav@597
|
306 |
* #contains contains} (which predates the {@link Map} interface).
|
jaroslav@597
|
307 |
*
|
jaroslav@597
|
308 |
* @param value value whose presence in this hashtable is to be tested
|
jaroslav@597
|
309 |
* @return <tt>true</tt> if this map maps one or more keys to the
|
jaroslav@597
|
310 |
* specified value
|
jaroslav@597
|
311 |
* @throws NullPointerException if the value is <code>null</code>
|
jaroslav@597
|
312 |
* @since 1.2
|
jaroslav@597
|
313 |
*/
|
jaroslav@597
|
314 |
public boolean containsValue(Object value) {
|
jaroslav@597
|
315 |
return contains(value);
|
jaroslav@597
|
316 |
}
|
jaroslav@597
|
317 |
|
jaroslav@597
|
318 |
/**
|
jaroslav@597
|
319 |
* Tests if the specified object is a key in this hashtable.
|
jaroslav@597
|
320 |
*
|
jaroslav@597
|
321 |
* @param key possible key
|
jaroslav@597
|
322 |
* @return <code>true</code> if and only if the specified object
|
jaroslav@597
|
323 |
* is a key in this hashtable, as determined by the
|
jaroslav@597
|
324 |
* <tt>equals</tt> method; <code>false</code> otherwise.
|
jaroslav@597
|
325 |
* @throws NullPointerException if the key is <code>null</code>
|
jaroslav@597
|
326 |
* @see #contains(Object)
|
jaroslav@597
|
327 |
*/
|
jaroslav@597
|
328 |
public synchronized boolean containsKey(Object key) {
|
jaroslav@597
|
329 |
Entry tab[] = table;
|
jaroslav@597
|
330 |
int hash = key.hashCode();
|
jaroslav@597
|
331 |
int index = (hash & 0x7FFFFFFF) % tab.length;
|
jaroslav@597
|
332 |
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
|
jaroslav@597
|
333 |
if ((e.hash == hash) && e.key.equals(key)) {
|
jaroslav@597
|
334 |
return true;
|
jaroslav@597
|
335 |
}
|
jaroslav@597
|
336 |
}
|
jaroslav@597
|
337 |
return false;
|
jaroslav@597
|
338 |
}
|
jaroslav@597
|
339 |
|
jaroslav@597
|
340 |
/**
|
jaroslav@597
|
341 |
* Returns the value to which the specified key is mapped,
|
jaroslav@597
|
342 |
* or {@code null} if this map contains no mapping for the key.
|
jaroslav@597
|
343 |
*
|
jaroslav@597
|
344 |
* <p>More formally, if this map contains a mapping from a key
|
jaroslav@597
|
345 |
* {@code k} to a value {@code v} such that {@code (key.equals(k))},
|
jaroslav@597
|
346 |
* then this method returns {@code v}; otherwise it returns
|
jaroslav@597
|
347 |
* {@code null}. (There can be at most one such mapping.)
|
jaroslav@597
|
348 |
*
|
jaroslav@597
|
349 |
* @param key the key whose associated value is to be returned
|
jaroslav@597
|
350 |
* @return the value to which the specified key is mapped, or
|
jaroslav@597
|
351 |
* {@code null} if this map contains no mapping for the key
|
jaroslav@597
|
352 |
* @throws NullPointerException if the specified key is null
|
jaroslav@597
|
353 |
* @see #put(Object, Object)
|
jaroslav@597
|
354 |
*/
|
jaroslav@597
|
355 |
public synchronized V get(Object key) {
|
jaroslav@597
|
356 |
Entry tab[] = table;
|
jaroslav@597
|
357 |
int hash = key.hashCode();
|
jaroslav@597
|
358 |
int index = (hash & 0x7FFFFFFF) % tab.length;
|
jaroslav@597
|
359 |
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
|
jaroslav@597
|
360 |
if ((e.hash == hash) && e.key.equals(key)) {
|
jaroslav@597
|
361 |
return e.value;
|
jaroslav@597
|
362 |
}
|
jaroslav@597
|
363 |
}
|
jaroslav@597
|
364 |
return null;
|
jaroslav@597
|
365 |
}
|
jaroslav@597
|
366 |
|
jaroslav@597
|
367 |
/**
|
jaroslav@597
|
368 |
* The maximum size of array to allocate.
|
jaroslav@597
|
369 |
* Some VMs reserve some header words in an array.
|
jaroslav@597
|
370 |
* Attempts to allocate larger arrays may result in
|
jaroslav@597
|
371 |
* OutOfMemoryError: Requested array size exceeds VM limit
|
jaroslav@597
|
372 |
*/
|
jaroslav@597
|
373 |
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
|
jaroslav@597
|
374 |
|
jaroslav@597
|
375 |
/**
|
jaroslav@597
|
376 |
* Increases the capacity of and internally reorganizes this
|
jaroslav@597
|
377 |
* hashtable, in order to accommodate and access its entries more
|
jaroslav@597
|
378 |
* efficiently. This method is called automatically when the
|
jaroslav@597
|
379 |
* number of keys in the hashtable exceeds this hashtable's capacity
|
jaroslav@597
|
380 |
* and load factor.
|
jaroslav@597
|
381 |
*/
|
jaroslav@597
|
382 |
protected void rehash() {
|
jaroslav@597
|
383 |
int oldCapacity = table.length;
|
jaroslav@597
|
384 |
Entry[] oldMap = table;
|
jaroslav@597
|
385 |
|
jaroslav@597
|
386 |
// overflow-conscious code
|
jaroslav@597
|
387 |
int newCapacity = (oldCapacity << 1) + 1;
|
jaroslav@597
|
388 |
if (newCapacity - MAX_ARRAY_SIZE > 0) {
|
jaroslav@597
|
389 |
if (oldCapacity == MAX_ARRAY_SIZE)
|
jaroslav@597
|
390 |
// Keep running with MAX_ARRAY_SIZE buckets
|
jaroslav@597
|
391 |
return;
|
jaroslav@597
|
392 |
newCapacity = MAX_ARRAY_SIZE;
|
jaroslav@597
|
393 |
}
|
jaroslav@597
|
394 |
Entry[] newMap = new Entry[newCapacity];
|
jaroslav@597
|
395 |
|
jaroslav@597
|
396 |
modCount++;
|
jaroslav@597
|
397 |
threshold = (int)(newCapacity * loadFactor);
|
jaroslav@597
|
398 |
table = newMap;
|
jaroslav@597
|
399 |
|
jaroslav@597
|
400 |
for (int i = oldCapacity ; i-- > 0 ;) {
|
jaroslav@597
|
401 |
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
|
jaroslav@597
|
402 |
Entry<K,V> e = old;
|
jaroslav@597
|
403 |
old = old.next;
|
jaroslav@597
|
404 |
|
jaroslav@597
|
405 |
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
|
jaroslav@597
|
406 |
e.next = newMap[index];
|
jaroslav@597
|
407 |
newMap[index] = e;
|
jaroslav@597
|
408 |
}
|
jaroslav@597
|
409 |
}
|
jaroslav@597
|
410 |
}
|
jaroslav@597
|
411 |
|
jaroslav@597
|
412 |
/**
|
jaroslav@597
|
413 |
* Maps the specified <code>key</code> to the specified
|
jaroslav@597
|
414 |
* <code>value</code> in this hashtable. Neither the key nor the
|
jaroslav@597
|
415 |
* value can be <code>null</code>. <p>
|
jaroslav@597
|
416 |
*
|
jaroslav@597
|
417 |
* The value can be retrieved by calling the <code>get</code> method
|
jaroslav@597
|
418 |
* with a key that is equal to the original key.
|
jaroslav@597
|
419 |
*
|
jaroslav@597
|
420 |
* @param key the hashtable key
|
jaroslav@597
|
421 |
* @param value the value
|
jaroslav@597
|
422 |
* @return the previous value of the specified key in this hashtable,
|
jaroslav@597
|
423 |
* or <code>null</code> if it did not have one
|
jaroslav@597
|
424 |
* @exception NullPointerException if the key or value is
|
jaroslav@597
|
425 |
* <code>null</code>
|
jaroslav@597
|
426 |
* @see Object#equals(Object)
|
jaroslav@597
|
427 |
* @see #get(Object)
|
jaroslav@597
|
428 |
*/
|
jaroslav@597
|
429 |
public synchronized V put(K key, V value) {
|
jaroslav@597
|
430 |
// Make sure the value is not null
|
jaroslav@597
|
431 |
if (value == null) {
|
jaroslav@597
|
432 |
throw new NullPointerException();
|
jaroslav@597
|
433 |
}
|
jaroslav@597
|
434 |
|
jaroslav@597
|
435 |
// Makes sure the key is not already in the hashtable.
|
jaroslav@597
|
436 |
Entry tab[] = table;
|
jaroslav@597
|
437 |
int hash = key.hashCode();
|
jaroslav@597
|
438 |
int index = (hash & 0x7FFFFFFF) % tab.length;
|
jaroslav@597
|
439 |
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
|
jaroslav@597
|
440 |
if ((e.hash == hash) && e.key.equals(key)) {
|
jaroslav@597
|
441 |
V old = e.value;
|
jaroslav@597
|
442 |
e.value = value;
|
jaroslav@597
|
443 |
return old;
|
jaroslav@597
|
444 |
}
|
jaroslav@597
|
445 |
}
|
jaroslav@597
|
446 |
|
jaroslav@597
|
447 |
modCount++;
|
jaroslav@597
|
448 |
if (count >= threshold) {
|
jaroslav@597
|
449 |
// Rehash the table if the threshold is exceeded
|
jaroslav@597
|
450 |
rehash();
|
jaroslav@597
|
451 |
|
jaroslav@597
|
452 |
tab = table;
|
jaroslav@597
|
453 |
index = (hash & 0x7FFFFFFF) % tab.length;
|
jaroslav@597
|
454 |
}
|
jaroslav@597
|
455 |
|
jaroslav@597
|
456 |
// Creates the new entry.
|
jaroslav@597
|
457 |
Entry<K,V> e = tab[index];
|
jaroslav@597
|
458 |
tab[index] = new Entry<>(hash, key, value, e);
|
jaroslav@597
|
459 |
count++;
|
jaroslav@597
|
460 |
return null;
|
jaroslav@597
|
461 |
}
|
jaroslav@597
|
462 |
|
jaroslav@597
|
463 |
/**
|
jaroslav@597
|
464 |
* Removes the key (and its corresponding value) from this
|
jaroslav@597
|
465 |
* hashtable. This method does nothing if the key is not in the hashtable.
|
jaroslav@597
|
466 |
*
|
jaroslav@597
|
467 |
* @param key the key that needs to be removed
|
jaroslav@597
|
468 |
* @return the value to which the key had been mapped in this hashtable,
|
jaroslav@597
|
469 |
* or <code>null</code> if the key did not have a mapping
|
jaroslav@597
|
470 |
* @throws NullPointerException if the key is <code>null</code>
|
jaroslav@597
|
471 |
*/
|
jaroslav@597
|
472 |
public synchronized V remove(Object key) {
|
jaroslav@597
|
473 |
Entry tab[] = table;
|
jaroslav@597
|
474 |
int hash = key.hashCode();
|
jaroslav@597
|
475 |
int index = (hash & 0x7FFFFFFF) % tab.length;
|
jaroslav@597
|
476 |
for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
|
jaroslav@597
|
477 |
if ((e.hash == hash) && e.key.equals(key)) {
|
jaroslav@597
|
478 |
modCount++;
|
jaroslav@597
|
479 |
if (prev != null) {
|
jaroslav@597
|
480 |
prev.next = e.next;
|
jaroslav@597
|
481 |
} else {
|
jaroslav@597
|
482 |
tab[index] = e.next;
|
jaroslav@597
|
483 |
}
|
jaroslav@597
|
484 |
count--;
|
jaroslav@597
|
485 |
V oldValue = e.value;
|
jaroslav@597
|
486 |
e.value = null;
|
jaroslav@597
|
487 |
return oldValue;
|
jaroslav@597
|
488 |
}
|
jaroslav@597
|
489 |
}
|
jaroslav@597
|
490 |
return null;
|
jaroslav@597
|
491 |
}
|
jaroslav@597
|
492 |
|
jaroslav@597
|
493 |
/**
|
jaroslav@597
|
494 |
* Copies all of the mappings from the specified map to this hashtable.
|
jaroslav@597
|
495 |
* These mappings will replace any mappings that this hashtable had for any
|
jaroslav@597
|
496 |
* of the keys currently in the specified map.
|
jaroslav@597
|
497 |
*
|
jaroslav@597
|
498 |
* @param t mappings to be stored in this map
|
jaroslav@597
|
499 |
* @throws NullPointerException if the specified map is null
|
jaroslav@597
|
500 |
* @since 1.2
|
jaroslav@597
|
501 |
*/
|
jaroslav@597
|
502 |
public synchronized void putAll(Map<? extends K, ? extends V> t) {
|
jaroslav@597
|
503 |
for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
|
jaroslav@597
|
504 |
put(e.getKey(), e.getValue());
|
jaroslav@597
|
505 |
}
|
jaroslav@597
|
506 |
|
jaroslav@597
|
507 |
/**
|
jaroslav@597
|
508 |
* Clears this hashtable so that it contains no keys.
|
jaroslav@597
|
509 |
*/
|
jaroslav@597
|
510 |
public synchronized void clear() {
|
jaroslav@597
|
511 |
Entry tab[] = table;
|
jaroslav@597
|
512 |
modCount++;
|
jaroslav@597
|
513 |
for (int index = tab.length; --index >= 0; )
|
jaroslav@597
|
514 |
tab[index] = null;
|
jaroslav@597
|
515 |
count = 0;
|
jaroslav@597
|
516 |
}
|
jaroslav@597
|
517 |
|
jaroslav@597
|
518 |
/**
|
jaroslav@597
|
519 |
* Creates a shallow copy of this hashtable. All the structure of the
|
jaroslav@597
|
520 |
* hashtable itself is copied, but the keys and values are not cloned.
|
jaroslav@597
|
521 |
* This is a relatively expensive operation.
|
jaroslav@597
|
522 |
*
|
jaroslav@597
|
523 |
* @return a clone of the hashtable
|
jaroslav@597
|
524 |
*/
|
jaroslav@597
|
525 |
public synchronized Object clone() {
|
jaroslav@597
|
526 |
try {
|
jaroslav@597
|
527 |
Hashtable<K,V> t = (Hashtable<K,V>) super.clone();
|
jaroslav@597
|
528 |
t.table = new Entry[table.length];
|
jaroslav@597
|
529 |
for (int i = table.length ; i-- > 0 ; ) {
|
jaroslav@597
|
530 |
t.table[i] = (table[i] != null)
|
jaroslav@597
|
531 |
? (Entry<K,V>) table[i].clone() : null;
|
jaroslav@597
|
532 |
}
|
jaroslav@597
|
533 |
t.keySet = null;
|
jaroslav@597
|
534 |
t.entrySet = null;
|
jaroslav@597
|
535 |
t.values = null;
|
jaroslav@597
|
536 |
t.modCount = 0;
|
jaroslav@597
|
537 |
return t;
|
jaroslav@597
|
538 |
} catch (CloneNotSupportedException e) {
|
jaroslav@597
|
539 |
// this shouldn't happen, since we are Cloneable
|
jaroslav@597
|
540 |
throw new InternalError();
|
jaroslav@597
|
541 |
}
|
jaroslav@597
|
542 |
}
|
jaroslav@597
|
543 |
|
jaroslav@597
|
544 |
/**
|
jaroslav@597
|
545 |
* Returns a string representation of this <tt>Hashtable</tt> object
|
jaroslav@597
|
546 |
* in the form of a set of entries, enclosed in braces and separated
|
jaroslav@597
|
547 |
* by the ASCII characters "<tt>, </tt>" (comma and space). Each
|
jaroslav@597
|
548 |
* entry is rendered as the key, an equals sign <tt>=</tt>, and the
|
jaroslav@597
|
549 |
* associated element, where the <tt>toString</tt> method is used to
|
jaroslav@597
|
550 |
* convert the key and element to strings.
|
jaroslav@597
|
551 |
*
|
jaroslav@597
|
552 |
* @return a string representation of this hashtable
|
jaroslav@597
|
553 |
*/
|
jaroslav@597
|
554 |
public synchronized String toString() {
|
jaroslav@597
|
555 |
int max = size() - 1;
|
jaroslav@597
|
556 |
if (max == -1)
|
jaroslav@597
|
557 |
return "{}";
|
jaroslav@597
|
558 |
|
jaroslav@597
|
559 |
StringBuilder sb = new StringBuilder();
|
jaroslav@597
|
560 |
Iterator<Map.Entry<K,V>> it = entrySet().iterator();
|
jaroslav@597
|
561 |
|
jaroslav@597
|
562 |
sb.append('{');
|
jaroslav@597
|
563 |
for (int i = 0; ; i++) {
|
jaroslav@597
|
564 |
Map.Entry<K,V> e = it.next();
|
jaroslav@597
|
565 |
K key = e.getKey();
|
jaroslav@597
|
566 |
V value = e.getValue();
|
jaroslav@597
|
567 |
sb.append(key == this ? "(this Map)" : key.toString());
|
jaroslav@597
|
568 |
sb.append('=');
|
jaroslav@597
|
569 |
sb.append(value == this ? "(this Map)" : value.toString());
|
jaroslav@597
|
570 |
|
jaroslav@597
|
571 |
if (i == max)
|
jaroslav@597
|
572 |
return sb.append('}').toString();
|
jaroslav@597
|
573 |
sb.append(", ");
|
jaroslav@597
|
574 |
}
|
jaroslav@597
|
575 |
}
|
jaroslav@597
|
576 |
|
jaroslav@597
|
577 |
|
jaroslav@597
|
578 |
private <T> Enumeration<T> getEnumeration(int type) {
|
jaroslav@597
|
579 |
if (count == 0) {
|
jaroslav@597
|
580 |
return Collections.emptyEnumeration();
|
jaroslav@597
|
581 |
} else {
|
jaroslav@597
|
582 |
return new Enumerator<>(type, false);
|
jaroslav@597
|
583 |
}
|
jaroslav@597
|
584 |
}
|
jaroslav@597
|
585 |
|
jaroslav@597
|
586 |
private <T> Iterator<T> getIterator(int type) {
|
jaroslav@597
|
587 |
if (count == 0) {
|
jaroslav@597
|
588 |
return Collections.emptyIterator();
|
jaroslav@597
|
589 |
} else {
|
jaroslav@597
|
590 |
return new Enumerator<>(type, true);
|
jaroslav@597
|
591 |
}
|
jaroslav@597
|
592 |
}
|
jaroslav@597
|
593 |
|
jaroslav@597
|
594 |
// Views
|
jaroslav@597
|
595 |
|
jaroslav@597
|
596 |
/**
|
jaroslav@597
|
597 |
* Each of these fields are initialized to contain an instance of the
|
jaroslav@597
|
598 |
* appropriate view the first time this view is requested. The views are
|
jaroslav@597
|
599 |
* stateless, so there's no reason to create more than one of each.
|
jaroslav@597
|
600 |
*/
|
jaroslav@597
|
601 |
private transient volatile Set<K> keySet = null;
|
jaroslav@597
|
602 |
private transient volatile Set<Map.Entry<K,V>> entrySet = null;
|
jaroslav@597
|
603 |
private transient volatile Collection<V> values = null;
|
jaroslav@597
|
604 |
|
jaroslav@597
|
605 |
/**
|
jaroslav@597
|
606 |
* Returns a {@link Set} view of the keys contained in this map.
|
jaroslav@597
|
607 |
* The set is backed by the map, so changes to the map are
|
jaroslav@597
|
608 |
* reflected in the set, and vice-versa. If the map is modified
|
jaroslav@597
|
609 |
* while an iteration over the set is in progress (except through
|
jaroslav@597
|
610 |
* the iterator's own <tt>remove</tt> operation), the results of
|
jaroslav@597
|
611 |
* the iteration are undefined. The set supports element removal,
|
jaroslav@597
|
612 |
* which removes the corresponding mapping from the map, via the
|
jaroslav@597
|
613 |
* <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
|
jaroslav@597
|
614 |
* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
|
jaroslav@597
|
615 |
* operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
|
jaroslav@597
|
616 |
* operations.
|
jaroslav@597
|
617 |
*
|
jaroslav@597
|
618 |
* @since 1.2
|
jaroslav@597
|
619 |
*/
|
jaroslav@597
|
620 |
public Set<K> keySet() {
|
jaroslav@597
|
621 |
if (keySet == null)
|
jaroslav@597
|
622 |
keySet = Collections.synchronizedSet(new KeySet(), this);
|
jaroslav@597
|
623 |
return keySet;
|
jaroslav@597
|
624 |
}
|
jaroslav@597
|
625 |
|
jaroslav@597
|
626 |
private class KeySet extends AbstractSet<K> {
|
jaroslav@597
|
627 |
public Iterator<K> iterator() {
|
jaroslav@597
|
628 |
return getIterator(KEYS);
|
jaroslav@597
|
629 |
}
|
jaroslav@597
|
630 |
public int size() {
|
jaroslav@597
|
631 |
return count;
|
jaroslav@597
|
632 |
}
|
jaroslav@597
|
633 |
public boolean contains(Object o) {
|
jaroslav@597
|
634 |
return containsKey(o);
|
jaroslav@597
|
635 |
}
|
jaroslav@597
|
636 |
public boolean remove(Object o) {
|
jaroslav@597
|
637 |
return Hashtable.this.remove(o) != null;
|
jaroslav@597
|
638 |
}
|
jaroslav@597
|
639 |
public void clear() {
|
jaroslav@597
|
640 |
Hashtable.this.clear();
|
jaroslav@597
|
641 |
}
|
jaroslav@597
|
642 |
}
|
jaroslav@597
|
643 |
|
jaroslav@597
|
644 |
/**
|
jaroslav@597
|
645 |
* Returns a {@link Set} view of the mappings contained in this map.
|
jaroslav@597
|
646 |
* The set is backed by the map, so changes to the map are
|
jaroslav@597
|
647 |
* reflected in the set, and vice-versa. If the map is modified
|
jaroslav@597
|
648 |
* while an iteration over the set is in progress (except through
|
jaroslav@597
|
649 |
* the iterator's own <tt>remove</tt> operation, or through the
|
jaroslav@597
|
650 |
* <tt>setValue</tt> operation on a map entry returned by the
|
jaroslav@597
|
651 |
* iterator) the results of the iteration are undefined. The set
|
jaroslav@597
|
652 |
* supports element removal, which removes the corresponding
|
jaroslav@597
|
653 |
* mapping from the map, via the <tt>Iterator.remove</tt>,
|
jaroslav@597
|
654 |
* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
|
jaroslav@597
|
655 |
* <tt>clear</tt> operations. It does not support the
|
jaroslav@597
|
656 |
* <tt>add</tt> or <tt>addAll</tt> operations.
|
jaroslav@597
|
657 |
*
|
jaroslav@597
|
658 |
* @since 1.2
|
jaroslav@597
|
659 |
*/
|
jaroslav@597
|
660 |
public Set<Map.Entry<K,V>> entrySet() {
|
jaroslav@597
|
661 |
if (entrySet==null)
|
jaroslav@597
|
662 |
entrySet = Collections.synchronizedSet(new EntrySet(), this);
|
jaroslav@597
|
663 |
return entrySet;
|
jaroslav@597
|
664 |
}
|
jaroslav@597
|
665 |
|
jaroslav@597
|
666 |
private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
|
jaroslav@597
|
667 |
public Iterator<Map.Entry<K,V>> iterator() {
|
jaroslav@597
|
668 |
return getIterator(ENTRIES);
|
jaroslav@597
|
669 |
}
|
jaroslav@597
|
670 |
|
jaroslav@597
|
671 |
public boolean add(Map.Entry<K,V> o) {
|
jaroslav@597
|
672 |
return super.add(o);
|
jaroslav@597
|
673 |
}
|
jaroslav@597
|
674 |
|
jaroslav@597
|
675 |
public boolean contains(Object o) {
|
jaroslav@597
|
676 |
if (!(o instanceof Map.Entry))
|
jaroslav@597
|
677 |
return false;
|
jaroslav@597
|
678 |
Map.Entry entry = (Map.Entry)o;
|
jaroslav@597
|
679 |
Object key = entry.getKey();
|
jaroslav@597
|
680 |
Entry[] tab = table;
|
jaroslav@597
|
681 |
int hash = key.hashCode();
|
jaroslav@597
|
682 |
int index = (hash & 0x7FFFFFFF) % tab.length;
|
jaroslav@597
|
683 |
|
jaroslav@597
|
684 |
for (Entry e = tab[index]; e != null; e = e.next)
|
jaroslav@597
|
685 |
if (e.hash==hash && e.equals(entry))
|
jaroslav@597
|
686 |
return true;
|
jaroslav@597
|
687 |
return false;
|
jaroslav@597
|
688 |
}
|
jaroslav@597
|
689 |
|
jaroslav@597
|
690 |
public boolean remove(Object o) {
|
jaroslav@597
|
691 |
if (!(o instanceof Map.Entry))
|
jaroslav@597
|
692 |
return false;
|
jaroslav@597
|
693 |
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
|
jaroslav@597
|
694 |
K key = entry.getKey();
|
jaroslav@597
|
695 |
Entry[] tab = table;
|
jaroslav@597
|
696 |
int hash = key.hashCode();
|
jaroslav@597
|
697 |
int index = (hash & 0x7FFFFFFF) % tab.length;
|
jaroslav@597
|
698 |
|
jaroslav@597
|
699 |
for (Entry<K,V> e = tab[index], prev = null; e != null;
|
jaroslav@597
|
700 |
prev = e, e = e.next) {
|
jaroslav@597
|
701 |
if (e.hash==hash && e.equals(entry)) {
|
jaroslav@597
|
702 |
modCount++;
|
jaroslav@597
|
703 |
if (prev != null)
|
jaroslav@597
|
704 |
prev.next = e.next;
|
jaroslav@597
|
705 |
else
|
jaroslav@597
|
706 |
tab[index] = e.next;
|
jaroslav@597
|
707 |
|
jaroslav@597
|
708 |
count--;
|
jaroslav@597
|
709 |
e.value = null;
|
jaroslav@597
|
710 |
return true;
|
jaroslav@597
|
711 |
}
|
jaroslav@597
|
712 |
}
|
jaroslav@597
|
713 |
return false;
|
jaroslav@597
|
714 |
}
|
jaroslav@597
|
715 |
|
jaroslav@597
|
716 |
public int size() {
|
jaroslav@597
|
717 |
return count;
|
jaroslav@597
|
718 |
}
|
jaroslav@597
|
719 |
|
jaroslav@597
|
720 |
public void clear() {
|
jaroslav@597
|
721 |
Hashtable.this.clear();
|
jaroslav@597
|
722 |
}
|
jaroslav@597
|
723 |
}
|
jaroslav@597
|
724 |
|
jaroslav@597
|
725 |
/**
|
jaroslav@597
|
726 |
* Returns a {@link Collection} view of the values contained in this map.
|
jaroslav@597
|
727 |
* The collection is backed by the map, so changes to the map are
|
jaroslav@597
|
728 |
* reflected in the collection, and vice-versa. If the map is
|
jaroslav@597
|
729 |
* modified while an iteration over the collection is in progress
|
jaroslav@597
|
730 |
* (except through the iterator's own <tt>remove</tt> operation),
|
jaroslav@597
|
731 |
* the results of the iteration are undefined. The collection
|
jaroslav@597
|
732 |
* supports element removal, which removes the corresponding
|
jaroslav@597
|
733 |
* mapping from the map, via the <tt>Iterator.remove</tt>,
|
jaroslav@597
|
734 |
* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
|
jaroslav@597
|
735 |
* <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
|
jaroslav@597
|
736 |
* support the <tt>add</tt> or <tt>addAll</tt> operations.
|
jaroslav@597
|
737 |
*
|
jaroslav@597
|
738 |
* @since 1.2
|
jaroslav@597
|
739 |
*/
|
jaroslav@597
|
740 |
public Collection<V> values() {
|
jaroslav@597
|
741 |
if (values==null)
|
jaroslav@597
|
742 |
values = Collections.synchronizedCollection(new ValueCollection(),
|
jaroslav@597
|
743 |
this);
|
jaroslav@597
|
744 |
return values;
|
jaroslav@597
|
745 |
}
|
jaroslav@597
|
746 |
|
jaroslav@597
|
747 |
private class ValueCollection extends AbstractCollection<V> {
|
jaroslav@597
|
748 |
public Iterator<V> iterator() {
|
jaroslav@597
|
749 |
return getIterator(VALUES);
|
jaroslav@597
|
750 |
}
|
jaroslav@597
|
751 |
public int size() {
|
jaroslav@597
|
752 |
return count;
|
jaroslav@597
|
753 |
}
|
jaroslav@597
|
754 |
public boolean contains(Object o) {
|
jaroslav@597
|
755 |
return containsValue(o);
|
jaroslav@597
|
756 |
}
|
jaroslav@597
|
757 |
public void clear() {
|
jaroslav@597
|
758 |
Hashtable.this.clear();
|
jaroslav@597
|
759 |
}
|
jaroslav@597
|
760 |
}
|
jaroslav@597
|
761 |
|
jaroslav@597
|
762 |
// Comparison and hashing
|
jaroslav@597
|
763 |
|
jaroslav@597
|
764 |
/**
|
jaroslav@597
|
765 |
* Compares the specified Object with this Map for equality,
|
jaroslav@597
|
766 |
* as per the definition in the Map interface.
|
jaroslav@597
|
767 |
*
|
jaroslav@597
|
768 |
* @param o object to be compared for equality with this hashtable
|
jaroslav@597
|
769 |
* @return true if the specified Object is equal to this Map
|
jaroslav@597
|
770 |
* @see Map#equals(Object)
|
jaroslav@597
|
771 |
* @since 1.2
|
jaroslav@597
|
772 |
*/
|
jaroslav@597
|
773 |
public synchronized boolean equals(Object o) {
|
jaroslav@597
|
774 |
if (o == this)
|
jaroslav@597
|
775 |
return true;
|
jaroslav@597
|
776 |
|
jaroslav@597
|
777 |
if (!(o instanceof Map))
|
jaroslav@597
|
778 |
return false;
|
jaroslav@597
|
779 |
Map<K,V> t = (Map<K,V>) o;
|
jaroslav@597
|
780 |
if (t.size() != size())
|
jaroslav@597
|
781 |
return false;
|
jaroslav@597
|
782 |
|
jaroslav@597
|
783 |
try {
|
jaroslav@597
|
784 |
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
|
jaroslav@597
|
785 |
while (i.hasNext()) {
|
jaroslav@597
|
786 |
Map.Entry<K,V> e = i.next();
|
jaroslav@597
|
787 |
K key = e.getKey();
|
jaroslav@597
|
788 |
V value = e.getValue();
|
jaroslav@597
|
789 |
if (value == null) {
|
jaroslav@597
|
790 |
if (!(t.get(key)==null && t.containsKey(key)))
|
jaroslav@597
|
791 |
return false;
|
jaroslav@597
|
792 |
} else {
|
jaroslav@597
|
793 |
if (!value.equals(t.get(key)))
|
jaroslav@597
|
794 |
return false;
|
jaroslav@597
|
795 |
}
|
jaroslav@597
|
796 |
}
|
jaroslav@597
|
797 |
} catch (ClassCastException unused) {
|
jaroslav@597
|
798 |
return false;
|
jaroslav@597
|
799 |
} catch (NullPointerException unused) {
|
jaroslav@597
|
800 |
return false;
|
jaroslav@597
|
801 |
}
|
jaroslav@597
|
802 |
|
jaroslav@597
|
803 |
return true;
|
jaroslav@597
|
804 |
}
|
jaroslav@597
|
805 |
|
jaroslav@597
|
806 |
/**
|
jaroslav@597
|
807 |
* Returns the hash code value for this Map as per the definition in the
|
jaroslav@597
|
808 |
* Map interface.
|
jaroslav@597
|
809 |
*
|
jaroslav@597
|
810 |
* @see Map#hashCode()
|
jaroslav@597
|
811 |
* @since 1.2
|
jaroslav@597
|
812 |
*/
|
jaroslav@597
|
813 |
public synchronized int hashCode() {
|
jaroslav@597
|
814 |
/*
|
jaroslav@597
|
815 |
* This code detects the recursion caused by computing the hash code
|
jaroslav@597
|
816 |
* of a self-referential hash table and prevents the stack overflow
|
jaroslav@597
|
817 |
* that would otherwise result. This allows certain 1.1-era
|
jaroslav@597
|
818 |
* applets with self-referential hash tables to work. This code
|
jaroslav@597
|
819 |
* abuses the loadFactor field to do double-duty as a hashCode
|
jaroslav@597
|
820 |
* in progress flag, so as not to worsen the space performance.
|
jaroslav@597
|
821 |
* A negative load factor indicates that hash code computation is
|
jaroslav@597
|
822 |
* in progress.
|
jaroslav@597
|
823 |
*/
|
jaroslav@597
|
824 |
int h = 0;
|
jaroslav@597
|
825 |
if (count == 0 || loadFactor < 0)
|
jaroslav@597
|
826 |
return h; // Returns zero
|
jaroslav@597
|
827 |
|
jaroslav@597
|
828 |
loadFactor = -loadFactor; // Mark hashCode computation in progress
|
jaroslav@597
|
829 |
Entry[] tab = table;
|
jaroslav@597
|
830 |
for (int i = 0; i < tab.length; i++)
|
jaroslav@597
|
831 |
for (Entry e = tab[i]; e != null; e = e.next)
|
jaroslav@597
|
832 |
h += e.key.hashCode() ^ e.value.hashCode();
|
jaroslav@597
|
833 |
loadFactor = -loadFactor; // Mark hashCode computation complete
|
jaroslav@597
|
834 |
|
jaroslav@597
|
835 |
return h;
|
jaroslav@597
|
836 |
}
|
jaroslav@597
|
837 |
|
jaroslav@597
|
838 |
/**
|
jaroslav@597
|
839 |
* Hashtable collision list.
|
jaroslav@597
|
840 |
*/
|
jaroslav@597
|
841 |
private static class Entry<K,V> implements Map.Entry<K,V> {
|
jaroslav@597
|
842 |
int hash;
|
jaroslav@597
|
843 |
K key;
|
jaroslav@597
|
844 |
V value;
|
jaroslav@597
|
845 |
Entry<K,V> next;
|
jaroslav@597
|
846 |
|
jaroslav@597
|
847 |
protected Entry(int hash, K key, V value, Entry<K,V> next) {
|
jaroslav@597
|
848 |
this.hash = hash;
|
jaroslav@597
|
849 |
this.key = key;
|
jaroslav@597
|
850 |
this.value = value;
|
jaroslav@597
|
851 |
this.next = next;
|
jaroslav@597
|
852 |
}
|
jaroslav@597
|
853 |
|
jaroslav@597
|
854 |
protected Object clone() {
|
jaroslav@597
|
855 |
return new Entry<>(hash, key, value,
|
jaroslav@597
|
856 |
(next==null ? null : (Entry<K,V>) next.clone()));
|
jaroslav@597
|
857 |
}
|
jaroslav@597
|
858 |
|
jaroslav@597
|
859 |
// Map.Entry Ops
|
jaroslav@597
|
860 |
|
jaroslav@597
|
861 |
public K getKey() {
|
jaroslav@597
|
862 |
return key;
|
jaroslav@597
|
863 |
}
|
jaroslav@597
|
864 |
|
jaroslav@597
|
865 |
public V getValue() {
|
jaroslav@597
|
866 |
return value;
|
jaroslav@597
|
867 |
}
|
jaroslav@597
|
868 |
|
jaroslav@597
|
869 |
public V setValue(V value) {
|
jaroslav@597
|
870 |
if (value == null)
|
jaroslav@597
|
871 |
throw new NullPointerException();
|
jaroslav@597
|
872 |
|
jaroslav@597
|
873 |
V oldValue = this.value;
|
jaroslav@597
|
874 |
this.value = value;
|
jaroslav@597
|
875 |
return oldValue;
|
jaroslav@597
|
876 |
}
|
jaroslav@597
|
877 |
|
jaroslav@597
|
878 |
public boolean equals(Object o) {
|
jaroslav@597
|
879 |
if (!(o instanceof Map.Entry))
|
jaroslav@597
|
880 |
return false;
|
jaroslav@597
|
881 |
Map.Entry e = (Map.Entry)o;
|
jaroslav@597
|
882 |
|
jaroslav@597
|
883 |
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
|
jaroslav@597
|
884 |
(value==null ? e.getValue()==null : value.equals(e.getValue()));
|
jaroslav@597
|
885 |
}
|
jaroslav@597
|
886 |
|
jaroslav@597
|
887 |
public int hashCode() {
|
jaroslav@597
|
888 |
return hash ^ (value==null ? 0 : value.hashCode());
|
jaroslav@597
|
889 |
}
|
jaroslav@597
|
890 |
|
jaroslav@597
|
891 |
public String toString() {
|
jaroslav@597
|
892 |
return key.toString()+"="+value.toString();
|
jaroslav@597
|
893 |
}
|
jaroslav@597
|
894 |
}
|
jaroslav@597
|
895 |
|
jaroslav@597
|
896 |
// Types of Enumerations/Iterations
|
jaroslav@597
|
897 |
private static final int KEYS = 0;
|
jaroslav@597
|
898 |
private static final int VALUES = 1;
|
jaroslav@597
|
899 |
private static final int ENTRIES = 2;
|
jaroslav@597
|
900 |
|
jaroslav@597
|
901 |
/**
|
jaroslav@597
|
902 |
* A hashtable enumerator class. This class implements both the
|
jaroslav@597
|
903 |
* Enumeration and Iterator interfaces, but individual instances
|
jaroslav@597
|
904 |
* can be created with the Iterator methods disabled. This is necessary
|
jaroslav@597
|
905 |
* to avoid unintentionally increasing the capabilities granted a user
|
jaroslav@597
|
906 |
* by passing an Enumeration.
|
jaroslav@597
|
907 |
*/
|
jaroslav@597
|
908 |
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
|
jaroslav@597
|
909 |
Entry[] table = Hashtable.this.table;
|
jaroslav@597
|
910 |
int index = table.length;
|
jaroslav@597
|
911 |
Entry<K,V> entry = null;
|
jaroslav@597
|
912 |
Entry<K,V> lastReturned = null;
|
jaroslav@597
|
913 |
int type;
|
jaroslav@597
|
914 |
|
jaroslav@597
|
915 |
/**
|
jaroslav@597
|
916 |
* Indicates whether this Enumerator is serving as an Iterator
|
jaroslav@597
|
917 |
* or an Enumeration. (true -> Iterator).
|
jaroslav@597
|
918 |
*/
|
jaroslav@597
|
919 |
boolean iterator;
|
jaroslav@597
|
920 |
|
jaroslav@597
|
921 |
/**
|
jaroslav@597
|
922 |
* The modCount value that the iterator believes that the backing
|
jaroslav@597
|
923 |
* Hashtable should have. If this expectation is violated, the iterator
|
jaroslav@597
|
924 |
* has detected concurrent modification.
|
jaroslav@597
|
925 |
*/
|
jaroslav@597
|
926 |
protected int expectedModCount = modCount;
|
jaroslav@597
|
927 |
|
jaroslav@597
|
928 |
Enumerator(int type, boolean iterator) {
|
jaroslav@597
|
929 |
this.type = type;
|
jaroslav@597
|
930 |
this.iterator = iterator;
|
jaroslav@597
|
931 |
}
|
jaroslav@597
|
932 |
|
jaroslav@597
|
933 |
public boolean hasMoreElements() {
|
jaroslav@597
|
934 |
Entry<K,V> e = entry;
|
jaroslav@597
|
935 |
int i = index;
|
jaroslav@597
|
936 |
Entry[] t = table;
|
jaroslav@597
|
937 |
/* Use locals for faster loop iteration */
|
jaroslav@597
|
938 |
while (e == null && i > 0) {
|
jaroslav@597
|
939 |
e = t[--i];
|
jaroslav@597
|
940 |
}
|
jaroslav@597
|
941 |
entry = e;
|
jaroslav@597
|
942 |
index = i;
|
jaroslav@597
|
943 |
return e != null;
|
jaroslav@597
|
944 |
}
|
jaroslav@597
|
945 |
|
jaroslav@597
|
946 |
public T nextElement() {
|
jaroslav@597
|
947 |
Entry<K,V> et = entry;
|
jaroslav@597
|
948 |
int i = index;
|
jaroslav@597
|
949 |
Entry[] t = table;
|
jaroslav@597
|
950 |
/* Use locals for faster loop iteration */
|
jaroslav@597
|
951 |
while (et == null && i > 0) {
|
jaroslav@597
|
952 |
et = t[--i];
|
jaroslav@597
|
953 |
}
|
jaroslav@597
|
954 |
entry = et;
|
jaroslav@597
|
955 |
index = i;
|
jaroslav@597
|
956 |
if (et != null) {
|
jaroslav@597
|
957 |
Entry<K,V> e = lastReturned = entry;
|
jaroslav@597
|
958 |
entry = e.next;
|
jaroslav@597
|
959 |
return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
|
jaroslav@597
|
960 |
}
|
jaroslav@597
|
961 |
throw new NoSuchElementException("Hashtable Enumerator");
|
jaroslav@597
|
962 |
}
|
jaroslav@597
|
963 |
|
jaroslav@597
|
964 |
// Iterator methods
|
jaroslav@597
|
965 |
public boolean hasNext() {
|
jaroslav@597
|
966 |
return hasMoreElements();
|
jaroslav@597
|
967 |
}
|
jaroslav@597
|
968 |
|
jaroslav@597
|
969 |
public T next() {
|
jaroslav@597
|
970 |
if (modCount != expectedModCount)
|
jaroslav@597
|
971 |
throw new ConcurrentModificationException();
|
jaroslav@597
|
972 |
return nextElement();
|
jaroslav@597
|
973 |
}
|
jaroslav@597
|
974 |
|
jaroslav@597
|
975 |
public void remove() {
|
jaroslav@597
|
976 |
if (!iterator)
|
jaroslav@597
|
977 |
throw new UnsupportedOperationException();
|
jaroslav@597
|
978 |
if (lastReturned == null)
|
jaroslav@597
|
979 |
throw new IllegalStateException("Hashtable Enumerator");
|
jaroslav@597
|
980 |
if (modCount != expectedModCount)
|
jaroslav@597
|
981 |
throw new ConcurrentModificationException();
|
jaroslav@597
|
982 |
|
jaroslav@597
|
983 |
synchronized(Hashtable.this) {
|
jaroslav@597
|
984 |
Entry[] tab = Hashtable.this.table;
|
jaroslav@597
|
985 |
int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
|
jaroslav@597
|
986 |
|
jaroslav@597
|
987 |
for (Entry<K,V> e = tab[index], prev = null; e != null;
|
jaroslav@597
|
988 |
prev = e, e = e.next) {
|
jaroslav@597
|
989 |
if (e == lastReturned) {
|
jaroslav@597
|
990 |
modCount++;
|
jaroslav@597
|
991 |
expectedModCount++;
|
jaroslav@597
|
992 |
if (prev == null)
|
jaroslav@597
|
993 |
tab[index] = e.next;
|
jaroslav@597
|
994 |
else
|
jaroslav@597
|
995 |
prev.next = e.next;
|
jaroslav@597
|
996 |
count--;
|
jaroslav@597
|
997 |
lastReturned = null;
|
jaroslav@597
|
998 |
return;
|
jaroslav@597
|
999 |
}
|
jaroslav@597
|
1000 |
}
|
jaroslav@597
|
1001 |
throw new ConcurrentModificationException();
|
jaroslav@597
|
1002 |
}
|
jaroslav@597
|
1003 |
}
|
jaroslav@597
|
1004 |
}
|
jaroslav@597
|
1005 |
}
|