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/