Notes on Java, Solaris, PHP, LDAP…

Map Example

import java.util.Map;

import java.util.Map.Entry;

import java.util.HashMap; /** It doesn't implement java.util.Map because that's not the important part for what

    this examples intends to show. To keep it simple, it's quite an inefficient map

    - no hashing.

*/

public class MapExample

{

    /**    This is set and populated only by MapExample( Map original ) - otherwise it's null.

        It is not modified once MapExample( Map original ) returns - then it's accessed read-only.

        It's used only while mutableArray is null. Once mutableArray is set it's used instead of initialArray.

        It's protected by Direct Component Guarantee. To be 100% JMM-compliant, the actual Map.Entry

        items must be final objects - because Direct Component Guarantee doesn't apply recursively deep.

        If used then it contains all initial entries of the map, and only those entries. I.e. map's size is same

        as initialArray.length.

    */

    private final Map.Entry initialArray[];

    /** It contains all entries of the map

        - once the instance was modified after it was constructed by MapExample( Map original ).

        - if the instance was initialized by constructor other than MapExample( Map original ).

        In both cases all threads must synchronize when using the instance - both read and write.

        If non-null it contains all current entries of the map starting from index 0 up to mutableSize-1. The rest of the array is ignored

        - that's where new entries are added, unless the array needs to be resized.

    */

    private Map.Entry mutableArray[];

    /** If mutableArray is non-null then mutableSize is the number of valid entries that are

        currently stored in mutableArray. mutableSize is always equal or lower than mutableArray.lenght.

    */

    private int mutableSize;

    public MapExample() { this(16); }

    public MapExample( int initialCapacity ) {

        initialArray= null;

        mutableArray= new Map.Entry[initialCapacity];

        mutableSize= 0;

    }

    /** To be 100% JMM-compliant, both the key and *value* must be final fields when used for initial

        unsynchronized entries in initialArray[]. Otherwise other threads could see key/value as null :(

        Since there's no public Java 6 for Mac OS X, I can't use java.util.AbstractMap.SimpleImmutableEntry

    */

    private static final class Entry implements Map.Entry {

        private final KT key;

        private final VT value;

        public KT getKey() { return key; }

        public VT getValue() { return value; }

        public VT setValue(VT newValue) { throw new Error( "Never to be used." ); }

        public boolean equals( Object o ) { throw new Error("TODO"); }

        public int hashCode() { throw new Error("TODO"); }

        Entry( KT givenKey, VT givenValue ) {

            key= givenKey;

            value= givenValue;

        }

    }

    public MapExample( Map original ) {

        initialArray= new Map.Entry[ original.size() ];

        int index= 0;

        for( Map.Entry entry:original.entrySet() ) {

            initialArray[ index ]= new Entry( (K)entry.getKey(), (V)entry.getValue() );

            index++;

        }

    }

private boolean usingMutableArray() { return mutableArray!=null; }

private Map.Entry[] currentActiveArray() { return usingMutableArray() ? mutableArray : initialArray; }

public int size() { return usingMutableArray() ? mutableSize : initialArray.length; }

private static boolean keysEqual( Object first, Object second ) {

        return first!=null && first.equals( second ) || first==second;

}

public V get( K key ) {

        // Efficiency is not important in this example

        for( int i=0; i< size(); i++ ) {

            Map.Entry entry= currentActiveArray()[ i ];

            if( keysEqual( key, entry.getKey() ) ) {

                return (V)entry.getValue();

            }

        }

        return null;

    }

    /** This doesn't return the previous value as Map.put(K,V) does.

    */

    public void put( K givenKey, V givenValue ) {

        // Efficiency is a foreign word here :)

        if( !usingMutableArray() || size()==mutableArray.length ) {

            /** Following should only resize if we need a new slot - not when replacing an existing value.

                And if !usingMutableArray() and changing the instance for the first time

                and if there's no need for a new slot, then it could just assign mutableArray= initialArray

                rather than creating a new array.

                It could also round the new size of mutableArray

                to the nearest higher power of 2. But it doesn't matter in this example.

            */

            Map.Entry newArray[]= new Map.Entry[ size()+1 ];

            /** Since we use immutable instances of class Entry in both initialArray[] and mutableArray[],

                we don't need to clone the actual entries here. It would be nice to type initialArray and mutableArray

                as arrays of MapExample.Entry rather than Map.Entry, but it doesn't matter.

            */

            System.arraycopy( currentActiveArray(), 0, newArray, 0, size() );

            if( !usingMutableArray() ) {

                // Here we initialize mutableSize to non-zero value for the first time

                assert mutableSize==0;

                mutableSize= size(); // We didn't put (newKey, newValue) yet

            }

            mutableArray= newArray;

        }

        assert usingMutableArray();

        for( int i=0; i< size(); i++ ) {

            Map.Entry entry= currentActiveArray()[ i ];

            if( keysEqual( givenKey, entry.getKey() ) ) {

                entry.setValue( givenValue );

                return; // replaced an existing value, done

            }

        }

        mutableArray[ mutableSize ]= new Entry( givenKey, givenValue );

        mutableSize++;

        assert mutableSize<=mutableArray.length;

    }

public static void main( String... argv ) {

        HashMap map= new HashMap();

        map.put( "1", "One" );

        map.put( "2", "Two" );

        MapExample initialized= new MapExample( map );

        assert initialized.size()==2;

        assert initialized.get( "1" ).equals( "One" );

        assert initialized.get( "2" ).equals( "Two" );

        /** If the code guaranteed that initialized doesn't ever get modified after it

            was constructed, it could be used in other threads without any synchronization action.

            Otherwise it must be synchronized if used by several threads.

        */

        initialized.put( "3", "Three" );

        assert initialized.size()==3;

        assert initialized.get( "3" ).equals( "Three" );

        MapExample modified= new MapExample( 2 ); // 2 is so that we can test resize easily

        modified.put( "1", "One" );

        modified.put( "2", "Two" );

        modified.put( "3", "Three" );

        modified.put( "4", "Four" );

        modified.put( "5", "Five" );

        assert modified.size()==5;

        assert modified.get( "1" ).equals( "One" );

        assert modified.get( "2" ).equals( "Two" );

        assert modified.get( "3" ).equals( "Three" );

        assert modified.get( "4" ).equals( "Four" );

        assert modified.get( "5" ).equals( "Five" );

}

}

4 Comments »

  1. I’ve been exploring for a little bit for any high-quality articles or blog posts on this sort of space . Exploring in Yahoo I finally stumbled upon this website. Reading this information So i’m satisfied to express that
    I have a very good uncanny feeling I discovered exactly what I needed.
    I most for sure will make certain to do not disregard this web site
    and give it a look regularly.

    Comment by katalog www — March 31, 2013 @ 6:44 pm | Reply

  2. This is very fascinating, You’re an overly skilled blogger. I have joined your rss feed and stay up for searching for more of your magnificent post. Also, I have shared your site in my social networks

    Comment by wiersze smutne — April 24, 2013 @ 10:32 pm | Reply

  3. This will be a fantastic site, will you be interested in doing an interview regarding just how you designed it? If so email me! ecdegefbddde

    Comment by Johnc880 — July 24, 2014 @ 3:55 am | Reply

  4. Please let me know if you’re looking for a article author for your weblog.
    You have some really good articles and I believe I would be a good asset.
    If you ever want to take some of the load off, I’d absolutely
    love to write some articles for your blog in exchange for a link back to mine.
    Please blast me an e-mail if interested. Many thanks!

    Comment by coat hanger — October 25, 2016 @ 6:55 pm | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: