Int Int Map : Customized Map « Collections Data Structure « Java

Java
1. 2D Graphics GUI
2. 3D
3. Advanced Graphics
4. Ant
5. Apache Common
6. Chart
7. Class
8. Collections Data Structure
9. Data Type
10. Database SQL JDBC
11. Design Pattern
12. Development Class
13. EJB3
14. Email
15. Event
16. File Input Output
17. Game
18. Generics
19. GWT
20. Hibernate
21. I18N
22. J2EE
23. J2ME
24. JDK 6
25. JNDI LDAP
26. JPA
27. JSP
28. JSTL
29. Language Basics
30. Network Protocol
31. PDF RTF
32. Reflection
33. Regular Expressions
34. Scripting
35. Security
36. Servlets
37. Spring
38. Swing Components
39. Swing JFC
40. SWT JFace Eclipse
41. Threads
42. Tiny Application
43. Velocity
44. Web Services SOA
45. XML
Java Tutorial
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 » Collections Data Structure » Customized MapScreenshots 
Int Int Map
    

/* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved.
 
 * This program and the accompanying materials are made available under
 * the terms of the Common Public License v1.0 which accompanies this distribution,
 * and is available at http://www.eclipse.org/legal/cpl-v10.html
 
 * $Id: IntIntMap.java,v 1.1.1.1 2004/05/09 16:57:53 vlad_r Exp $
 */

// ----------------------------------------------------------------------------
/**
 *
 * MT-safety: an instance of this class is <I>not</I> safe for access from
 * multiple concurrent threads [even if access is done by a single thread at a
 * time]. The caller is expected to synchronize externally on an instance [the
 * implementation does not do internal synchronization for the sake of efficiency].
 * java.util.ConcurrentModificationException is not supported either.
 *
 @author Vlad Roubtsov, (C) 2001
 */
public
final class IntIntMap
{
    // public: ................................................................
    
    // TODO: optimize key comparisons using key.hash == entry.key.hash condition

    /**
     * Equivalent to <CODE>IntObjectMap(11, 0.75F)</CODE>.
     */
    public IntIntMap ()
    {
        this (110.75F);
    }
    
    /**
     * Equivalent to <CODE>IntObjectMap(capacity, 0.75F)</CODE>.
     */
    public IntIntMap (final int initialCapacity)
    {
        this (initialCapacity, 0.75F);
    }
    
