Map

1	public interface Map<K,V>

框架：

AbstractMap

1	public abstract class AbstractMap<K,V> implements Map<K,V>

唯一抽象方法

1	public abstract Set<Entry<K,V>> entrySet();

不可变，需要重写put()方法

1
2
3

public V put(K key, V value) {
    throw new UnsupportedOperationException();
}

成员变量

1 2	transient volatile Set<K> keySet; //1.8 去除volatile transient volatile Collection<V> values;

hashCode() 值为每个entry的hash和
equals()

同一个对象？—> 是否Map？—> 长度一样？—> 遍历每个entry的key和value

内部类
SimpleEntry 与 SimpleImmutableEntry唯一的区别就是支持 setValue() 操作。

HashMap

1 2	public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

数据结构

允许空键，空值
负载因子 0.75
初始长度 1 << 4
数组最大长度 1 << 30
非线程安全使用Collections.synchronizedMap()包装
fail-fast机制。iterator迭代更改map结构会抛出 ConcurrentModificationException，通过iterator.remove()删除元素
jdk8 使用红黑树来优化元素均匀分布
1. TREEIFY_THRESHOLD = 8 一个桶的树化阈值，当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点
2. UNTREEIFY_THRESHOLD = 6 一个树的链表还原阈值，桶中元素个数小于这个值，就会把树形的桶元素还原（切分）为链表结构
3. int MIN_TREEIFY_CAPACITY = 64 哈希表的最小树形化容量，这个值不能小于 4 * TREEIFY_THRESHOLD
链表节点：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;  
    final K key;
    V value;
    Node<K,V> next; //指向下一个节点的指针
}

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;
    Entry<K,V> before, after;	 //LinkedHashMap.Entry<K,V>

    final int hash;			//HashMap.Node<K,V>
    final K key;
    V value;
    Node<K,V> next;
}

源码分析

hash计算

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//兼顾高低位, 优化hash值位置冲突
}

当hash数组的长度为 2^n 时, table.length -1 后, 最低的 n-1 位全部为1, 说明hash值存放的位置由hash值的低 n-1 位决定. 而HashMap计算hash值时, 同时兼顾了hash值的高位与低位.

get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {  //first指向hash值对应数组位置中的Node节点
        if (first.hash == hash && // 如果first节点对应的hash和key的hash相等(在数组相同位置,只是说明 hash&(n-1) 操作结果相等, 说明hash值的部分低位相等, 并不代表整个hash值相等), 并且first对应的key也相等的话, first节点就是要查找的
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {  //说明存在hash冲突
            if (first instanceof TreeNode)  //说明由红黑树对hash值冲突进行管理
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);  //查找红黑树
            do {  //说明hash值冲突是由链表进行管理
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);  //对链表进行遍历
        }
    }
    return null;
}

步骤：

(length - 1) & hash 做hash找出bucket位置
首节点hash和key与所找的相同，返回首节点
equals() 比较key
jdk8 会先做treeNode 节点类型判断

put方法

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

JDK7中先扩容再插入，插入时插入链表首节点；而JDK8先插入值再扩容，插入时插在链表尾部

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;  //当数组table为null时, 调用resize生成数组table, 并令tab指向数组table
    if ((p = tab[i = (n - 1) & hash]) == null)  //如果新存放的hash值没有冲突
        tab[i] = newNode(hash, key, value, null);  //则只需要生成新的Node节点并存放到table数组中即可
    else {  //否则就是产生了hash冲突
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k)))) 
            e = p;  //如果hash值相等且key值相等, 则令e指向冲突的头节点
        else if (p instanceof TreeNode)  //如果头节点的key值与新插入的key值不等, 并且头结点是TreeNode类型,说明该hash值冲突是采用红黑树进行处理.
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  //向红黑树中插入新的Node节点
        else {  //否则就是采用链表处理hash值冲突
            for (int binCount = 0; ; ++binCount) {  //遍历冲突链表, binCount记录hash值冲突链表中节点个数
                if ((e = p.next) == null) {  //当遍历到冲突链表的尾部时
                    p.next = newNode(hash, key, value, null);  //生成新节点添加到链表末尾
                    if (binCount >= TREEIFY_THRESHOLD - 1) //如果binCount即冲突节点的个数大于等于 (TREEIFY_THRESHOLD(=8) - 1),便将冲突链表改为红黑树结构, 对冲突进行管理, 否则不需要改为红黑树结构
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))  //如果在冲突链表中找到相同key值的节点, 则直接用新的value覆盖原来的value值即可
                    break;
                p = e;
            }
        }
        if (e != null) { // 说明原来已经存在相同key的键值对
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)  //onlyIfAbsent为true表示仅当<key,value>不存在时进行插入, 为false表示强制覆盖;
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;  //修改次数自增
    if (++size > threshold) //当键值对数量size达到临界值threhold后, 需要进行扩容操作.
        resize();
    afterNodeInsertion(evict);
    return null;
}

