Hash map using String values as keys mapped to primitive int values. : Customized Map « Collections « Java Tutorial

Java Tutorial
1. Language
2. Data Type
3. Operators
4. Statement Control
5. Class Definition
6. Development
7. Reflection
8. Regular Expressions
9. Collections
10. Thread
11. File
12. Generics
13. I18N
14. Swing
15. Swing Event
16. 2D Graphics
17. SWT
18. SWT 2D Graphics
19. Network
20. Database
21. Hibernate
22. JPA
23. JSP
24. JSTL
25. Servlet
26. Web Services SOA
27. EJB3
28. Spring
29. PDF
30. Email
31. J2ME
32. J2EE Application
33. XML
34. Design Pattern
35. Log
36. Security
37. Apache Common
38. Ant
39. JUnit
Java
Java Source Code / Java Documentation
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 Tutorial » Collections » Customized Map 
9. 33. 17. Hash map using String values as keys mapped to primitive int values.
/*
 * Copyright (c) 2000-2005, Dennis M. Sosnoski. All rights reserved.
 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer. Redistributions in binary
 * form must reproduce the above copyright notice, this list of conditions and
 * the following disclaimer in the documentation and/or other materials provided
 * with the distribution. Neither the name of JiBX nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */


/**
 * Hash map using <code>String</code> values as keys mapped to primitive
 * <code>int</code> values. This implementation is unsynchronized in order to
 * provide the best possible performance for typical usage scenarios, so
 * explicit synchronization must be implemented by a wrapper class or directly
 * by the application in cases where instances are modified in a multithreaded
 * environment. The map implementation is not very efficient when resizing, but
 * works well when the size of the map is known in advance.
 
 @author Dennis M. Sosnoski
 @version 1.1
 */
public class StringIntHashMap
{
    /** Default value returned when key not found in table. */
    public static final int DEFAULT_NOT_FOUND = Integer.MIN_VALUE;

    /** Default fill fraction allowed before growing table. */
    protected static final double DEFAULT_FILL = 0.3d;

    /** Minimum size used for hash table. */
    protected static final int MINIMUM_SIZE = 31;

    /** Fill fraction allowed for this hash table. */
    protected final double m_fillFraction;

    /** Number of entries present in table. */
    protected int m_entryCount;

    /** Entries allowed before growing table. */
    protected int m_entryLimit;

    /** Size of array used for keys. */
    protected int m_arraySize;

    /** Offset added (modulo table size) to slot number on collision. */
    protected int m_hitOffset;

    /** Array of key table slots. */
    protected String[] m_keyTable;

    /** Array of value table slots. */
    protected int[] m_valueTable;

    /** Value returned when key not found in table. */
    protected int m_notFoundValue;

