文章目录

Map简介

Map简介

Map，即哈希表，也称字典，是一个键值对(Kry-Value)的数据结构，put()和get()函数几乎可以在常数级别内完成，哈希表有两种实现方式，一种被称为开放地址法(open addressing)，另一只被称为冲突链表法（seperate chaining），和之间的分析步骤一样，我们先看一下相关接口的设计，再深入到具体实现类。

1. Map接口

public interface Map<K,V> {

    int size();  						// k-v 对的数量
    boolean isEmpty();  				// map是否为空
    boolean containsKey(Object key);	// 是否包含指定的key
    boolean containsValue(Object value); // 是否包含指定的value
    V get(Object key);					// 获取指定key对应的value
    default V getOrDefault(Object key, V defaultValue)		// get or default，非常常用
    
    // Modification Operations
    V put(K key, V value);				// 设置 map[key]=value,返回该key之前对应的value
    V remove(Object key);				// 移除指定key的键值对，返回该key之前对应的value
    
    // Bulk Operations 块操作
    void putAll(Map<? extends K, ? extends V> m);  // 把哈希表m中的键值对全部放到当前map中来
    void clear();						// 清空当前map中的所有键值对
    Set<K> keySet();					// 返回所有key
    Collection<V> values();				// 返回所有values
    Set<Map.Entry<K, V>> entrySet(); 	// 返回所有键值对
    
}

常用的方法也就是上述的这些，由上述接口我们可以发现，在Map接口中其实还包含了另一个内部接口Map.Entry<K,V>，用来表示一个个键值对。这个Entry<K,V>接口中最关键的方法就是int hashCode(),到时候该键值对放在哪个地方，就是根据这里返回的哈希值来决定的。

在上述方法中还需要注意一个点，那就是Map.values()方法返回的是一个Collection对象，而Map.keys()返回的是一个Set对象，这个也很显然，哈希表中的key是唯一的、不会重复的，而value可以随便是什么值、支持重复。

2. HashMap实现类

这个类可以说是Java中用的最多的集合类之一了，HashMap采用的就是冲突链表法来实现的，一个很好的示意图如下：

常用的例子如下：

Map<String, Integer> map = new HashMap<>();

map.put("Andy", 123);
map.put("Jack", 333);
map.put("Rose", 233);

HashMap本身的继承和实现关系如下，AbstractMap抽象类中已经为我们已经实现好了一些默认的方法。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
	
	# ...
}

2.1 构造函数

首先，我们要知道，HashMap底层实现是按照数组+链表来实现的，我们在源码中可以发现transient Node<K,V>[] table;的存在，其中，每一个数组项，我们称之为桶。与之相关的有个属性叫做loadFactor，当哈希表中的桶的数量超过该装填因子时，会引发扩容，导致哈希表重新哈希。

构造函数有如下4个：

static final float DEFAULT_LOAD_FACTOR = 0.75f;  // 默认装填因子
static final int MAXIMUM_CAPACITY = 1 << 30;	// 最大容量 2^31-1
// The next size value at which to resize (capacity * load factor).
int threshold;

// 全部默认
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 指定初始化容量
public HashMap(int initialCapacity) { 
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 指定初始化容量和装填因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    // 确定扩容操作时的阈值 -- 这里实现有问题吗？其实没有
    this.threshold = tableSizeFor(initialCapacity);
}

// 用另外一个哈希表m来初始当前map
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

这里需要注意的就是tableSizeFor()这个函数，这个函数的作用就是大于或等于输入参数，且最近的2的整数次幂的数。比如参数为10时，则返回16；参数为4时，返回也是4，其代码如下：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这里我感觉怪怪的，this.threshold = tableSizeFor(initialCapacity);这一句是不是有bug呀？比方说，用户指定的capacity为15，tableSizeFor()方法返回一个16，你居然把16赋值给扩容阈值？什么情况？后来，我继续阅读后续源码才发现，此时哈希表的桶其实还没有初始化，即table数组还实际上没有申请内存，这一工作被推迟到了put()函数中，到时候threshold变量会被重新赋值成capacity * loadFactor。这里的位移操作还是很高效的。

2.2 put方法

这里我们需要知道几个点：

在HashMap的底层，是按照数组+链表来实现的，如果链表长度大于等于8，就会将链表变为红黑树；
对于链表的操作，插入和获取某个结点的时间复杂度是O(N),而红黑树可以达到O(log N)级别；
对于某个k-v对，首先我们要求key的hash值，然后将这个hash值与哈希表的容量做某个运算，得到具体放在哪个桶处。

Okay，暂时就将这么多，我们来看下源码。

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

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

// hash方法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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;
    // 如果对应的桶原来是空
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K, V> e;
        K k;
        // 如果桶的第一个结点，和当前入参的key相同(null 或 非null都可以)，那覆盖原来的键值对
        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果对应的桶中是红黑树，就在树中插入一个结点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
        // 对应的桶处是链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果插入新结点后，该桶对应的链表节点数大于8，就变成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 中间某个地方存在一个相同的key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 写入键值对，e已经是待放置的位置了
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 修改次数加1
    ++modCount;
    // 如果添加结点后容量大于扩容阈值，就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

