Source Code Cross Referenced for HashMap.java in  » 6.0-JDK-Core » Collections-Jar-Zip-Logging-regex » java » util » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Home
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
26.ERP CRM Financial
27.ESB
28.Forum
29.Game
30.GIS
31.Graphic 3D
32.Graphic Library
33.Groupware
34.HTML Parser
35.IDE
36.IDE Eclipse
37.IDE Netbeans
38.Installer
39.Internationalization Localization
40.Inversion of Control
41.Issue Tracking
42.J2EE
43.J2ME
44.JBoss
45.JMS
46.JMX
47.Library
48.Mail Clients
49.Music
50.Net
51.Parser
52.PDF
53.Portal
54.Profiler
55.Project Management
56.Report
57.RSS RDF
58.Rule Engine
59.Science
60.Scripting
61.Search Engine
62.Security
63.Sevlet Container
64.Source Control
65.Swing Library
66.Template Engine
67.Test Coverage
68.Testing
69.UML
70.Web Crawler
71.Web Framework
72.Web Mail
73.Web Server
74.Web Services
75.Web Services apache cxf 2.2.6
76.Web Services AXIS2
77.Wiki Engine
78.Workflow Engines
79.XML
80.XML UI
Java Source Code / Java Documentation » 6.0 JDK Core » Collections Jar Zip Logging regex » java.util 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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