Map篇

一、Map接口

Map接口主要的方法有：

方法名	参数	返回类型	功能
size		int	获取长度
isEmpty		boolean	是否为空
containsKey		boolean	是否包含 key
containsValue		boolean	是否包含value
get	K	V	根据Key返回Value
put	K,V	V	存放键值对
remove	K	V	将key对应的键值对删除，并返回Value
putAll	Map<? extends K,? extends V>		将另一个Map放入当前Map中
clear		清空
keySet		Set<K>	返回Key的Set集合
values		Collection<V>	返回Value的Collection集合
entrySet		Set<Map.Entry<K, V>>	以Set的形式返回所有Entry
equals	Object	boolean	重写Object方法
hashCode		int	重写Object方法

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

方法名	参数	返回类型	功能
getOrDefault	Object	V	default实现的方法，V为空且不包含当前key时，返回默认值
forEach	BiConsumer<? super K, ? super V>	void	for循环执行BiConsumer的accept方法
replaceAll	BiFunction<? super K, ? super V, ? extends V> function		通过BiFunction方法，接受K,V并返回新一个新的V，替换原来的Value
putIfAbsent	K key, V value	V	如果get(K)返回null，则执行put方法
remove	K,V	boolean	如果当前Value和传入Value相等，或当前Value不为null或包含当前Key,则执行remove(K)方法
replace	K,OldV,NewV	boolean	与上一方法雷同，只是最终执行put方法
replace	K,V	当前有V或K存在时执行put
computeIfAbsent	K,Function	V	若当前V为null，则执行计算方法，put(K,NewV)
computeIfPresent	K,BiFunction	V	同上
compute	K，BiFunction	V	直接计算原K，V，替换V
merge	K,V,BiFunction	V	计算新老V，替换当前V

二、主要实现类

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除了以数组、链表的形式存储数据外，还以红黑树的形式对列表进行了优化。
以下是几个重要的参数：

字段	类型	默认值	释义
DEFAULT_INITIAL_CAPACITY	int	16	默认的初始大小
MAXIMUM_CAPACITY	int	1<<30	最大容量
DEFAULT_LOAD_FACTOR	float	0.75f	默认负载因子
TREEIFY_THRESHOLD	int	8	单链表转换为红黑树的阀值
UNTREEIFY_THRESHOLD	int	6	红黑树还原为单链表的阀值
MIN_TREEIFY_CAPACITY	int	64	最小转换为红黑树的阀值，这里需要说明：只有当容量超过这个阀值的时候，且满足红黑树转化繁殖，才会将链表转为红黑树，否则只会进行扩容操作。所以由以上默认值可知，只有当HashMap容量为128以上，扩容阀值在96以上时，才会有红黑树出现。

执行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