|
1
50 package org.apache.avalon.excalibur.collections;
51
52 import java.util.Collection  ;
53 import java.util.HashSet ;
54 import java.util.Iterator ;
55 import java.util.Map ;
56 import java.util.Set ;
57
58
72 public final class BucketMap implements Map
73 {
74 private static final int DEFAULT_BUCKETS = 256;
75 private final Node[] m_buckets;
76 private volatile int m_size = 0;
77
78
81 public BucketMap()
82 {
83 this( DEFAULT_BUCKETS );
84 }
85
86
94 public BucketMap( int numBuckets )
95 {
96 int size = Math.max( 17, numBuckets );
97
98 m_buckets = new Node[ size ];
99
100 for( int i = 0; i < size; i++ )
101 {
102 m_buckets[ i ] = new Node();
103 }
104 }
105
106
119 private final int getHash( Object key )
120 {
121 int hash = key.hashCode();
122
123 hash += ~(hash << 9);
124 hash ^= (hash >>> 14);
125 hash += (hash << 4);
126 hash ^= (hash >>> 10);
127
128 hash %= m_buckets.length;
129
130 return ( hash < 0 ) ? hash * -1 : hash;
131 }
132
133
138 public Set keySet()
139 {
140 Set keySet = new HashSet ();
141
142 for( int i = 0; i < m_buckets.length; i++ )
143 {
144 synchronized( m_buckets[ i ] )
145 {
146 Node n = m_buckets[ i ];
147
148 while( n != null && n.key != null )
149 {
150 keySet.add( n.key );
151 n = n.next;
152 }
153 }
154 }
155
156 return keySet;
157 }
158
159
162 public int size()
163 {
164 return m_size;
165 }
166
167
170 public Object put( final Object key, final Object value )
171 {
172 if( null == key || null == value )
173 {
174 return null;
175 }
176
177 int hash = getHash( key );
178
179 synchronized( m_buckets[ hash ] )
180 {
181 Node n = m_buckets[ hash ];
182
183 if( n.key == null )
184 {
185 n.key = key;
186 n.value = value;
187 m_size++;
188 return value;
189 }
190
191 for( Node next = n; next != null; next = next.next )
195 {
196 n = next;
197
198 if( ( n.key == key ) || ( n.key.equals( key ) ) )
199 {
200 Object returnVal = n.value;
202 n.value = value;
203 return returnVal;
204 }
205 }
206
207 Node newNode = new Node();
210 newNode.key = key;
211 newNode.value = value;
212 n.next = newNode;
213 m_size++;
214 }
215
216 return null;
217 }
218
219
222 public Object get( final Object key )
223 {
224 if( null == key )
225 {
226 return null;
227 }
228
229 int hash = getHash( key );
230
231 synchronized( m_buckets[ hash ] )
232 {
233 Node n = m_buckets[ hash ];
234
235 while( n != null && n.key != null )
236 {
237 if( ( n.key == key ) || ( n.key.equals( key ) ) )
238 {
239 return n.value;
240 }
241
242 n = n.next;
243 }
244 }
245
246 return null;
247 }
248
249
252 public boolean containsKey( final Object key )
253 {
254 if( null == key )
255 {
256 return false;
257 }
258
259 int hash = getHash( key );
260
261 synchronized( m_buckets[ hash ] )
262 {
263 Node n = m_buckets[ hash ];
264
265 while( n != null && n.key != null )
266 {
267 if( ( n.key == key ) || ( n.key.equals( key ) ) )
268 {
269 return true;
270 }
271
272 n = n.next;
273 }
274 }
275
276 return false;
277 }
278
279
284 public boolean containsValue( final Object value )
285 {
286 if( null == value )
287 {
288 return false;
289 }
290
291 for( int i = 0; i < m_buckets.length; i++ )
292 {
293 synchronized( m_buckets[ i ] )
294 {
295 Node n = m_buckets[ i ];
296
297 while( n != null && n.key != null )
298 {
299 if( ( n.value == value ) || ( n.value.equals( value ) ) )
300 {
301 return true;
302 }
303
304 n = n.next;
305 }
306 }
307 }
308
309 return false;
310 }
311
312
317 public Collection values()
318 {
319 Set valueSet = new HashSet ();
320
321 for( int i = 0; i < m_buckets.length; i++ )
322 {
323 synchronized( m_buckets[ i ] )
324 {
325 Node n = m_buckets[ i ];
326
327 while( n != null && n.key != null )
328 {
329 valueSet.add( n.value );
330 n = n.next;
331 }
332 }
333 }
334
335 return valueSet;
336 }
337
338
343 public Set entrySet()
344 {
345 Set entrySet = new HashSet ();
346
347 for( int i = 0; i < m_buckets.length; i++ )
348 {
349 synchronized( m_buckets[ i ] )
350 {
351 Node n = m_buckets[ i ];
352
353 while( n != null && n.key != null )
354 {
355 entrySet.add( n );
356 n = n.next;
357 }
358 }
359 }
360
361 return entrySet;
362 }
363
364
367 public void putAll( Map other )
368 {
369 Iterator i = other.keySet().iterator();
370
371 while( i.hasNext() )
372 {
373 Object key = i.next();
374 put( key, other.get( key ) );
375 }
376 }
377
378
381 public Object remove( Object key )
382 {
383 if( null == key )
384 {
385 return null;
386 }
387
388 int hash = getHash( key );
389
390 synchronized( m_buckets[ hash ] )
391 {
392 Node n = m_buckets[ hash ];
393 Node prev = null;
394
395 while( n != null && n.key != null )
396 {
397 if( ( n.key == key ) || ( n.key.equals( key ) ) )
398 {
399 if( null == prev )
401 {
402 m_buckets[ hash ] = ( n.next == null ? new Node() : n.next );
404 }
405 else
406 {
407 prev.next = n.next;
409 }
410
411 m_size--;
412 return n.value;
413 }
414
415 prev = n;
416 n = n.next;
417 }
418 }
419
420 return null;
421 }
422
423
426 public final boolean isEmpty()
427 {
428 return m_size == 0;
429 }
430
431
434 public final void clear()
435 {
436 for( int i = 0; i < m_buckets.length; i++ )
437 {
438 m_buckets[ i ] = null; m_buckets[ i ] = new Node();
440 }
441 }
442
443
446 private final class Node implements Map.Entry
447 {
448 protected Object key;
449 protected Object value;
450 protected Node next;
451
452 public Object getKey()
453 {
454 return key;
455 }
456
457 public Object getValue()
458 {
459 return value;
460 }
461
462 public int hashCode()
463 {
464 return getHash( key );
465 }
466
467 public Object setValue( Object val )
468 {
469 Object retVal = value;
470 value = val;
471 return retVal;
472 }
473 }
474 }
475 |
Popular Tags |
Java API By Example, From Geeks To Geeks.