    /**
     * Constructs an IntObjectMap with specified initial capacity and load factor.
     *
     @param initialCapacity initial number of hash buckets in the table [may not be negative, 0 is equivalent to 1].
     @param loadFactor the load factor to use to determine rehashing points [must be in (0.0, 1.0] range].
     */
    public IntIntMap (int initialCapacity, final float loadFactor)
    {
        if (initialCapacity < 0throw new IllegalArgumentException ("negative input: initialCapacity [" + initialCapacity + "]");
        if ((loadFactor <= 0.0|| (loadFactor >= 1.0 1.0E-6))
            throw new IllegalArgumentException ("loadFactor not in (0.0, 1.0] range: " + loadFactor);
        
        if (initialCapacity == 0initialCapacity = 1;
        
        m_loadFactor = loadFactor > 1.0 1.0F : loadFactor;        
        m_sizeThreshold = (int) (initialCapacity * loadFactor);
        m_buckets = new Entry [initialCapacity];
    }
    
    
    /**
     * Overrides Object.toString() for debug purposes.
     */
    public String toString ()
    {
        final StringBuffer s = new StringBuffer ();
        debugDump (s);
        
        return s.toString ();
    }
    
    /**
     * Returns the number of key-value mappings in this map.
     */
    public int size ()
    {
        return m_size;
    }

    public boolean contains (final int key)
    {
        // index into the corresponding hash bucket:
        final Entry [] buckets = m_buckets;
        final int bucketIndex = (key & 0x7FFFFFFF% buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
        {
            if (key == entry.m_keyreturn true;
        }
        
        return false;
    }
    
    /**
     * Returns the value that is mapped to a given 'key'. Returns
     * false if this key has never been mapped.
     *
     @param key mapping key
     @param out holder for the found value [must be at least of size 1]
     *
     @return 'true' if this key was mapped to an existing value
     */
    public boolean get (final int key, final int [] out)
    {
        // index into the corresponding hash bucket:
        final Entry [] buckets = m_buckets;
        final int bucketIndex = (key & 0x7FFFFFFF% buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
        {
            if (key == entry.m_key)
            {
                out [0= entry.m_value;
                return true;
            }
        }
        
        return false;
    }
    
    public boolean get (final int key, final int [] out, final int index)
    {
        // index into the corresponding hash bucket:
        final Entry [] buckets = m_buckets;
        final int bucketIndex = (key & 0x7FFFFFFF% buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
        {
            if (key == entry.m_key)
            {
                out [index= entry.m_value;
                return true;
            }
        }
        
        return false;
    }
    
    public int [] keys ()
    {
        final int [] result = new int [m_size];
        int scan = 0;
        
        for (int b = 0; b < m_buckets.length; ++ b)
        {
            for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next)
            {
                result [scan ++= entry.m_key;
            }
        }
        
        return result;
    }
    
    /**
     * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
     *
     @param key mapping key
     @param value mapping value
     */
    public void put (final int key, final int value)
    {
        Entry currentKeyEntry = null;
        
        // detect if 'key' is already in the table [in which case, set 'currentKeyEntry' to point to its entry]:
        
        // index into the corresponding hash bucket:
        int bucketIndex = (key & 0x7FFFFFFF% m_buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        Entry [] buckets = m_buckets;
        for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
        {
            if (key == entry.m_key)
            {
                currentKeyEntry = entry;
                break;
            }
        }
        
        if (currentKeyEntry != null)
        {
            // replace the current value:
                
            currentKeyEntry.m_value = value;
        }
        else
        {
            // add a new entry:
            
            if (m_size >= m_sizeThresholdrehash ();
            
            buckets = m_buckets;
            bucketIndex = (key & 0x7FFFFFFF% buckets.length;
            final Entry bucketListHead = buckets [bucketIndex];
            final Entry newEntry = new Entry (key, value, bucketListHead);
            buckets [bucketIndex= newEntry;
            
            ++ m_size;
        }
    }
    
    /**
     * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
     *
     @param key mapping key
     */
    public void remove (final int key)
    {
        // index into the corresponding hash bucket:
        final int bucketIndex = (key  & 0x7FFFFFFF% m_buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        Entry [] buckets = m_buckets;
        for (Entry entry = buckets [bucketIndex], prev = entry; entry != null)
        {
            final Entry next = entry.m_next;
            
            if (key == entry.m_key)
            {
                if (prev == entry)
                    buckets [bucketIndex= next;
                else
                    prev.m_next = next;
                
                -- m_size;     
                break;
            }
            
            prev = entry;
            entry = next;
        }
    }

    
    // protected: .............................................................

    // package: ...............................................................
    
    
    void debugDump (final StringBuffer out)
    {
        if (out != null)
        {
            out.append (super.toString ()); out.append (EOL);
            out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL);
            out.append ("size threshold = " + m_sizeThreshold + EOL);
        }
    }

    // private: ...............................................................

    
    /**
     * The structure used for chaining colliding keys.
     */
    private static final class Entry
    {
        Entry (final int key, final int value, final Entry next)
        {
            m_key = key; 
            m_value = value;
            m_next = next;
        }
        
        int m_key;
        int m_value;
        
        Entry m_next; // singly-linked list link
        
    // end of nested class
    

    /**
     * Re-hashes the table into a new array of buckets.
     */
    private void rehash ()
    {
        // TODO: it is possible to run this method twice, first time using the 2*k+1 prime sequencer for newBucketCount
        // and then with that value reduced to actually shrink capacity. As it is right now, the bucket table can
        // only grow in size
        
        final Entry [] buckets = m_buckets;
        
        final int newBucketCount = (m_buckets.length << 11;
        final Entry [] newBuckets = new Entry [newBucketCount];

        // rehash all entry chains in every bucket:
        for (int b = 0; b < buckets.length; ++ b)
        {
            for (Entry entry = buckets [b]; entry != null)
            {
                final Entry next = entry.m_next; // remember next pointer because we are going to reuse this entry
                final int entryKeyHash = entry.m_key & 0x7FFFFFFF;
            
                // index into the corresponding new hash bucket:
                final int newBucketIndex = entryKeyHash % newBucketCount;
                
                final Entry bucketListHead = newBuckets [newBucketIndex];
                entry.m_next = bucketListHead;
                newBuckets [newBucketIndex= entry;                                
                
                entry = next;
            }
        }
        

        m_sizeThreshold = (int) (newBucketCount * m_loadFactor);
        m_buckets = newBuckets;
    }
    
    
    private final float m_loadFactor; // determines the setting of m_sizeThreshold
    
    private Entry [] m_buckets; // table of buckets
    private int m_size; // number of keys in the table, not cleared as of last check
    private int m_sizeThreshold; // size threshold for rehashing
        
    private static final String EOL = System.getProperty ("line.separator""\n");
    
// end of class
// ----------------------------------------------------------------------------

   
    
    
    
  
Related examples in the same category
1. Ordered Map
2. Case Insensitive Map
3. A Map collection with real-time behavior
4. Cache Map
5. Map implementation Optimized for Strings keys
6. An integer hashmap
7. An IdentityMap that uses reference-equality instead of object-equality
8. Int Object HashMap
9. Concurrent Skip List Map
10. A hash map that uses primitive ints for the key rather than objects.
11. Integer Map
12. Copy On Write Map
13. Expiring Map
14. Array Map
15. Int Object HashMap (from CERN)
16. Int HashMap from jodd.org
17. String Map
18. List Map
19. Map using Locale objects as keys
20. Map with keys iterated in insertion order
21. Most Recently Used Map
22. Multi Map
23. MultiMap is a Java version of the C++ STL class std::multimap
24. Object Int Map
25. Sequenced HashMap
26. Int Object Map
27. Identity HashMap
28. A java.util.Map interface which can only hold a single object
29. A multi valued Map
30. A simple hashmap from keys to integers
31. A memory-efficient hash map.
32. An implementation of the java.util.Map interface which can only hold a single object.
33. Utility methods for operating on memory-efficient maps.
34. CaseBlindHashMap - a HashMap extension, using Strings as key values.
35. A fixed size map implementation.
36. Int HashMap
37. IntMap provides a simple hashmap from keys to integers
38. Complex Key HashMap
39. A Map with multiple values for a key
40. A Map that accepts int or Integer keys only
41. A Map where keys are compared by object identity, rather than equals()
42. Type-safe Map, from char array to String value
43. A hashtable-based Map implementation with soft keys
44. List ordered map
45. Hash map using String values as keys mapped to primitive int values.
46. Lookup table that stores a list of strings
47. 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.
48. Combines multiple values to form a single composite key. MultiKey can often be used as an alternative to nested maps.
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.