一、Map接口

Map接口主要的方法有：

还有一些默认实现的方法：

二、主要实现类

1. HashMap
2. HashTable
3. ConcurrentHashMap

HashMap的实现

Java 7 中：
HashMap主要以数组的形式存放Entry，每个Entry是一个单向链表结构，存储了下一个键值对Entry<K,V> next，HashMap有几个重要的属性：

1. capacity 容量
2. loadFactor 负载因子
3. threshold 扩容阀值

这几个属性涉及到了HashMap的扩容操作，即loadFactor为基本的负载因子，loadFactor*capacity=threshold，即当size>=threshoold，或者size/capacity>=loadFactory，且数组每个槽都至少有一个Entry的时候，HashMap会进行扩容操作。

Java 8 中：
HashMap除了以数组、链表的形式存储数据外，还以红黑树的形式对列表进行了优化。
以下是几个重要的参数：

执行put操作的时候，流程图如下图所示：

20161126224434590 .jpg

Q1:什么是红黑树？
答：http://www.jianshu.com/p/b71eab42db06

Q2:HashMap如何实现红黑树的？
答：通过TreeNode类

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}
//同时，由于LinkedHashMap.Entry<K,V>继承了Node<K,V>，所以TreeNode还具有以下属性
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

Q3:HashMap的扩容过程是怎样的？
答：

HashTable 的线程安全

HashTable使用数组加链表的方式实现，与HashMap 1.7中的实现十分类似，但通过同步锁，牺牲性能，实现了线程安全，如putfangfa :

 public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

ConcurrentHashMap 的实现

Java 7 中：
以Segment的形式存储数据，相当于一个HashTable的数组，通过针对每个Segment上锁，实现了并发的写操作，默认数组大小为16，即理想状态下对HashTable的性能提升为16倍。

Java 8 中：
摒弃Segment的概念，改为以Node的节点的形式存储。
同时大量使用CAS来实现类似乐观锁的操作，保证线程安全。

Q2: ConcurrentHashMap操作的线程安全如何保证？
答：通过以下原子操作：

@SuppressWarnings("unchecked")
    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

参考链接：
http://blog.csdn.net/u011240877/article/details/53358305
http://www.jianshu.com/p/e694f1e868ec