abstracthashedmap.java

来自「drools 一个开放源码的规则引擎」· Java 代码 · 共 1,652 行 · 第 1/4 页

    {
        modCount++;
        HashEntry[] data = this.data;
        for ( int i = data.length - 1; i >= 0; i-- )
        {
            data[i] = null;
        }
        size = 0;
    }

    // -----------------------------------------------------------------------
    /**
     * Converts input keys to another object for storage in the map. This
     * implementation masks nulls. Subclasses can override this to perform
     * alternate key conversions.
     * <p>
     * The reverse conversion can be changed, if required, by overriding the
     * getKey() method in the hash entry.
     *
     * @param key
     *            the key convert
     * @return the converted key
     */
    protected Object convertKey(Object key)
    {
        return (key == null ? NULL : key);
    }

    /**
     * Gets the hash code for the key specified. This implementation uses the
     * additional hashing routine from JDK1.4. Subclasses can override this to
     * return alternate hash codes.
     *
     * @param key
     *            the key to get a hash code for
     * @return the hash code
     */
    protected int hash(Object key)
    {
        // same as JDK 1.4
        int h = key.hashCode( );
        h += ~(h << 9);
        h ^= (h >>> 14);
        h += (h << 4);
        h ^= (h >>> 10);
        return h;
    }

    /**
     * Compares two keys, in internal converted form, to see if they are equal.
     * This implementation uses the equals method and assumes neither key is
     * null. Subclasses can override this to match differently.
     *
     * @param key1
     *            the first key to compare passed in from outside
     * @param key2
     *            the second key extracted from the entry via
     *            <code>entry.key</code>
     * @return true if equal
     */
    protected boolean isEqualKey(Object key1,
                                 Object key2)
    {
        return (key1 == key2 || key1.equals( key2 ));
    }

    /**
     * Compares two values, in external form, to see if they are equal. This
     * implementation uses the equals method and assumes neither value is null.
     * Subclasses can override this to match differently.
     *
     * @param value1
     *            the first value to compare passed in from outside
     * @param value2
     *            the second value extracted from the entry via
     *            <code>getValue()</code>
     * @return true if equal
     */
    protected boolean isEqualValue(Object value1,
                                   Object value2)
    {
        return (value1 == value2 || value1.equals( value2 ));
    }

    /**
     * Gets the index into the data storage for the hashCode specified. This
     * implementation uses the least significant bits of the hashCode.
     * Subclasses can override this to return alternate bucketing.
     *
     * @param hashCode
     *            the hash code to use
     * @param dataSize
     *            the size of the data to pick a bucket from
     * @return the bucket index
     */
    protected int hashIndex(int hashCode,
                            int dataSize)
    {
        return hashCode & (dataSize - 1);
    }

    // -----------------------------------------------------------------------
    /**
     * Gets the entry mapped to the key specified.
     * <p>
     * This method exists for subclasses that may need to perform a multi-step
     * process accessing the entry. The public methods in this class don't use
     * this method to gain a small performance boost.
     *
     * @param key
     *            the key
     * @return the entry, null if no match
     */
    protected HashEntry getEntry(Object key)
    {
        key = convertKey( key );
        int hashCode = hash( key );
        HashEntry entry = data[hashIndex( hashCode,
                                          data.length )]; // no local for hash
                                                            // index
        while ( entry != null )
        {
            if ( entry.hashCode == hashCode && isEqualKey( key,
                                                           entry.key ) )
            {
                return entry;
            }
            entry = entry.next;
        }
        return null;
    }

    // -----------------------------------------------------------------------
    /**
     * Updates an existing key-value mapping to change the value.
     * <p>
     * This implementation calls <code>setValue()</code> on the entry.
     * Subclasses could override to handle changes to the map.
     *
     * @param entry
     *            the entry to update
     * @param newValue
     *            the new value to store
     */
    protected void updateEntry(HashEntry entry,
                               Object newValue)
    {
        entry.setValue( newValue );
    }

    /**
     * Reuses an existing key-value mapping, storing completely new data.
     * <p>
     * This implementation sets all the data fields on the entry. Subclasses
     * could populate additional entry fields.
     *
     * @param entry
     *            the entry to update, not null
     * @param hashIndex
     *            the index in the data array
     * @param hashCode
     *            the hash code of the key to add
     * @param key
     *            the key to add
     * @param value
     *            the value to add
     */
    protected void reuseEntry(HashEntry entry,
                              int hashIndex,
                              int hashCode,
                              Object key,
                              Object value)
    {
        entry.next = data[hashIndex];
        entry.hashCode = hashCode;
        entry.key = key;
        entry.value = value;
    }

    // -----------------------------------------------------------------------
    /**
     * Adds a new key-value mapping into this map.
     * <p>
     * This implementation calls <code>createEntry()</code>,
     * <code>addEntry()</code> and <code>checkCapacity()</code>. It also
     * handles changes to <code>modCount</code> and <code>size</code>.
     * Subclasses could override to fully control adds to the map.
     *
     * @param hashIndex
     *            the index into the data array to store at
     * @param hashCode
     *            the hash code of the key to add
     * @param key
     *            the key to add
     * @param value
     *            the value to add
     */
    protected void addMapping(int hashIndex,
                              int hashCode,
                              Object key,
                              Object value)
    {
        modCount++;
        HashEntry entry = createEntry( data[hashIndex],
                                       hashCode,
                                       key,
                                       value );
        addEntry( entry,
                  hashIndex );
        size++;
        checkCapacity( );
    }

    /**
     * Creates an entry to store the key-value data.
     * <p>
     * This implementation creates a new HashEntry instance. Subclasses can
     * override this to return a different storage class, or implement caching.
     *
     * @param next
     *            the next entry in sequence
     * @param hashCode
     *            the hash code to use
     * @param key
     *            the key to store
     * @param value
     *            the value to store
     * @return the newly created entry
     */
    protected HashEntry createEntry(HashEntry next,
                                    int hashCode,
                                    Object key,
                                    Object value)
    {
        return new HashEntry( next,
                              hashCode,
                              key,
                              value );
    }

    /**
     * Adds an entry into this map.
     * <p>
     * This implementation adds the entry to the data storage table. Subclasses
     * could override to handle changes to the map.
     *
     * @param entry
     *            the entry to add
     * @param hashIndex
     *            the index into the data array to store at
     */
    protected void addEntry(HashEntry entry,
                            int hashIndex)
    {
        data[hashIndex] = entry;
    }

    // -----------------------------------------------------------------------
    /**
     * Removes a mapping from the map.
     * <p>
     * This implementation calls <code>removeEntry()</code> and
     * <code>destroyEntry()</code>. It also handles changes to
     * <code>modCount</code> and <code>size</code>. Subclasses could
     * override to fully control removals from the map.
     *
     * @param entry
     *            the entry to remove
     * @param hashIndex
     *            the index into the data structure
     * @param previous
     *            the previous entry in the chain
     */
    protected void removeMapping(HashEntry entry,
                                 int hashIndex,
                                 HashEntry previous)
    {
        modCount++;
        removeEntry( entry,
                     hashIndex,
                     previous );
        size--;
        destroyEntry( entry );
    }

    /**
     * Removes an entry from the chain stored in a particular index.
     * <p>
     * This implementation removes the entry from the data storage table. The
     * size is not updated. Subclasses could override to handle changes to the
     * map.
     *
     * @param entry
     *            the entry to remove
     * @param hashIndex
     *            the index into the data structure
     * @param previous
     *            the previous entry in the chain
     */
    protected void removeEntry(HashEntry entry,
                               int hashIndex,
                               HashEntry previous)
    {
        if ( previous == null )
        {
            data[hashIndex] = entry.next;
        }
        else
        {
            previous.next = entry.next;
        }
    }

    /**
     * Kills an entry ready for the garbage collector.
     * <p>
     * This implementation prepares the HashEntry for garbage collection.
     * Subclasses can override this to implement caching (override clear as
     * well).
     *
     * @param entry
     *            the entry to destroy
     */
    protected void destroyEntry(HashEntry entry)
    {
        entry.next = null;
        entry.key = null;
        entry.value = null;
    }

    // -----------------------------------------------------------------------
    /**
     * Checks the capacity of the map and enlarges it if necessary.
     * <p>
     * This implementation uses the threshold to check if the map needs
     * enlarging
     */
    protected void checkCapacity()
    {
        if ( size >= threshold )
        {
            int newCapacity = data.length * 2;
            if ( newCapacity <= MAXIMUM_CAPACITY )
            {
                ensureCapacity( newCapacity );
            }
        }
    }

    /**
     * Changes the size of the data structure to the capacity proposed.
     *
     * @param newCapacity
     *            the new capacity of the array (a power of two, less or equal
     *            to max)
     */
    protected void ensureCapacity(int newCapacity)
    {
        int oldCapacity = data.length;
        if ( newCapacity <= oldCapacity )
        {
            return;
        }
        if ( size == 0 )
        {
            threshold = calculateThreshold( newCapacity,
                                            loadFactor );
            data = new HashEntry[newCapacity];
        }
        else
        {
            HashEntry oldEntries[] = data;
            HashEntry newEntries[] = new HashEntry[newCapacity];

            modCount++;
            for ( int i = oldCapacity - 1; i >= 0; i-- )
            {
                HashEntry entry = oldEntries[i];
                if ( entry != null )
                {
                    oldEntries[i] = null; // gc
                    do
                    {
                        HashEntry next = entry.next;
                        int index = hashIndex( entry.hashCode,
                                               newCapacity );
                        entry.next = newEntries[index];
                        newEntries[index] = entry;
                        entry = next;
                    }
                    while ( entry != null );
                }
            }
            threshold = calculateThreshold( newCapacity,
                                            loadFactor );
            data = newEntries;
        }
    }

    /**
     * Calculates the new capacity of the map. This implementation normalizes
     * the capacity to a power of two.
     *
     * @param proposedCapacity
     *            the proposed capacity
     * @return the normalized new capacity
     */
    protected int calculateNewCapacity(int proposedCapacity)
    {
        int newCapacity = 1;
        if ( proposedCapacity > MAXIMUM_CAPACITY )
        {
            newCapacity = MAXIMUM_CAPACITY;