    /**
     * Constructor with full specification.
     
     @param count number of values to assume in initial sizing of table
     @param fill fraction full allowed for table before growing
     @param miss value returned when key not found in table
     */
    public StringIntHashMap(int count, double fill, int miss) {

        // check the passed in fill fraction
        if (fill <= 0.0d || fill >= 1.0d) {
            throw new IllegalArgumentException("fill value out of range");
        }
        m_fillFraction = fill;

        // compute initial table size (ensuring odd)
        m_arraySize = Math.max((int)(count / m_fillFraction), MINIMUM_SIZE);
        m_arraySize += (m_arraySize + 12;

        // initialize the table information
        m_entryLimit = (int)(m_arraySize * m_fillFraction);
        m_hitOffset = m_arraySize / 2;
        m_keyTable = new String[m_arraySize];
        m_valueTable = new int[m_arraySize];
        m_notFoundValue = miss;
    }

    /**
     * Constructor with size and fill fraction specified. Uses default hash
     * technique and value returned when key not found in table.
     
     @param count number of values to assume in initial sizing of table
     @param fill fraction full allowed for table before growing
     */
    public StringIntHashMap(int count, double fill) {
        this(count, fill, DEFAULT_NOT_FOUND);
    }

    /**
     * Constructor with only size supplied. Uses default hash technique and
     * values for fill fraction and value returned when key not found in table.
     
     @param count number of values to assume in initial sizing of table
     */
    public StringIntHashMap(int count) {
        this(count, DEFAULT_FILL);
    }

    /**
     * Default constructor.
     */
    public StringIntHashMap() {
        this(0, DEFAULT_FILL);
    }

    /**
     * Copy (clone) constructor.
     
     @param base instance being copied
     */
    public StringIntHashMap(StringIntHashMap base) {

        // copy the basic occupancy information
        m_fillFraction = base.m_fillFraction;
        m_entryCount = base.m_entryCount;
        m_entryLimit = base.m_entryLimit;
        m_arraySize = base.m_arraySize;
        m_hitOffset = base.m_hitOffset;
        m_notFoundValue = base.m_notFoundValue;

        // copy table of items
        m_keyTable = new String[m_arraySize];
        System.arraycopy(base.m_keyTable, 0, m_keyTable, 0, m_arraySize);
        m_valueTable = new int[m_arraySize];
        System.arraycopy(base.m_valueTable, 0, m_valueTable, 0, m_arraySize);
    }

    /**
     * Step the slot number for an entry. Adds the collision offset (modulo
     * the table size) to the slot number.
     *
     @param slot slot number to be stepped
     @return stepped slot number
     */
    private final int stepSlot(int slot) {
        return (slot + m_hitOffset% m_arraySize;
    }

    /**
     * Find free slot number for entry. Starts at the slot based directly
     * on the hashed key value. If this slot is already occupied, it adds
     * the collision offset (modulo the table size) to the slot number and
     * checks that slot, repeating until an unused slot is found.
     *
     @param slot initial slot computed from key
     @return slot at which entry was added
     */
    private final int freeSlot(int slot) {
        while (m_keyTable[slot!= null) {
            slot = stepSlot(slot);
        }
        return slot;
    }

    /**
     * Standard base slot computation for a key.
     *
     @param key key value to be computed
     @return base slot for key
     */
    private final int standardSlot(Object key) {
        return (key.hashCode() & Integer.MAX_VALUE% m_arraySize;
    }

    /**
     * Standard find key in table. This method may be used directly for key
     * lookup using either the <code>hashCode()</code> method defined for the
     * key objects or the <code>System.identityHashCode()</code> method, and
     * either the <code>equals()</code> method defined for the key objects or
     * the <code>==</code> operator, as selected by the hash technique
     * constructor parameter. To implement a hash class based on some other
     * methods of hashing and/or equality testing, define a separate method in
     * the subclass with a different name and use that method instead. This
     * avoids the overhead caused by overrides of a very heavily used method.
     *
     @param key to be found in table
     @return index of matching key, or <code>-index-1</code> of slot to be
     * used for inserting key in table if not already present (always negative)
     */
    private int standardFind(Object key) {

        // find the starting point for searching table
        int slot = standardSlot(key);

        // scan through table to find target key
        while (m_keyTable[slot!= null) {

            // check if we have a match on target key
            if (m_keyTable[slot].equals(key)) {
                return slot;
            else {
                slot = stepSlot(slot);
            }

        }
        return -slot-1;
    }

    /**
     * Reinsert an entry into the hash map. This is used when the table is being
     * directly modified, and does not adjust the count present or check the
     * table capacity.
     
     @param slot position of entry to be reinserted into hash map
     @return <code>true</code> if the slot number used by the entry has has
     * changed, <code>false</code> if not
     */
    private boolean reinsert(int slot) {
        String key = m_keyTable[slot];
        m_keyTable[slotnull;
        return assignSlot(key, m_valueTable[slot]) != slot;
    }

    /**
     * Internal remove pair from the table. Removes the pair from the table
     * by setting the key entry to <code>null</code> and adjusting the count
     * present, then chains through the table to reinsert any other pairs
     * which may have collided with the removed pair. If the associated value
     * is an object reference, it should be set to <code>null</code> before
     * this method is called.
     *
     @param slot index number of pair to be removed
     */
    protected void internalRemove(int slot) {

        // delete pair from table
        m_keyTable[slotnull;
        m_entryCount--;
        while (m_keyTable[(slot = stepSlot(slot))] != null) {

            // reinsert current entry in table to fill holes
            reinsert(slot);

        }
    }

    /**
     * Restructure the table. This is used when the table is increasing or
     * decreasing in size, and works directly with the old table representation
     * arrays. It inserts pairs from the old arrays directly into the table
     * without adjusting the count present or checking the table size.
     
     @param keys array of keys
     @param values array of values
     */
    private void restructure(String[] keys, int[] values) {
        for (int i = 0; i < keys.length; i++) {
            if (keys[i!= null) {
                assignSlot(keys[i], values[i]);
            }
        }
    }

    /**
     * Assign slot for entry. Starts at the slot found by the hashed key value.
     * If this slot is already occupied, it steps the slot number and checks the
     * resulting slot, repeating until an unused slot is found. This method does
     * not check for duplicate keys, so it should only be used for internal
     * reordering of the tables.
     
     @param key to be added to table
     @param value associated value for key
     @return slot at which entry was added
     */
    private int assignSlot(String key, int value) {
        int offset = freeSlot(standardSlot(key));
        m_keyTable[offset= key;
        m_valueTable[offset= value;
        return offset;
    }

    /**
     * Add an entry to the table. If the key is already present in the table,
     * this replaces the existing value associated with the key.
     
     @param key key to be added to table (non- <code>null</code>)
     @param value associated value for key
     @return value previously associated with key, or reserved not found value
     * if key not previously present in table
     */
    public int add(String key, int value) {

        // first validate the parameters
        if (key == null) {
            throw new IllegalArgumentException("null key not supported");
        else if (value == m_notFoundValue) {
            throw new IllegalArgumentException(
                "value matching not found return not supported");
        else {

            // check space available
            int min = m_entryCount + 1;
            if (min > m_entryLimit) {
                
                // find the array size required
                int size = m_arraySize;
                int limit = m_entryLimit;
                while (limit < min) {
                    size = size * 1;
                    limit = (int) (size * m_fillFraction);
                }
            
                // set parameters for new array size
                m_arraySize = size;
                m_entryLimit = limit;
                m_hitOffset = size / 2;
                
                // restructure for larger arrays
                String[] keys = m_keyTable;
                m_keyTable = new String[m_arraySize];
                int[] values = m_valueTable;
                m_valueTable = new int[m_arraySize];
                restructure(keys, values);
            }
            
            // find slot of table
            int offset = standardFind(key);
            if (offset >= 0) {

                // replace existing value for key
                int prior = m_valueTable[offset];
                m_valueTable[offset= value;
                return prior;

            else {

                // add new pair to table
                m_entryCount++;
                offset = -offset - 1;
                m_keyTable[offset= key;
                m_valueTable[offset= value;
                return m_notFoundValue;

            }
        }
    }

    /**
     * Check if an entry is present in the table. This method is supplied to
     * support the use of values matching the reserved not found value.
     
     @param key key for entry to be found
     @return <code>true</code> if key found in table, <code>false</code>
     * if not
     */
    public final boolean containsKey(String key) {
        return standardFind(key>= 0;
    }

    /**
     * Find an entry in the table.
     
     @param key key for entry to be returned
     @return value for key, or reserved not found value if key not found
     */
    public final int get(String key) {
        int slot = standardFind(key);
        if (slot >= 0) {
            return m_valueTable[slot];
        else {
            return m_notFoundValue;
        }
    }

    /**
     * Remove an entry from the table. If multiple entries are present with the
     * same key value, only the first one found will be removed.
     
     @param key key to be removed from table
     @return value associated with removed key, or reserved not found value if
     * key not found in table
     */
    public int remove(String key) {
        int slot = standardFind(key);
        if (slot >= 0) {
            int value = m_valueTable[slot];
            internalRemove(slot);
            return value;
        else {
            return m_notFoundValue;
        }
    }

    /**
     * Construct a copy of the table.
     
     @return shallow copy of table
     */
    public Object clone() {
        return new StringIntHashMap(this);
    }
}
9. 33. Customized Map
9. 33. 1. Implementation of a bit map of any size, together with static methods to manipulate int, byte and byte[] values as bit maps
9. 33. 2. A fixed size map implementation.
9. 33. 3. A memory-efficient hash map.
9. 33. 4. CaseBlindHashMap - a HashMap extension, using Strings as key values.
9. 33. 5. Clones a map and prefixes the keys in the clone
9. 33. 6. Converts array into a java.util.Map.
9. 33. 7. Ordered Map
9. 33. 8. A hash map that uses primitive ints for the key rather than objects.
9. 33. 9. HashNMap stores multiple values by a single key value. Values can be retrieved using a direct query or by creating an enumeration over the stored elements.
9. 33. 10. A Map where keys are compared by object identity, rather than equals()
9. 33. 11. A java.util.Map implementation using reference values
9. 33. 12. A simple hashmap from keys to integers
9. 33. 13. An IdentityMap that uses reference-equality instead of object-equality
9. 33. 14. Creates a mutable map from two arrays with keys and values
9. 33. 15. Fixed size hash map using String values as keys mapped to primitive int values.
9. 33. 16. Hash map for counting references to Object keys.
9. 33. 17. Hash map using String values as keys mapped to primitive int values.
9. 33. 18. IntMap provides a simple hashmap from keys to integers
9. 33. 19. List ordered map
9. 33. 20. Lookup table that stores a list of strings
9. 33. 21. Map implementation Optimized for Strings keys
9. 33. 22. Map with keys iterated in insertion order
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.