longhashmap.java

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

        this.distinct++;

        if (this.freeEntries < 1) { //delta
            int newCapacity = chooseGrowCapacity(
                    this.distinct+1,
                    this.minLoadFactor,
                    this.maxLoadFactor
                );
            rehash(newCapacity);
        }

        return true;
    }

    /**
     * Returns the number of (key,value) associations currently contained.
     *
     * @return the number of (key,value) associations currently contained.
     */
    public int size() {
        return distinct;
    }

    /**
     * Returns <tt>true</tt> if the receiver contains no (key,value) associations.
     *
     * @return <tt>true</tt> if the receiver contains no (key,value) associations.
     */
    public boolean isEmpty() {
        return distinct == 0;
    }

    /**
     * Rehashes the contents of the receiver into a new table
     * with a smaller or larger capacity.
     * This method is called automatically when the
     * number of keys in the receiver exceeds the high water mark or falls
     * below the low water mark.
     */
    protected void rehash(int newCapacity) {
        int oldCapacity = table.length;
        //if (oldCapacity == newCapacity) return;

        long oldTable[] = table;
        Object oldValues[] = values;
        byte oldState[] = state;

        long newTable[] = new long[newCapacity];
        Object newValues[] = new Object[newCapacity];
        byte newState[] = new byte[newCapacity];

        this.lowWaterMark  = chooseLowWaterMark(newCapacity,this.minLoadFactor);
        this.highWaterMark = chooseHighWaterMark(newCapacity,this.maxLoadFactor);

        this.table = newTable;
        this.values = newValues;
        this.state = newState;
        this.freeEntries = newCapacity-this.distinct; // delta

        for (int i = oldCapacity ; i-- > 0 ;) {
            if (oldState[i]==FULL) {
                long element = oldTable[i];
                int index = indexOfInsertion(element);
                newTable[index]=element;
                newValues[index]=oldValues[i];
                newState[index]=FULL;
            }
        }
    }

    /**
     * Removes the given key with its associated element from the receiver, if
     * present.
     *
     * @param key the key to be removed from the receiver.
     * @return <tt>true</tt> if the receiver contained the specified key,
     *      <tt>false</tt> otherwise.
     */
    public boolean removeKey(long key) {
        int i = indexOfKey(key);
        if (i<0) return false; // key not contained

        this.state[i]=REMOVED;
        this.values[i]=null; // delta
        this.distinct--;

        if (this.distinct < this.lowWaterMark) {
                int newCapacity = chooseShrinkCapacity(
                        this.distinct,
                        this.minLoadFactor,
                        this.maxLoadFactor
                    );
                rehash(newCapacity);
        }

        return true;
    }

    /**
     * Initializes the receiver.
     *
     * @param      initialCapacity   the initial capacity of the receiver.
     * @param      minLoadFactor        the minLoadFactor of the receiver.
     * @param      maxLoadFactor        the maxLoadFactor of the receiver.
     * @throws	IllegalArgumentException if <tt>initialCapacity < 0 ||
     *      (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
     *      (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) ||
     *      (minLoadFactor >= maxLoadFactor)</tt>.
     */
    protected void setUp(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException(
                "Initial Capacity must not be less than zero: "+ initialCapacity
            );
        }
        if (minLoadFactor < 0.0 || minLoadFactor >= 1.0) {
                throw new IllegalArgumentException(
                    "Illegal minLoadFactor: "+ minLoadFactor
                );
        }
        if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) {
                throw new IllegalArgumentException(
                    "Illegal maxLoadFactor: "+ maxLoadFactor
                );
        }
        if (minLoadFactor >= maxLoadFactor) {
                throw new IllegalArgumentException(
                    "Illegal minLoadFactor: " + minLoadFactor +
                    " and maxLoadFactor: " + maxLoadFactor
                );
        }

        int capacity = initialCapacity;
        capacity = nextPrime(capacity);
        // open addressing needs at least one FREE slot at any time.
        if (capacity==0) {
            capacity=1;
        }

        this.table = new long[capacity];
        this.values = new Object[capacity];
        this.state = new byte[capacity];

        //memory will be exhausted long before this pathological case happens, anyway.
        this.minLoadFactor = minLoadFactor;
        if (capacity == LARGEST_PRIME) this.maxLoadFactor = 1.0;
        else this.maxLoadFactor = maxLoadFactor;

        this.distinct = 0;
        this.freeEntries = capacity; // delta

        /**
         * lowWaterMark will be established upon first expansion. Establishing
         * it now (upon instance construction) would immediately make the table
         * shrink upon first put(...). After all the idea of an
         * "initialCapacity" implies violating lowWaterMarks when an object is
         * young. See ensureCapacity(...)
         */
        this.lowWaterMark = 0;
        this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
    }

    /**
     * Trims the capacity of the receiver to be the receiver's current size.
     * Releases any superfluous internal memory. An application can use this
     * operation to minimize the storage of the receiver.
     */
    public void trimToSize() {
        //*1.2 because open addressing's performance exponentially degrades
        //beyond that point so that even rehashing the table can take very long
        int newCapacity = nextPrime((int)(1 + 1.2*size()));
        if (table.length > newCapacity) {
            rehash(newCapacity);
        }
    }

    /**
     * Returns an array of all the values in the Map.
     */
    public Object[] values() {
        Object[] elements = new Object[distinct];

        Object[] val = values;
        byte[] stat = state;

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

    /**
     * Chooses a new prime table capacity optimized for growing that
     * (approximately) satisfies the invariant
     * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt>
     * and has at least one FREE slot for the given size.
     */
    private int chooseGrowCapacity(int size, double minLoad, double maxLoad) {
        return nextPrime(Math.max(size+1, (int) ((4*size / (3*minLoad+maxLoad)))));
    }

    /**
     * Returns new high water mark threshold based on current capacity and
     * maxLoadFactor.
     *
     * @return int the new threshold.
     */
    private int chooseHighWaterMark(int capacity, double maxLoad) {
        //makes sure there is always at least one FREE slot
        return Math.min(capacity-2, (int) (capacity * maxLoad));
    }

    /**
     * Returns new low water mark threshold based on current capacity and minLoadFactor.
     * @return int the new threshold.
     */
    protected int chooseLowWaterMark(int capacity, double minLoad) {
        return (int) (capacity * minLoad);
    }

    /**
     * Chooses a new prime table capacity neither favoring shrinking nor growing,
     * that (approximately) satisfies the invariant
     * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt>
     * and has at least one FREE slot for the given size.
     */
    protected int chooseMeanCapacity(int size, double minLoad, double maxLoad) {
        return nextPrime(Math.max(size+1, (int) ((2*size / (minLoad+maxLoad)))));
    }

    /**
     * Chooses a new prime table capacity optimized for shrinking that
     * (approximately) satisfies the invariant
     * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt>
     * and has at least one FREE slot for the given size.
     */
    protected int chooseShrinkCapacity(int size, double minLoad, double maxLoad) {
        return nextPrime(Math.max(size+1, (int) ((4*size / (minLoad+3*maxLoad)))));
    }

    /**
     * Returns a prime number which is <code>&gt;= desiredCapacity</code> and
     * very close to <code>desiredCapacity</code> (within 11% if
     * <code>desiredCapacity &gt;= 1000</code>).
     *
     * @param desiredCapacity the capacity desired by the user.
     * @return the capacity which should be used for a hashtable.
     */
    protected int nextPrime(int desiredCapacity) {
        int i = java.util.Arrays.binarySearch(primeCapacities, desiredCapacity);
        if (i<0) {
            //desired capacity not found, choose next prime greater than desired
            //capacity
            i = -i -1; // remember the semantics of binarySearch...
        }
        return primeCapacities[i];
    }

    /**
     * The largest prime this class can generate; currently equal to <tt>Integer.MAX_VALUE</tt>.
     */
    public static final int LARGEST_PRIME = Integer.MAX_VALUE; //yes, it is prime.

    /**
     * The prime number list consists of 11 chunks. Each chunk contains prime
     * numbers. A chunk starts with a prime P1. The next element is a prime P2.
     * P2 is the smallest prime for which holds: P2 >= 2*P1. The next element
     * is P3, for which the same holds with respect to P2, and so on.<p>
     *
     * Chunks are chosen such that for any desired capacity >= 1000 the list
     * includes a prime number <= desired capacity * 1.11.* Therefore, primes
     * can be retrieved which are quite close to any desired capacity, which in
     * turn avoids wasting memory. For example, the list includes 1039,1117,
     * 1201,1277,1361,1439,1523,1597,1759,1907,2081. So if you need a
     * prime >= 1040, you will find a prime <= 1040*1.11=1154.<p>
     *
     * Chunks are chosen such that they are optimized for a hashtable
     * growthfactor of 2.0; If your hashtable has such a growthfactor then,
     * after initially "rounding to a prime" upon hashtable construction,
     * it will later expand to prime capacities such that there exist no better
     * primes.<p>
     *
     * In total these are about 32*10=320 numbers -> 1 KB of static memory
     * needed. If you are stingy, then delete every second or fourth chunk.
     */
    private static final int[] primeCapacities = {
        //chunk #0
        LARGEST_PRIME,

        //chunk #1
        5,11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759,
        411527,823117,1646237,3292489,6584983,13169977,26339969,52679969,105359939,
        210719881,421439783,842879579,1685759167,

        //chunk #2
        433,877,1759,3527,7057,14143,28289,56591,113189,226379,452759,905551,1811107,
        3622219,7244441,14488931,28977863,57955739,115911563,231823147,463646329,927292699,
        1854585413,

        //chunk #3
        953,1907,3821,7643,15287,30577,61169,122347,244703,489407,978821,1957651,3915341,
        7830701,15661423,31322867,62645741,125291483,250582987,501165979,1002331963,
        2004663929,

        //chunk #4
        1039,2081,4177,8363,16729,33461,66923,133853,267713,535481,1070981,2141977,4283963,
        8567929,17135863,34271747,68543509,137087021,274174111,548348231,1096696463,

        //chunk #5
        31,67,137,277,557,1117,2237,4481,8963,17929,35863,71741,143483,286973,573953,
        1147921,2295859,4591721,9183457,18366923,36733847,73467739,146935499,293871013,
        587742049,1175484103,

        //chunk #6
        599,1201,2411,4831,9677,19373,38747,77509,155027,310081,620171,1240361,2480729,
        4961459,9922933,19845871,39691759,79383533,158767069,317534141,635068283,1270136683,

        //chunk #7
        311,631,1277,2557,5119,10243,20507,41017,82037,164089,328213,656429,1312867,
        2625761,5251529,10503061,21006137,42012281,84024581,168049163,336098327,672196673,
        1344393353,

        //chunk #8
        3,7,17,37,79,163,331,673,1361,2729,5471,10949,21911,43853,87719,175447,350899,
        701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557,
        359339171,718678369,1437356741,

        //chunk #9
        43,89,179,359,719,1439,2879,5779,11579,23159,46327,92657,185323,370661,741337,
        1482707,2965421,5930887,11861791,23723597,47447201,94894427,189788857,379577741,
        759155483,1518310967,

        //chunk #10
        379,761,1523,3049,6101,12203,24407,48817,97649,195311,390647,781301,1562611,
        3125257,6250537,12501169,25002389,50004791,100009607,200019221,400038451,800076929,
        1600153859
    };

    static { //initializer
        // The above prime numbers are formatted for human readability.
        // To find numbers fast, we sort them once and for all.
        java.util.Arrays.sort(primeCapacities);
    }
}