Source Code Cross Referenced for HashMap.java in  » 6.0-JDK-Modules » j2me » java » util » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » 6.0 JDK Modules » j2me » java.util 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


0001:        /*
0002:         * @(#)HashMap.java	1.45 06/10/10
0003:         *
0004:         * Copyright  1990-2006 Sun Microsystems, Inc. All Rights Reserved.  
0005:         * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER  
0006:         *   
0007:         * This program is free software; you can redistribute it and/or  
0008:         * modify it under the terms of the GNU General Public License version  
0009:         * 2 only, as published by the Free Software Foundation.   
0010:         *   
0011:         * This program is distributed in the hope that it will be useful, but  
0012:         * WITHOUT ANY WARRANTY; without even the implied warranty of  
0013:         * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU  
0014:         * General Public License version 2 for more details (a copy is  
0015:         * included at /legal/license.txt).   
0016:         *   
0017:         * You should have received a copy of the GNU General Public License  
0018:         * version 2 along with this work; if not, write to the Free Software  
0019:         * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  
0020:         * 02110-1301 USA   
0021:         *   
0022:         * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa  
0023:         * Clara, CA 95054 or visit www.sun.com if you need additional  
0024:         * information or have any questions. 
0025:         *
0026:         */
0027:
0028:        package java.util;
0029:
0030:        import java.io.*;
0031:
0032:        /**
0033:         * Hash table based implementation of the <tt>Map</tt> interface.  This
0034:         * implementation provides all of the optional map operations, and permits
0035:         * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
0036:         * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
0037:         * unsynchronized and permits nulls.)  This class makes no guarantees as to
0038:         * the order of the map; in particular, it does not guarantee that the order
0039:         * will remain constant over time.
0040:         *
0041:         * <p>This implementation provides constant-time performance for the basic
0042:         * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
0043:         * disperses the elements properly among the buckets.  Iteration over
0044:         * collection views requires time proportional to the "capacity" of the
0045:         * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
0046:         * of key-value mappings).  Thus, it's very important not to set the initial
0047:         * capacity too high (or the load factor too low) if iteration performance is
0048:         * important.
0049:         *
0050:         * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
0051:         * performance: <i>initial capacity</i> and <i>load factor</i>.  The
0052:         * <i>capacity</i> is the number of buckets in the hash table, and the initial
0053:         * capacity is simply the capacity at the time the hash table is created.  The
0054:         * <i>load factor</i> is a measure of how full the hash table is allowed to
0055:         * get before its capacity is automatically increased.  When the number of
0056:         * entries in the hash table exceeds the product of the load factor and the
0057:         * current capacity, the capacity is roughly doubled by calling the
0058:         * <tt>rehash</tt> method.
0059:         *
0060:         * <p>As a general rule, the default load factor (.75) offers a good tradeoff
0061:         * between time and space costs.  Higher values decrease the space overhead
0062:         * but increase the lookup cost (reflected in most of the operations of the
0063:         * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>).  The
0064:         * expected number of entries in the map and its load factor should be taken
0065:         * into account when setting its initial capacity, so as to minimize the
0066:         * number of <tt>rehash</tt> operations.  If the initial capacity is greater
0067:         * than the maximum number of entries divided by the load factor, no
0068:         * <tt>rehash</tt> operations will ever occur.
0069:         *
0070:         * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
0071:         * creating it with a sufficiently large capacity will allow the mappings to
0072:         * be stored more efficiently than letting it perform automatic rehashing as
0073:         * needed to grow the table.
0074:         *
0075:         * <p><b>Note that this implementation is not synchronized.</b> If multiple
0076:         * threads access this map concurrently, and at least one of the threads
0077:         * modifies the map structurally, it <i>must</i> be synchronized externally.
0078:         * (A structural modification is any operation that adds or deletes one or
0079:         * more mappings; merely changing the value associated with a key that an
0080:         * instance already contains is not a structural modification.)  This is
0081:         * typically accomplished by synchronizing on some object that naturally
0082:         * encapsulates the map.  If no such object exists, the map should be
0083:         * "wrapped" using the <tt>Collections.synchronizedMap</tt> method.  This is
0084:         * best done at creation time, to prevent accidental unsynchronized access to
0085:         * the map: <pre> Map m = Collections.synchronizedMap(new HashMap(...));
0086:         * </pre>
0087:         *
0088:         * <p>The iterators returned by all of this class's "collection view methods"
0089:         * are <i>fail-fast</i>: if the map is structurally modified at any time after
0090:         * the iterator is created, in any way except through the iterator's own
0091:         * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
0092:         * <tt>ConcurrentModificationException</tt>.  Thus, in the face of concurrent
0093:         * modification, the iterator fails quickly and cleanly, rather than risking
0094:         * arbitrary, non-deterministic behavior at an undetermined time in the
0095:         * future.
0096:         *
0097:         * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
0098:         * as it is, generally speaking, impossible to make any hard guarantees in the
0099:         * presence of unsynchronized concurrent modification.  Fail-fast iterators
0100:         * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 
0101:         * Therefore, it would be wrong to write a program that depended on this
0102:         * exception for its correctness: <i>the fail-fast behavior of iterators
0103:         * should be used only to detect bugs.</i>
0104:         *
0105:         * <p>This class is a member of the 
0106:         * <a href="{@docRoot}/../guide/collections/index.html">
0107:         * Java Collections Framework</a>.
0108:         *
0109:         * @author  Doug Lea
0110:         * @author  Josh Bloch
0111:         * @author  Arthur van Hoff
0112:         * @version 1.38, 02/02/00
0113:         * @see     Object#hashCode()
0114:         * @see     Collection
0115:         * @see	    Map
0116:         * @see	    TreeMap
0117:         * @see	    Hashtable
0118:         * @since   1.2
0119:         */
0120:
0121:        public class HashMap extends AbstractMap implements  Map, Cloneable,
0122:                Serializable {
0123:            /**
0124:             * The default initial capacity - MUST be a power of two.
0125:             */
0126:            static final int DEFAULT_INITIAL_CAPACITY = 16;
0127:
0128:            /**
0129:             * The maximum capacity, used if a higher value is implicitly specified
0130:             * by either of the constructors with arguments.
0131:             * MUST be a power of two <= 1<<30.
0132:             */
0133:            static final int MAXIMUM_CAPACITY = 1 << 30;
0134:
0135:            /**
0136:             * The load factor used when none specified in constructor.
0137:             **/
0138:            static final float DEFAULT_LOAD_FACTOR = 0.75f;
0139:
0140:            /**
0141:             * The table, resized as necessary. Length MUST Always be a power of two.
0142:             */
0143:            transient Entry[] table;
0144:
0145:            /**
0146:             * The number of key-value mappings contained in this identity hash map.
0147:             */
0148:            transient int size;
0149:
0150:            /**
0151:             * The next size value at which to resize (capacity * load factor).
0152:             * @serial
0153:             */
0154:            int threshold;
0155:
0156:            /**
0157:             * The load factor for the hash table.
0158:             *
0159:             * @serial
0160:             */
0161:            final float loadFactor;
0162:
0163:            /**
0164:             * The number of times this HashMap has been structurally modified
0165:             * Structural modifications are those that change the number of mappings in
0166:             * the HashMap or otherwise modify its internal structure (e.g.,
0167:             * rehash).  This field is used to make iterators on Collection-views of
0168:             * the HashMap fail-fast.  (See ConcurrentModificationException).
0169:             */
0170:            transient volatile int modCount;
0171:
0172:            /**
0173:             * Constructs an empty <tt>HashMap</tt> with the specified initial
0174:             * capacity and load factor.
0175:             *
0176:             * @param  initialCapacity The initial capacity.
0177:             * @param  loadFactor      The load factor.
0178:             * @throws IllegalArgumentException if the initial capacity is negative
0179:             *         or the load factor is nonpositive.
0180:             */
0181:            public HashMap(int initialCapacity, float loadFactor) {
0182:                if (initialCapacity < 0)
0183:                    throw new IllegalArgumentException(
0184:                            "Illegal initial capacity: " + initialCapacity);
0185:                if (initialCapacity > MAXIMUM_CAPACITY)
0186:                    initialCapacity = MAXIMUM_CAPACITY;
0187:                if (loadFactor <= 0 || Float.isNaN(loadFactor))
0188:                    throw new IllegalArgumentException("Illegal load factor: "
0189:                            + loadFactor);
0190:
0191:                // Find a power of 2 >= initialCapacity
0192:                int capacity = 1;
0193:                while (capacity < initialCapacity)
0194:                    capacity <<= 1;
0195:
0196:                this .loadFactor = loadFactor;
0197:                threshold = (int) (capacity * loadFactor);
0198:                table = new Entry[capacity];
0199:                init();
0200:            }
0201:
0202:            /**
0203:             * Constructs an empty <tt>HashMap</tt> with the specified initial
0204:             * capacity and the default load factor (0.75).
0205:             *
0206:             * @param  initialCapacity the initial capacity.
0207:             * @throws IllegalArgumentException if the initial capacity is negative.
0208:             */
0209:            public HashMap(int initialCapacity) {
0210:                this (initialCapacity, DEFAULT_LOAD_FACTOR);
0211:            }
0212:
0213:            /**
0214:             * Constructs an empty <tt>HashMap</tt> with the default initial capacity
0215:             * (16) and the default load factor (0.75).
0216:             */
0217:            public HashMap() {
0218:                this .loadFactor = DEFAULT_LOAD_FACTOR;
0219:                threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
0220:                table = new Entry[DEFAULT_INITIAL_CAPACITY];
0221:                init();
0222:            }
0223:
0224:            /**
0225:             * Constructs a new <tt>HashMap</tt> with the same mappings as the
0226:             * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
0227:             * default load factor (0.75) and an initial capacity sufficient to
0228:             * hold the mappings in the specified <tt>Map</tt>.
0229:             *
0230:             * @param   m the map whose mappings are to be placed in this map.
0231:             * @throws  NullPointerException if the specified map is null.
0232:             */
0233:            public HashMap(Map m) {
0234:                this (Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
0235:                        DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
0236:                putAllForCreate(m);
0237:            }
0238:
0239:            // internal utilities
0240:
0241:            /**
0242:             * Initialization hook for subclasses. This method is called
0243:             * in all constructors and pseudo-constructors (clone, readObject)
0244:             * after HashMap has been initialized but before any entries have
0245:             * been inserted.  (In the absence of this method, readObject would
0246:             * require explicit knowledge of subclasses.)
0247:             */
0248:            void init() {
0249:            }
0250:
0251:            /**
0252:             * Value representing null keys inside tables.
0253:             */
0254:            static final Object NULL_KEY = new Object();
0255:
0256:            /**
0257:             * Returns internal representation for key. Use NULL_KEY if key is null.
0258:             */
0259:            static Object maskNull(Object key) {
0260:                return (key == null ? NULL_KEY : key);
0261:            }
0262:
0263:            /**
0264:             * Returns key represented by specified internal representation.
0265:             */
0266:            static Object unmaskNull(Object key) {
0267:                return (key == NULL_KEY ? null : key);
0268:            }
0269:
0270:            /**
0271:             * Returns a hash value for the specified object.  In addition to 
0272:             * the object's own hashCode, this method applies a "supplemental
0273:             * hash function," which defends against poor quality hash functions.
0274:             * This is critical because HashMap uses power-of two length 
0275:             * hash tables.<p>
0276:             *
0277:             * The shift distances in this function were chosen as the result
0278:             * of an automated search over the entire four-dimensional search space.
0279:             */
0280:            static int hash(Object x) {
0281:                int h = x.hashCode();
0282:
0283:                h += ~(h << 9);
0284:                h ^= (h >>> 14);
0285:                h += (h << 4);
0286:                h ^= (h >>> 10);
0287:                return h;
0288:            }
0289:
0290:            /** 
0291:             * Check for equality of non-null reference x and possibly-null y. 
0292:             */
0293:            static boolean eq(Object x, Object y) {
0294:                return x == y || x.equals(y);
0295:            }
0296:
0297:            /**
0298:             * Returns index for hash code h. 
0299:             */
0300:            static int indexFor(int h, int length) {
0301:                return h & (length - 1);
0302:            }
0303:
0304:            /**
0305:             * Returns the number of key-value mappings in this map.
0306:             *
0307:             * @return the number of key-value mappings in this map.
0308:             */
0309:            public int size() {
0310:                return size;
0311:            }
0312:
0313:            /**
0314:             * Returns <tt>true</tt> if this map contains no key-value mappings.
0315:             *
0316:             * @return <tt>true</tt> if this map contains no key-value mappings.
0317:             */
0318:            public boolean isEmpty() {
0319:                return size == 0;
0320:            }
0321:
0322:            /**
0323:             * Returns the value to which the specified key is mapped in this identity
0324:             * hash map, or <tt>null</tt> if the map contains no mapping for this key.
0325:             * A return value of <tt>null</tt> does not <i>necessarily</i> indicate
0326:             * that the map contains no mapping for the key; it is also possible that
0327:             * the map explicitly maps the key to <tt>null</tt>. The
0328:             * <tt>containsKey</tt> method may be used to distinguish these two cases.
0329:             *
0330:             * @param   key the key whose associated value is to be returned.
0331:             * @return  the value to which this map maps the specified key, or
0332:             *          <tt>null</tt> if the map contains no mapping for this key.
0333:             * @see #put(Object, Object)
0334:             */
0335:            public Object get(Object key) {
0336:                Object k = maskNull(key);
0337:                int hash = hash(k);
0338:                int i = indexFor(hash, table.length);
0339:                Entry e = table[i];
0340:                while (true) {
0341:                    if (e == null)
0342:                        return e;
0343:                    if (e.hash == hash && eq(k, e.key))
0344:                        return e.value;
0345:                    e = e.next;
0346:                }
0347:            }
0348:
0349:            /**
0350:             * Returns <tt>true</tt> if this map contains a mapping for the
0351:             * specified key.
0352:             *
0353:             * @param   key   The key whose presence in this map is to be tested
0354:             * @return <tt>true</tt> if this map contains a mapping for the specified
0355:             * key.
0356:             */
0357:            public boolean containsKey(Object key) {
0358:                Object k = maskNull(key);
0359:                int hash = hash(k);
0360:                int i = indexFor(hash, table.length);
0361:                Entry e = table[i];
0362:                while (e != null) {
0363:                    if (e.hash == hash && eq(k, e.key))
0364:                        return true;
0365:                    e = e.next;
0366:                }
0367:                return false;
0368:            }
0369:
0370:            /**
0371:             * Returns the entry associated with the specified key in the
0372:             * HashMap.  Returns null if the HashMap contains no mapping
0373:             * for this key.
0374:             */
0375:            Entry getEntry(Object key) {
0376:                Object k = maskNull(key);
0377:                int hash = hash(k);
0378:                int i = indexFor(hash, table.length);
0379:                Entry e = table[i];
0380:                while (e != null && !(e.hash == hash && eq(k, e.key)))
0381:                    e = e.next;
0382:                return e;
0383:            }
0384:
0385:            /**
0386:             * Associates the specified value with the specified key in this map.
0387:             * If the map previously contained a mapping for this key, the old
0388:             * value is replaced.
0389:             *
0390:             * @param key key with which the specified value is to be associated.
0391:             * @param value value to be associated with the specified key.
0392:             * @return previous value associated with specified key, or <tt>null</tt>
0393:             *	       if there was no mapping for key.  A <tt>null</tt> return can
0394:             *	       also indicate that the HashMap previously associated
0395:             *	       <tt>null</tt> with the specified key.
0396:             */
0397:            public Object put(Object key, Object value) {
0398:                Object k = maskNull(key);
0399:                int hash = hash(k);
0400:                int i = indexFor(hash, table.length);
0401:
0402:                for (Entry e = table[i]; e != null; e = e.next) {
0403:                    if (e.hash == hash && eq(k, e.key)) {
0404:                        Object oldValue = e.value;
0405:                        e.value = value;
0406:                        e.recordAccess(this );
0407:                        return oldValue;
0408:                    }
0409:                }
0410:
0411:                modCount++;
0412:                addEntry(hash, k, value, i);
0413:                return null;
0414:            }
0415:
0416:            /**
0417:             * This method is used instead of put by constructors and
0418:             * pseudoconstructors (clone, readObject).  It does not resize the table,
0419:             * check for comodification, etc.  It calls createEntry rather than
0420:             * addEntry.
0421:             */
0422:            private void putForCreate(Object key, Object value) {
0423:                Object k = maskNull(key);
0424:                int hash = hash(k);
0425:                int i = indexFor(hash, table.length);
0426:
0427:                /**
0428:                 * Look for preexisting entry for key.  This will never happen for
0429:                 * clone or deserialize.  It will only happen for construction if the
0430:                 * input Map is a sorted map whose ordering is inconsistent w/ equals.
0431:                 */
0432:                for (Entry e = table[i]; e != null; e = e.next) {
0433:                    if (e.hash == hash && eq(k, e.key)) {
0434:                        e.value = value;
0435:                        return;
0436:                    }
0437:                }
0438:
0439:                createEntry(hash, k, value, i);
0440:            }
0441:
0442:            void putAllForCreate(Map m) {
0443:                for (Iterator i = m.entrySet().iterator(); i.hasNext();) {
0444:                    Map.Entry e = (Map.Entry) i.next();
0445:                    putForCreate(e.getKey(), e.getValue());
0446:                }
0447:            }
0448:
0449:            /**
0450:             * Rehashes the contents of this map into a new array with a
0451:             * larger capacity.  This method is called automatically when the
0452:             * number of keys in this map reaches its threshold.
0453:             *
0454:             * If current capacity is MAXIMUM_CAPACITY, this method does not
0455:             * resize the map, but but sets threshold to Integer.MAX_VALUE.
0456:             * This has the effect of preventing future calls.
0457:             *
0458:             * @param newCapacity the new capacity, MUST be a power of two;
0459:             *        must be greater than current capacity unless current
0460:             *        capacity is MAXIMUM_CAPACITY (in which case value
0461:             *        is irrelevant).
0462:             */
0463:            void resize(int newCapacity) {
0464:                Entry[] oldTable = table;
0465:                int oldCapacity = oldTable.length;
0466:                if (oldCapacity == MAXIMUM_CAPACITY) {
0467:                    threshold = Integer.MAX_VALUE;
0468:                    return;
0469:                }
0470:
0471:                Entry[] newTable = new Entry[newCapacity];
0472:                transfer(newTable);
0473:                table = newTable;
0474:                threshold = (int) (newCapacity * loadFactor);
0475:            }
0476:
0477:            /** 
0478:             * Transfer all entries from current table to newTable.
0479:             */
0480:            void transfer(Entry[] newTable) {
0481:                Entry[] src = table;
0482:                int newCapacity = newTable.length;
0483:                for (int j = 0; j < src.length; j++) {
0484:                    Entry e = src[j];
0485:                    if (e != null) {
0486:                        src[j] = null;
0487:                        do {
0488:                            Entry next = e.next;
0489:                            int i = indexFor(e.hash, newCapacity);
0490:                            e.next = newTable[i];
0491:                            newTable[i] = e;
0492:                            e = next;
0493:                        } while (e != null);
0494:                    }
0495:                }
0496:            }
0497:
0498:            /**
0499:             * Copies all of the mappings from the specified map to this map
0500:             * These mappings will replace any mappings that
0501:             * this map had for any of the keys currently in the specified map.
0502:             *
0503:             * @param m mappings to be stored in this map.
0504:             * @throws NullPointerException if the specified map is null.
0505:             */
0506:            public void putAll(Map m) {
0507:                int numKeysToBeAdded = m.size();
0508:                if (numKeysToBeAdded == 0)
0509:                    return;
0510:
0511:                /*
0512:                 * Expand the map if the map if the number of mappings to be added
0513:                 * is greater than or equal to threshold.  This is conservative; the
0514:                 * obvious condition is (m.size() + size) >= threshold, but this
0515:                 * condition could result in a map with twice the appropriate capacity,
0516:                 * if the keys to be added overlap with the keys already in this map.
0517:                 * By using the conservative calculation, we subject ourself
0518:                 * to at most one extra resize.
0519:                 */
0520:                if (numKeysToBeAdded > threshold) {
0521:                    int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
0522:                    if (targetCapacity > MAXIMUM_CAPACITY)
0523:                        targetCapacity = MAXIMUM_CAPACITY;
0524:                    int newCapacity = table.length;
0525:                    while (newCapacity < targetCapacity)
0526:                        newCapacity <<= 1;
0527:                    if (newCapacity > table.length)
0528:                        resize(newCapacity);
0529:                }
0530:
0531:                for (Iterator i = m.entrySet().iterator(); i.hasNext();) {
0532:                    Map.Entry e = (Map.Entry) i.next();
0533:                    put(e.getKey(), e.getValue());
0534:                }
0535:            }
0536:
0537:            /**
0538:             * Removes the mapping for this key from this map if present.
0539:             *
0540:             * @param  key key whose mapping is to be removed from the map.
0541:             * @return previous value associated with specified key, or <tt>null</tt>
0542:             *	       if there was no mapping for key.  A <tt>null</tt> return can
0543:             *	       also indicate that the map previously associated <tt>null</tt>
0544:             *	       with the specified key.
0545:             */
0546:            public Object remove(Object key) {
0547:                Entry e = removeEntryForKey(key);
0548:                return (e == null ? e : e.value);
0549:            }
0550:
0551:            /**
0552:             * Removes and returns the entry associated with the specified key
0553:             * in the HashMap.  Returns null if the HashMap contains no mapping
0554:             * for this key.
0555:             */
0556:            Entry removeEntryForKey(Object key) {
0557:                Object k = maskNull(key);
0558:                int hash = hash(k);
0559:                int i = indexFor(hash, table.length);
0560:                Entry prev = table[i];
0561:                Entry e = prev;
0562:
0563:                while (e != null) {
0564:                    Entry next = e.next;
0565:                    if (e.hash == hash && eq(k, e.key)) {
0566:                        modCount++;
0567:                        size--;
0568:                        if (prev == e)
0569:                            table[i] = next;
0570:                        else
0571:                            prev.next = next;
0572:                        e.recordRemoval(this );
0573:                        return e;
0574:                    }
0575:                    prev = e;
0576:                    e = next;
0577:                }
0578:
0579:                return e;
0580:            }
0581:
0582:            /**
0583:             * Special version of remove for EntrySet.
0584:             */
0585:            Entry removeMapping(Object o) {
0586:                if (!(o instanceof  Map.Entry))
0587:                    return null;
0588:
0589:                Map.Entry entry = (Map.Entry) o;
0590:                Object k = maskNull(entry.getKey());
0591:                int hash = hash(k);
0592:                int i = indexFor(hash, table.length);
0593:                Entry prev = table[i];
0594:                Entry e = prev;
0595:
0596:                while (e != null) {
0597:                    Entry next = e.next;
0598:                    if (e.hash == hash && e.equals(entry)) {
0599:                        modCount++;
0600:                        size--;
0601:                        if (prev == e)
0602:                            table[i] = next;
0603:                        else
0604:                            prev.next = next;
0605:                        e.recordRemoval(this );
0606:                        return e;
0607:                    }
0608:                    prev = e;
0609:                    e = next;
0610:                }
0611:
0612:                return e;
0613:            }
0614:
0615:            /**
0616:             * Removes all mappings from this map.
0617:             */
0618:            public void clear() {
0619:                modCount++;
0620:                Entry tab[] = table;
0621:                for (int i = 0; i < tab.length; i++)
0622:                    tab[i] = null;
0623:                size = 0;
0624:            }
0625:
0626:            /**
0627:             * Returns <tt>true</tt> if this map maps one or more keys to the
0628:             * specified value.
0629:             *
0630:             * @param value value whose presence in this map is to be tested.
0631:             * @return <tt>true</tt> if this map maps one or more keys to the
0632:             *         specified value.
0633:             */
0634:            public boolean containsValue(Object value) {
0635:                if (value == null)
0636:                    return containsNullValue();
0637:
0638:                Entry tab[] = table;
0639:                for (int i = 0; i < tab.length; i++)
0640:                    for (Entry e = tab[i]; e != null; e = e.next)
0641:                        if (value.equals(e.value))
0642:                            return true;
0643:                return false;
0644:            }
0645:
0646:            /**
0647:             * Special-case code for containsValue with null argument
0648:             **/
0649:            private boolean containsNullValue() {
0650:                Entry tab[] = table;
0651:                for (int i = 0; i < tab.length; i++)
0652:                    for (Entry e = tab[i]; e != null; e = e.next)
0653:                        if (e.value == null)
0654:                            return true;
0655:                return false;
0656:            }
0657:
0658:            /**
0659:             * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
0660:             * values themselves are not cloned.
0661:             *
0662:             * @return a shallow copy of this map.
0663:             */
0664:            public Object clone() {
0665:                HashMap result = null;
0666:                try {
0667:                    result = (HashMap) super .clone();
0668:                } catch (CloneNotSupportedException e) {
0669:                    // assert false;
0670:                }
0671:                result.table = new Entry[table.length];
0672:                result.entrySet = null;
0673:                result.modCount = 0;
0674:                result.size = 0;
0675:                result.init();
0676:                result.putAllForCreate(this );
0677:
0678:                return result;
0679:            }
0680:
0681:            static class Entry implements  Map.Entry {
0682:                final Object key;
0683:                Object value;
0684:                final int hash;
0685:                Entry next;
0686:
0687:                /**
0688:                 * Create new entry.
0689:                 */
0690:                Entry(int h, Object k, Object v, Entry n) {
0691:                    value = v;
0692:                    next = n;
0693:                    key = k;
0694:                    hash = h;
0695:                }
0696:
0697:                public Object getKey() {
0698:                    return unmaskNull(key);
0699:                }
0700:
0701:                public Object getValue() {
0702:                    return value;
0703:                }
0704:
0705:                public Object setValue(Object newValue) {
0706:                    Object oldValue = value;
0707:                    value = newValue;
0708:                    return oldValue;
0709:                }
0710:
0711:                public boolean equals(Object o) {
0712:                    if (!(o instanceof  Map.Entry))
0713:                        return false;
0714:                    Map.Entry e = (Map.Entry) o;
0715:                    Object k1 = getKey();
0716:                    Object k2 = e.getKey();
0717:                    if (k1 == k2 || (k1 != null && k1.equals(k2))) {
0718:                        Object v1 = getValue();
0719:                        Object v2 = e.getValue();
0720:                        if (v1 == v2 || (v1 != null && v1.equals(v2)))
0721:                            return true;
0722:                    }
0723:                    return false;
0724:                }
0725:
0726:                public int hashCode() {
0727:                    return (key == NULL_KEY ? 0 : key.hashCode())
0728:                            ^ (value == null ? 0 : value.hashCode());
0729:                }
0730:
0731:                public String toString() {
0732:                    return getKey() + "=" + getValue();
0733:                }
0734:
0735:                /**
0736:                 * This method is invoked whenever the value in an entry is
0737:                 * overwritten by an invocation of put(k,v) for a key k that's already
0738:                 * in the HashMap.
0739:                 */
0740:                void recordAccess(HashMap m) {
0741:                }
0742:
0743:                /**
0744:                 * This method is invoked whenever the entry is
0745:                 * removed from the table.
0746:                 */
0747:                void recordRemoval(HashMap m) {
0748:                }
0749:            }
0750:
0751:            /**
0752:             * Add a new entry with the specified key, value and hash code to
0753:             * the specified bucket.  It is the responsibility of this 
0754:             * method to resize the table if appropriate.
0755:             *
0756:             * Subclass overrides this to alter the behavior of put method.
0757:             */
0758:            void addEntry(int hash, Object key, Object value, int bucketIndex) {
0759:                table[bucketIndex] = new Entry(hash, key, value,
0760:                        table[bucketIndex]);
0761:                if (size++ >= threshold)
0762:                    resize(2 * table.length);
0763:            }
0764:
0765:            /**
0766:             * Like addEntry except that this version is used when creating entries
0767:             * as part of Map construction or "pseudo-construction" (cloning,
0768:             * deserialization).  This version needn't worry about resizing the table.
0769:             *
0770:             * Subclass overrides this to alter the behavior of HashMap(Map),
0771:             * clone, and readObject.
0772:             */
0773:            void createEntry(int hash, Object key, Object value, int bucketIndex) {
0774:                table[bucketIndex] = new Entry(hash, key, value,
0775:                        table[bucketIndex]);
0776:                size++;
0777:            }
0778:
0779:            private abstract class HashIterator implements  Iterator {
0780:                Entry next; // next entry to return
0781:                int expectedModCount; // For fast-fail 
0782:                int index; // current slot 
0783:                Entry current; // current entry
0784:
0785:                HashIterator() {
0786:                    expectedModCount = modCount;
0787:                    Entry[] t = table;
0788:                    int i = t.length;
0789:                    Entry n = null;
0790:                    if (size != 0) { // advance to first entry
0791:                        while (i > 0 && (n = t[--i]) == null)
0792:                            ;
0793:                    }
0794:                    next = n;
0795:                    index = i;
0796:                }
0797:
0798:                public boolean hasNext() {
0799:                    return next != null;
0800:                }
0801:
0802:                Entry nextEntry() {
0803:                    if (modCount != expectedModCount)
0804:                        throw new ConcurrentModificationException();
0805:                    Entry e = next;
0806:                    if (e == null)
0807:                        throw new NoSuchElementException();
0808:
0809:                    Entry n = e.next;
0810:                    Entry[] t = table;
0811:                    int i = index;
0812:                    while (n == null && i > 0)
0813:                        n = t[--i];
0814:                    index = i;
0815:                    next = n;
0816:                    return current = e;
0817:                }
0818:
0819:                public void remove() {
0820:                    if (current == null)
0821:                        throw new IllegalStateException();
0822:                    if (modCount != expectedModCount)
0823:                        throw new ConcurrentModificationException();
0824:                    Object k = current.key;
0825:                    current = null;
0826:                    HashMap.this .removeEntryForKey(k);
0827:                    expectedModCount = modCount;
0828:                }
0829:
0830:            }
0831:
0832:            private class ValueIterator extends HashIterator {
0833:                public Object next() {
0834:                    return nextEntry().value;
0835:                }
0836:            }
0837:
0838:            private class KeyIterator extends HashIterator {
0839:                public Object next() {
0840:                    return nextEntry().getKey();
0841:                }
0842:            }
0843:
0844:            private class EntryIterator extends HashIterator {
0845:                public Object next() {
0846:                    return nextEntry();
0847:                }
0848:            }
0849:
0850:            // Subclass overrides these to alter behavior of views' iterator() method
0851:            Iterator newKeyIterator() {
0852:                return new KeyIterator();
0853:            }
0854:
0855:            Iterator newValueIterator() {
0856:                return new ValueIterator();
0857:            }
0858:
0859:            Iterator newEntryIterator() {
0860:                return new EntryIterator();
0861:            }
0862:
0863:            // Views
0864:
0865:            private transient Set entrySet = null;
0866:
0867:            /**
0868:             * Returns a set view of the keys contained in this map.  The set is
0869:             * backed by the map, so changes to the map are reflected in the set, and
0870:             * vice-versa.  The set supports element removal, which removes the
0871:             * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
0872:             * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
0873:             * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
0874:             * <tt>addAll</tt> operations.
0875:             *
0876:             * @return a set view of the keys contained in this map.
0877:             */
0878:            public Set keySet() {
0879:                Set ks = keySet;
0880:                return (ks != null ? ks : (keySet = new KeySet()));
0881:            }
0882:
0883:            private class KeySet extends AbstractSet {
0884:                public Iterator iterator() {
0885:                    return newKeyIterator();
0886:                }
0887:
0888:                public int size() {
0889:                    return size;
0890:                }
0891:
0892:                public boolean contains(Object o) {
0893:                    return containsKey(o);
0894:                }
0895:
0896:                public boolean remove(Object o) {
0897:                    return HashMap.this .removeEntryForKey(o) != null;
0898:                }
0899:
0900:                public void clear() {
0901:                    HashMap.this .clear();
0902:                }
0903:            }
0904:
0905:            /**
0906:             * Returns a collection view of the values contained in this map.  The
0907:             * collection is backed by the map, so changes to the map are reflected in
0908:             * the collection, and vice-versa.  The collection supports element
0909:             * removal, which removes the corresponding mapping from this map, via the
0910:             * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0911:             * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
0912:             * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0913:             *
0914:             * @return a collection view of the values contained in this map.
0915:             */
0916:            public Collection values() {
0917:                Collection vs = values;
0918:                return (vs != null ? vs : (values = new Values()));
0919:            }
0920:
0921:            private class Values extends AbstractCollection {
0922:                public Iterator iterator() {
0923:                    return newValueIterator();
0924:                }
0925:
0926:                public int size() {
0927:                    return size;
0928:                }
0929:
0930:                public boolean contains(Object o) {
0931:                    return containsValue(o);
0932:                }
0933:
0934:                public void clear() {
0935:                    HashMap.this .clear();
0936:                }
0937:            }
0938:
0939:            /**
0940:             * Returns a collection view of the mappings contained in this map.  Each
0941:             * element in the returned collection is a <tt>Map.Entry</tt>.  The
0942:             * collection is backed by the map, so changes to the map are reflected in
0943:             * the collection, and vice-versa.  The collection supports element
0944:             * removal, which removes the corresponding mapping from the map, via the
0945:             * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0946:             * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
0947:             * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0948:             *
0949:             * @return a collection view of the mappings contained in this map.
0950:             * @see Map.Entry
0951:             */
0952:            public Set entrySet() {
0953:                Set es = entrySet;
0954:                return (es != null ? es : (entrySet = new EntrySet()));
0955:            }
0956:
0957:            private class EntrySet extends AbstractSet {
0958:                public Iterator iterator() {
0959:                    return newEntryIterator();
0960:                }
0961:
0962:                public boolean contains(Object o) {
0963:                    if (!(o instanceof  Map.Entry))
0964:                        return false;
0965:                    Map.Entry e = (Map.Entry) o;
0966:                    Entry candidate = getEntry(e.getKey());
0967:                    return candidate != null && candidate.equals(e);
0968:                }
0969:
0970:                public boolean remove(Object o) {
0971:                    return removeMapping(o) != null;
0972:                }
0973:
0974:                public int size() {
0975:                    return size;
0976:                }
0977:
0978:                public void clear() {
0979:                    HashMap.this .clear();
0980:                }
0981:            }
0982:
0983:            /**
0984:             * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
0985:             * serialize it).
0986:             *
0987:             * @serialData The <i>capacity</i> of the HashMap (the length of the
0988:             *		   bucket array) is emitted (int), followed  by the
0989:             *		   <i>size</i> of the HashMap (the number of key-value
0990:             *		   mappings), followed by the key (Object) and value (Object)
0991:             *		   for each key-value mapping represented by the HashMap
0992:             *             The key-value mappings are emitted in the order that they
0993:             *             are returned by <tt>entrySet().iterator()</tt>.
0994:             * 
0995:             */
0996:            private void writeObject(java.io.ObjectOutputStream s)
0997:                    throws IOException {
0998:                // Write out the threshold, loadfactor, and any hidden stuff
0999:                s.defaultWriteObject();
1000:
1001:                // Write out number of buckets
1002:                s.writeInt(table.length);
1003:
1004:                // Write out size (number of Mappings)
1005:                s.writeInt(size);
1006:
1007:                // Write out keys and values (alternating)
1008:                for (Iterator i = entrySet().iterator(); i.hasNext();) {
1009:                    Map.Entry e = (Map.Entry) i.next();
1010:                    s.writeObject(e.getKey());
1011:                    s.writeObject(e.getValue());
1012:                }
1013:            }
1014:
1015:            private static final long serialVersionUID = 362498820763181265L;
1016:
1017:            /**
1018:             * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
1019:             * deserialize it).
1020:             */
1021:            private void readObject(java.io.ObjectInputStream s)
1022:                    throws IOException, ClassNotFoundException {
1023:                // Read in the threshold, loadfactor, and any hidden stuff
1024:                s.defaultReadObject();
1025:
1026:                // Read in number of buckets and allocate the bucket array;
1027:                int numBuckets = s.readInt();
1028:                table = new Entry[numBuckets];
1029:
1030:                init(); // Give subclass a chance to do its thing.
1031:
1032:                // Read in size (number of Mappings)
1033:                int size = s.readInt();
1034:
1035:                // Read the keys and values, and put the mappings in the HashMap
1036:                for (int i = 0; i < size; i++) {
1037:                    Object key = s.readObject();
1038:                    Object value = s.readObject();
1039:                    putForCreate(key, value);
1040:                }
1041:            }
1042:
1043:            // These methods are used when serializing HashSets
1044:            int capacity() {
1045:                return table.length;
1046:            }
1047:
1048:            float loadFactor() {
1049:                return loadFactor;
1050:            }
1051:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.