longhashmap.java

这个是网络上下载的一个struct框架的程序

/**
 * $RCSfile: LongHashMap.java,v $
 * $Revision: 1.1 $
 * $Date: 2002/06/24 18:51:23 $
 *
 * This class was adapted directly from the Colt sources by CoolServlets Inc.
 * The changes involved modifying the code so that the functionality could be
 * encapsulated in a single class file.
 *
 * As such, the original copyright is left intact and this file is distributed
 * under the original Colt license as seen below. Please visit the Colt
 * homepage for more information about the excellent package:
 * http://tilde-hoschek.home.cern.ch/~hoschek/colt/index.htm
 * ---------------------------------------------------------------------------
 * Copyright ?? 1999 CERN - European Organization for Nuclear Research.
 * Permission to use, copy, modify, distribute and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that copyright
 * notice and this permission notice appear in supporting documentation. CERN
 * makes no representations about the suitability of this software for any
 * purpose. It is provided "as is" without expressed or implied warranty.
 */

package com.struts2.framework.util;

/**
 * Hash map holding (key,value) associations of type <tt>(long-->Object)</tt>;
 * Automatically grows and shrinks as needed; Implemented using open addressing
 * with double hashing.<p>
 *
 * Adapted from the Colt package by CoolServlets. Please visit the Colt
 * homepage at: http://tilde-hoschek.home.cern.ch/~hoschek/colt/index.htm
 *
 * @author [e-mail]
 */
public final class LongHashMap {

    //The hash table keys.
    protected long table[];
    //The hash table values.
    protected Object values[];
    //The state of each hash table entry (FREE, FULL, REMOVED).
    protected byte state[];
    //The number of table entries in state==FREE.
    protected int freeEntries;

    //The number of distinct associations in the map; its "size()".
    protected int distinct;

    /**
     * The table capacity c=table.length always satisfies the invariant
     * <tt>c * minLoadFactor <= s <= c * maxLoadFactor</tt>, where s=size() is
     * the number of associations currently contained. The term
     * "c * minLoadFactor" is called the "lowWaterMark", "c * maxLoadFactor" is
     * called the "highWaterMark". In other words, the table capacity (and
     * proportionally the memory used by this class) oscillates within these
     * constraints. The terms are precomputed and cached to avoid recalculating
     * them each time put(..) or removeKey(...) is called.
     */
    protected int lowWaterMark;
    protected int highWaterMark;

    //The minimum load factor for the hashtable.
    protected double minLoadFactor;
    //The maximum load factor for the hashtable.
    protected double maxLoadFactor;

    protected static final int DEFAULT_CAPACITY = 277;
    protected static final double DEFAULT_MIN_LOAD_FACTOR = 0.2;
    protected static final double DEFAULT_MAX_LOAD_FACTOR = 0.6;

    protected static final byte FREE = 0;
    protected static final byte FULL = 1;
    protected static final byte REMOVED = 2;

    /**
     * Constructs an empty map with default capacity and default load factors.
     */
    public LongHashMap() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * Constructs an empty map with the specified initial capacity and default
     * load factors.
     *
     * @param      initialCapacity   the initial capacity of the map.
     * @throws     IllegalArgumentException if the initial capacity is less
     *             than zero.
     */
    public LongHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_MIN_LOAD_FACTOR, DEFAULT_MAX_LOAD_FACTOR);
    }

    /**
     * Constructs an empty map with the specified initial capacity and the
     * specified minimum and maximum load factor.
     *
     * @param      initialCapacity   the initial capacity.
     * @param      minLoadFactor        the minimum load factor.
     * @param      maxLoadFactor        the maximum load factor.
     * @throws	IllegalArgumentException if <tt>initialCapacity < 0 ||
     *      (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
     *      (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) ||
     *      (minLoadFactor >= maxLoadFactor)</tt>.
     */
    public LongHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
        setUp(initialCapacity,minLoadFactor,maxLoadFactor);
    }

    /**
     * Removes all (key,value) associations from the receiver.
     * Implicitly calls <tt>trimToSize()</tt>.
     */
    public void clear() {
        for (int i=0; i<state.length; i++) {
            state[i] = FREE;
        }
        for (int i=0; i<values.length-1; i++) {
            values[i] = null;
        }

        this.distinct = 0;
        this.freeEntries = table.length; // delta
        trimToSize();
    }

    /**
     * Returns <tt>true</tt> if the receiver contains the specified key.
     *
     * @return <tt>true</tt> if the receiver contains the specified key.
     */
    public boolean containsKey(long key) {
        return indexOfKey(key) >= 0;
    }

    /**
     * Returns <tt>true</tt> if the receiver contains the specified value.
    *
     * @return <tt>true</tt> if the receiver contains the specified value.
     */
    public boolean containsValue(Object value) {
        return indexOfValue(value) >= 0;
    }

    /**
     * Ensures that the receiver can hold at least the specified number of
     * associations without needing to allocate new internal memory. If
     * necessary, allocates new internal memory and increases the capacity of
     * the receiver.<p>
     *
     * This method never need be called; it is for performance tuning only.
     * Calling this method before <tt>put()</tt>ing a large number of
     * associations boosts performance, because the receiver will grow only
     * once instead of potentially many times and hash collisions get less
     * probable.
     *
     * @param minCapacity the desired minimum capacity.
     */
    public void ensureCapacity(int minCapacity) {
        if (table.length < minCapacity) {
            int newCapacity = nextPrime(minCapacity);
            rehash(newCapacity);
        }
    }

    /**
     * Returns the value associated with the specified key.
     * It is often a good idea to first check with {@link #containsKey(long)}
     * whether the given key has a value associated or not, i.e. whether there
     * exists an association for the given key or not.
     *
     * @param key the key to be searched for.
     * @return the value associated with the specified key; <tt>null</tt> if no
     *      such key is present.
     */
    public final Object get(long key) {
        int i = indexOfKey(key);
        //If not in the map return null
        if (i<0) {
            return null;
        }
        else {
            return values[i];
        }
    }

    /**
     * Returns the index where the key would need to be inserted, if it is not
     * already contained. Returns -index-1 if the key is already contained
     * at slot index. Therefore, if the returned index < 0, then it is
     * already contained at slot -index-1. If the returned index >= 0,
     * then it is NOT already contained and should be inserted at slot index.
     *
     * @param key the key to be added to the receiver.
     * @return the index where the key would need to be inserted.
     */
    private final int indexOfInsertion(long key) {
        final long tab[] = table;
        final byte stat[] = state;
        final int length = tab.length;

        final int hash = ((int)(key ^ (key >> 32))) & 0x7FFFFFFF;
        int i = hash % length;
        // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
        int decrement = (hash) % (length-2);
        //OLD CODE: int decrement = (hash / length) % length;
        if (decrement == 0) decrement = 1;

        // stop if we find a removed or free slot, or if we find the key itself
        // do NOT skip over removed slots (yes, open addressing is like that...)
        while (stat[i] == FULL && tab[i] != key) {
        i -= decrement;
            //hashCollisions++;
            if (i<0) i+=length;
        }

        if (stat[i] == REMOVED) {
            // stop if we find a free slot, or if we find the key itself.
            // do skip over removed slots (yes, open addressing is like that...)
            // assertion: there is at least one FREE slot.
            int j = i;
            while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
                i -= decrement;
                //hashCollisions++;
                if (i<0) i+=length;
            }
            if (stat[i] == FREE) i = j;
        }

        if (stat[i] == FULL) {
            // key already contained at slot i.
            // return a negative number identifying the slot.
            return -i-1;
        }
        // not already contained, should be inserted at slot i.
        // return a number >= 0 identifying the slot.
        return i;
    }

    /**
     * @param key the key to be searched in the receiver.
     * @return the index where the key is contained in the receiver, returns -1
     *      if the key was not found.
     */
    private final int indexOfKey(long key) {
        final long tab[] = table;
        final byte stat[] = state;
        final int length = tab.length;

        final int hash = ((int)(key ^ (key >> 32))) & 0x7FFFFFFF;
        int i = hash % length;
        // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
        int decrement = (hash) % (length-2);
        //OLD CODE: int decrement = (hash / length) % length;
        if (decrement == 0) decrement = 1;

        // stop if we find a free slot, or if we find the key itself.
        // do skip over removed slots (yes, open addressing is like that...)
        while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
            i -= decrement;
            //hashCollisions++;
            if (i<0) i+=length;
        }

        if (stat[i] == FREE) return -1; // not found
        return i; //found, return index where key is contained
    }


    /**
     * @param value the value to be searched in the receiver.
     * @return the index where the value is contained in the receiver,
     *      returns -1 if the value was not found.
     */
    protected int indexOfValue(Object value) {
        final Object val[] = values;
        final byte stat[] = state;

        for (int i=stat.length; --i >= 0;) {
            if (stat[i]==FULL && val[i]==value) return i;
        }

        return -1; // not found
    }

    /**
     * Returns the first key the given value is associated with.
     *
     * @param value the value to search for.
     * @return the first key for which holds <tt>get(key) == value</tt>;
     *		   returns <tt>Long.MIN_VALUE</tt> if no such key exists.
     */
    public long keyOf(Object value) {
        //returns the first key found; there may be more matching keys, however.
        int i = indexOfValue(value);
        if (i<0) return Long.MIN_VALUE;
        return table[i];
    }

    /**
     * Returns all the keys in the map.
     */
    public long[] keys() {
        long[] elements = new long[distinct];
        long[] tab = table;
        byte[] stat = state;
        int j=0;
        for (int i = tab.length ; i-- > 0 ;) {
            if (stat[i]==FULL) {
                elements[j++]=tab[i];
            }
        }
        return elements;
    }

    /**
     * Associates the given key with the given value. Replaces any old
     * <tt>(key,someOtherValue)</tt> association, if existing.
     *
     * @param key the key the value shall be associated with.
     * @param value the value to be associated.
     * @return <tt>true</tt> if the receiver did not already contain such a key;
     *      <tt>false</tt> if the receiver did already contain such a key - the
     *      new value has now replaced the formerly associated value.
     */
    public boolean put(long key, Object value) {
        int i = indexOfInsertion(key);
        if (i<0) { //already contained
            i = -i -1;
            this.values[i]=value;
            return false;
        }

        if (this.distinct > this.highWaterMark) {
            int newCapacity = chooseGrowCapacity(
                    this.distinct+1,
                    this.minLoadFactor,
                    this.maxLoadFactor
                );
            rehash(newCapacity);
            return put(key, value);
        }

        this.table[i]=key;
        this.values[i]=value;
        if (this.state[i]==FREE) this.freeEntries--;
        this.state[i]=FULL;