HashMap

map共同特点:unique key。如果同一key有不同value,取后者
HashMap:not synchronized. no order。 permits null values and the null key
HashTable: synchronized. Supporting full concurrency of retrievals and adjustable expected concurrency for updates.
ConcurrentHashMap: no block on reading. concurrency among update operations is guided by the optional concurrencyLevel constructor argument (default 16).
TreeMap:implemented based on red-black tree structure, and it is ordered by the key.
LinkedHashMap: ordered by insertion order

Very Good Explanation. http://www.programcreek.com/2013/03/hashmap-vs-treemap-vs-hashtable-vs-linkedhashmap/

HashMap Implementation

package algorithms.hashmap;
 
 
public class TMHashMap {
    // for simplicity size is taken as 2^4
    private static final int SIZE = 16;
    private Entry table[] = new Entry[SIZE];
 
    /**
     * User defined simple Map data structure
     * with key and value.
     * This is also used as linked list in case multiple
     * key-value pairs lead to the same bucket with same
     * hashcodes and different keys (collisions) using
     * pointer 'next'.
     *
     * @author ntallapa
     */
    class Entry {
        final String key;
        String value;
        Entry next;
 
        Entry(String k, String v) {
            key = k;
            value = v;
        }
 
        public String getValue() {
            return value;
        }
 
        public void setValue(String value) {
            this.value = value;
        }
 
        public String getKey() {
            return key;
        }
    }
 
    /**
     * Returns the entry associated with the specified key in the
     * HashMap.  Returns null if the HashMap contains no mapping
     * for the key.
     */
    public Entry get(String k) {
        int hash = k.hashCode() % SIZE;
        Entry e = table[hash];
 
        // if bucket is found then traverse through the linked list and
        // see if element is present
        while(e != null) {
            if(e.key.equals(k)) {
                return e;
            }
            e = e.next;
        }
        return null;
    }
 
    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     */
    public void put(String k, String v) {
        int hash = k.hashCode() % SIZE;
        Entry e = table[hash];
        if(e != null) {
            // it means we are trying to insert duplicate
            // key-value pair, hence overwrite the current
            // pair with the old pair
            if(e.key.equals(k)) {
                e.value = v;
            } else {
                // traverse to the end of the list and insert new element 
                // in the same bucket
                while(e.next != null) {
                    e = e.next;
                }
                Entry entryInOldBucket = new Entry(k, v);
                e.next = entryInOldBucket;
            }
        } else {
            // new element in the map, hence creating new bucket
            Entry entryInNewBucket = new Entry(k, v);
            table[hash] = entryInNewBucket;
        }
    }
 
    // for testing our own map
    public static void main(String[] args) {
        TMHashMap tmhm = new TMHashMap();
 
        tmhm.put("student1", "SMTS");
        tmhm.put("student2", "SSE");
        tmhm.put("student3", "SMTS1");
        tmhm.put("student3", "SSE");
 
        Entry e = tmhm.get("student3");
        System.out.println(""+e.getValue());
    }
}

reference: http://tekmarathon.com/2013/03/11/creating-our-own-hashmap-in-java/

Advertisements
HashMap

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s