步骤：

空表进行resize()
hash 对应位置没有发生碰撞，直接插入
发生碰撞，链表节点将遍历节点，插入最后，超过TREEIFY_THRESHOLD，转为树形结构
TreeNode, 红黑树找到父节点，进行插入
如果节点已经存在，进行替换
超过负载因子，进行resize()

冲突链表改为红黑树

//该方法的主要作用是将冲突链表改为红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  //当数组的长度< MIN_TREEIFY_CAPACITY(64) 时,只是单纯将数组扩容, 而没有直接将链表改为红黑树. 因为hash数组长度还太小时导致多冲突的主要原因, 增大hash数组长度可以改善冲突情况
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

resize方法

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;  //oldTab变量指向原来的数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;  //oldThr变量保存原来数组的临界值
    int newCap, newThr = 0;
    if (oldCap > 0) {   //说明将要进行扩容操作
        if (oldCap >= MAXIMUM_CAPACITY) {  //由于最大容量不能超过 MAXMUM_CAPACITY, 当原来数组的容量达到这个值后不能再进行扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
                 oldCap >= DEFAULT_INITIAL_CAPACITY)  // 进行两倍扩容
            newThr = oldThr << 1; 
    }
    else if (oldThr > 0) // oldCap=0, 说明原来的table数组为null, 对应使用 new HashMap(int initialCapacity) 初始化后，第一次 put 的时候
        newCap = oldThr;   // 新创建的容器容量为原来容器中设定的临界值
    else {     // 对应使用 new HashMap() 初始化后，第一次 put 的时候
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor; //新容器的临界值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  //创建新容量的数组
    table = newTab; 
    if (oldTab != null) {  //如果原来的数组中存在值, 需要将原来数组中的值保存到新数组中
        for (int j = 0; j < oldCap; ++j) {  //遍历原来的数组
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {  //如果原来数组位置中的值不为null, 则需要进行转移
                oldTab[j] = null;   //置为null, 方便进行GC
                if (e.next == null)   //说明原来数组中保存的hash值是没有冲突的, 也就是Node类型变量
                    newTab[e.hash & (newCap - 1)] = e;  //将e的hash值和(newCap-1)进行与操作, 从而获取在新数组中的位置
                else if (e instanceof TreeNode)  // 说明原来数组中保存的hash值存在冲突, 是红黑树 TreeNode 类型变量, 采用红黑树管理冲突的键值对
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 这说明原来数组中保存的hash值存在冲突, 但是并没有采用红黑树对冲突的Hash值进行管理, 而是采用Node链表进行管理
                    Node<K,V> loHead = null, loTail = null;//低位指针，hash & oldCap == 0
                    Node<K,V> hiHead = null, hiTail = null;//高位指针，hash & oldCap == 1
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //因为需要根据冲突链表中的hash值存放到新数组中,而新数组的长度是原数组长度的2倍, newTable.length-1 比 oldTable.length-1 多oldCap, 因此 hash&(newTable.length-1) 等价于 hash&(oldTable.length-1) + (hash&oldCap ==0 ? 0 : oldCap)
                        if ((e.hash & oldCap) == 0) {  
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);  //将链表复制到新数组中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;  //返回新数组的引用
}

扩容原理：翻倍扩容，节点要么在原来位置，要么两倍偏移
jdk7 同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部
jdk8 顺序不变

注意：当容量为2^n时，h & (length - 1) == h % length” . 按位运算特别快，非2^n时候，数据不能均匀分布在数组中

remove方法

//删除key对应的键值对
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

//参数matchValue为true表明只有key在HashMap中对应值为value时才删除; 为false表示强制删除;
final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {   //在table中查找对应hash值
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;		//头结点
        else if ((e = p.next) != null) {   //说明hash值存在冲突
            if (p instanceof TreeNode)   //hash值冲突由红黑树进行管理
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);   //查找红黑树并返回该节点
            else {   //hash值冲突由链表管理
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);  //从红黑树中删除该节点
            else if (node == p)
                tab[index] = node.next;   //直接修改
            else
                p.next = node.next;   //修改冲突链表
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

SynchronizedMap()方法

创建SynchronizedMap封装类，实现map接口，对map方法进行加锁重写，调用原方法

Hashtable

1
2
3

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

数据结构

不支持空键空值
初始长度 11
默认负载因子 0.75
线程安全方法synchronize 修饰
数组最大长度 Integer.MAX_VALUE - 8 ，防止OOM

源码分析

get()

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;	//index位置
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) { //同时比较hash和key
            return (V)e.value;
        }
    }
    return null;
}

rehash()扩容

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;	//数组长度变为原来两倍+1
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) { //原来节点依次放入新数组，先放进去的在链表尾部
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

put()

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; //找到hash所在index
    @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;
}

迭代遍历

初始化expectedModCount = modCount; next()判断不相等抛出异常ConcurrentModificationException