我们先看下hash值和index是怎么计算的吧！这一部分来源于Yikun兄的分析，非常感谢！计算下标时，先对key的hashCode进行hash操作，然后再通过hash值进一步计算下标，如下图所示：

这个函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或。然后根据hash值求桶index时，用的是i = (n - 1) & hash与运算操作。

Q：为啥子要这样求hash呢？

A：主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

我们可以总结一下put()方法的大致流程：

对键值对的key求hash，然后再计算出index；
如果index对应的桶为空，直接放到桶中去；
如果index对应的桶不为空（即所谓碰撞了），那就用链表来存储该桶中的所有结点；
如果插入新结点后，链表长度大于等于TREEIFY_THRESHOLD，就把链表转为红黑树；
如果当前入参的key在哈希表中已经存在，就替换之前的键值对，返回原来的value；
如果put后超过了下一次扩容的阈值，就执行一次扩容操作。

2.2 扩容方法

HashMap中扩容的方法是resize()，这个我觉得是JDK 1.8 中对HashMap修改的精华部分，一开始我也没怎么看懂，后来在参考了Yikun兄的分析后恍然大悟，别担心，看完本文，你也会明白其中的道理的。

首先我想澄清两个事实，那就是：

HashMap中的数组，也就是桶的数量，无论何时，总是2的次方！
HashMap在扩容时，如果可以扩容的话，也总是扩容为原来的两倍！

Okay，有了这两个前提，我想先举一个例子来说明情况，假设我们原来的哈希表中的情况如下图所示：

假设最开始，哈希表的容量为16，扩容后大小为32，即oldCap=16，newCap=32，原来哈希表中各键值对情况如左图所示。

然后我们继续假设，扩容前，index=5处的桶中有一个链表存在，链表中有两个键值对，记为node1和node2，node1的hash值为1111 1111 1111 1111 0000 1111 0000 0101，而node2的hash值为1111 1111 1111 1111 0000 1111 0001 0101，二者就是在第5个二进制位上有区别。根据当前的index求解方法i = (n - 1) & hash,再次确认，这两个键值对都会放在index=5处的桶中。

现在执行一次扩容，扩容后的变换如下：

因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

扩容后，我们肯定要对哈希表中的键值对重新分布一次，而这里，我们实际上不需要做rehash，我们只要根据(e.hash & oldCap) == 0对原来桶中的结点进行一次判断，如果某结点e的hash值和oldCap进行&运算后为0，也就是扩容后的n-1对应的那个最高二进制位是0，就说明重新散列后，这个结点其实还是会待在原来的桶处；相反，如果(e.hash & oldCap) == 1，就说明重新散列后，这个结点会被放在原索引 + oldCap位置处。这里，我把这两种情况分别叫做高低链，高链对应(e.hash & oldCap) == 1的结点，低链对应(e.hash & oldCap) == 0的结点。OK，看代码吧：

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K, V>[] resize() {
    Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果oldCap>0,也就是桶中已经有键值对
    if (oldCap > 0)
    {
        // 如果旧的桶容量已经是最大容量,即2^31-1
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE; // threshold也设置为2^31-1
            return oldTab; // 返回原来的数组，相当于没扩容
        }

        // 如果扩容后也没超过最大容量，并且旧的容量大于默认初始容量（16）,就扩为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 阈值也自然扩为2倍

    }
    // 如果oldCap<=0,也就是初始化后，table数组并未分配内存的情况
    else if (oldThr > 0)
        // 初始化容量是存在了threshold变量中的
        newCap = oldThr;

    // 如果旧的容量小于默认初始容量（16）,最大为8，因为容量配时只按照2的次方分配
    // 不可能出现旧的容量为15或者12这样的情况
    else
    {
        // 那么就把新的容量赋值我默认初始容量（16）
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 对应else if (oldThr > 0)中的情况，此时把阈值算好
    if (newThr == 0) {
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                (int) ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    
    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) {
                oldTab[j] = null;  // 释放原来的空间，GC会发现
                if (e.next == null)  // 如果就旧桶为空，那新桶对应位置也为空
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)  // 如果桶中是一棵红黑树
                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K, V> loHead = null, loTail = null;  // 低位链
                    Node<K, V> hiHead = null, hiTail = null;  // 高位连
                    Node<K, V> next; // 游标指针
                    do {
                        next = e.next;
                        // 如果当前节点扩容后还放在原索引
                        if ((e.hash & oldCap) == 0) {
                            // 下面是低位链的尾插法
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 如果当前节点扩容，放在原索引+oldCap桶处
                        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;
                    }
                    // 把高位链放到扩容后数组的 原索引+oldCap 桶处
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

2.3 get方法

get()方法相对来说就比较简单了，只要按照key的hash值依次查找就行了。

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) {
        // 看下第一个结点是否对应
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 继续在后面的结点中查找
        if ((e = first.next) != null) {
            // 如果桶中是红黑树
            if (first instanceof TreeNode)
                return ((TreeNode<K, V>) first).getTreeNode(hash, key);
            // 链表的顺序遍历查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

3. ConcurrentHashMap

下次再补充

Java集合—Map篇

HashMap、ConcurrentMap