LinkedHashMap

1
2
3

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

数据结构

Entry节点结构

class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  //用于维护整个双向链表
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

有序性：提供保持插入顺序的(accessOrder = false) LinkedHashMap 和保持访问顺序的LinkedHashMap，LinkedHashMap的默认实现是按插入顺序排序的
resize()

jdk1.6 通过双向链表进行遍历旧数据

get() put() 会更将节点置为双向链表尾部

TreeMap

1
2
3

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

树

树：可以有多个子节点，顶部只有一个节点，顶部小，底部大
. 二叉树：每个节点最多有两个子节点
- 叶子节点：没有子节点的节点
- 层：根节点到该节点经过多少代
树变二叉树

树变二叉树的规则：每个结点的左指针指向它的第一个孩子结点。右指针指向它在树中的相邻兄弟结点。
也即：左孩子右兄弟。
根没有兄弟，所以转换以后的树没有右子树。

具体操作：

1. 在兄弟之间连线
2. 对每一个结点，只保持它与第一个子结点（长子）的连线，与其他子结点的连线全部抹去。
3. 以树根为轴心，顺时针旋转45度。

二叉树变树

二叉树变树的规则：是树变二叉树的逆过程。问：二叉树可以变成各种各样的树，为何这里只是唯一一种树形？这里只是假设这个二叉树是由上面的变换算法得来，那么过程可逆。所以对于有右子树的二叉树树形，是不能用这种办法化为树的

具体操作：

1. 加线。如果某个结点有左孩子，那么把这个左孩子的右孩子，右孩子的右孩子，一直右下去，全部连接到这个结点。这个对应树变二叉树算法中的抹掉与长子以外的结点的连线，现在要找回自己的全部儿子。
2. 去线。删除树中所有结点与这些右孩子的连线。找回了自己的儿子，不容许别人还和它们有瓜葛。
3. 层次调整。

平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点，其左右子树的高度都相近。

红黑树

特性：

1、每个节点都只能是红色或者黑色
2、根节点是黑色
3、每个叶节点（NIL节点，空节点）是黑色的。
4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长
检索效率O(log n)
左旋

LEFT-ROTATE(T, x)  
 y ← right[x]            // 前提：这里假设x的右孩子为y。下面开始正式操作
 right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子
 p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x
 p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
 if p[x] = nil[T]       
 then root[T] ← y                 // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点
 else if x = left[p[x]]  
           then left[p[x]] ← y    // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
           else right[p[x]] ← y   // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
 left[y] ← x             // 将 “x” 设为 “y的左孩子”
 p[x] ← y                // 将 “x的父节点” 设为 “y”

右旋

RIGHT-ROTATE(T, y)  
 x ← left[y]             // 前提：这里假设y的左孩子为x。下面开始正式操作
 left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”，即 将β设为y的左孩子
 p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”，即 将β的父亲设为y
 p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
 if p[y] = nil[T]       
 then root[T] ← x                 // 情况1：如果 “y的父亲” 是空节点，则将x设为根节点
 else if y = right[p[y]]  
           then right[p[y]] ← x   // 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子”
           else left[p[y]] ← x    // 情况3：(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
 right[x] ← y            // 将 “y” 设为 “x的右孩子”
 p[y] ← x                // 将 “y的父节点” 设为 “x”

TreeMap

数据结构

TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。
TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。
TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
TreeMap 实现了Cloneable接口，意味着它能被克隆。
TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。
TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
TreeMap是非同步的。它的iterator 方法返回的迭代器是fail-fastl的。
节点信息

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

源码分析

firstEntry() 和 getFirstEntry()

都是用于获取第一个节点。
但是，firstEntry() 是对外接口, 防止用户修改返回的Entry； getFirstEntry() 是内部接口

firstEntry()
返回exportEntry(getFirstEntry())
exportEntry：新建一个AbstractMap.SimpleImmutableEntry类型的对象，并返回

value()函数

public Collection<V> values() {
    Collection<V> vs = values;
    return (vs != null) ? vs : (values = new Values());
}

1	class Values extends AbstractCollection<V>

Values类就是一个集合。而 AbstractCollection 实现了除 size() 和 iterator() 之外的其它函数，因此只需要在Values类中实现这两个函数即可。
iterator() 则返回一个迭代器，用于遍历Values

1
2
3

public Iterator<V> iterator() {
    return new ValueIterator(getFirstEntry());
}

iterator() 是通过ValueIterator() 返回迭代器的，ValueIterator是一个类，它的主要实现应该在它的父类PrivateEntryIterator中

PrivateEntryIterator是一个抽象类，它的实现很简单，只实现了Iterator的remove()和hasNext()接口，没有实现next()接口。
而我们在ValueIterator中已经实现的next()接口

参考

http://www.cnblogs.com/skywang12345/p/3323085.html

https://blog.csdn.net/dou_yuan/article/details/77675872