Java-Map之HashMap

Map概述

Map 提供了一个更通用的元素存储方法。
Map 集合类用于存储元素对（称作“键”和“值”），其中每个键映射到一个值。

Map的实现类

① HashMap：Map的主要实现类；无序的，线程不安全的，效率高；可以存储null的key和value。
② LinkedHashMap extends HashMap：有序的；保证在遍历map元素时，可以按照添加的顺序实现遍历。原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。对于频繁的遍历操作，此类执行效率高于HashMap。
③ TreeMap：保证按照添加的key-value键值对进行排序，实现排序遍历。此时key的自然排序或定制排序；底层使用红黑树存储。
④ Hashtable：作为古老的实现类；线程安全的，效率低；不能存储null的key和value。
⑤ Properties extends Hashtable：常用来处理配置文件。key和value都是String类型。

HashMap的底层实现原理

首先以jdk7为例说明：
HashMap map = new HashMap();这行代码执行后：
底层会定义数组的初始容量为默认的16，以下是jdk7内该构造器的源码：

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

可以看到，在初始化后，会定义数组的初始容量为默认的16，加载因子为默认的0.75。

map.put(key1,value1);在这行代码执行后，HashMap会在底层按照以下的流程去执行：

在不断的添加过程中，会涉及扩容和红黑树的问题，当超出临界值（且要存放的位置非空）时，会扩容。
默认的扩容方式：扩容为原来容量的2倍，并将原有数据复制过来。

jdk8 相较于jdk7，在底层实现方面的主要有以下几方面不同：
（1）new HashMap()时候，底层并没有定义初始容量为默认的16，仅仅定义了默认的加载因子，而是等到第一次put()的时候才会定义初始容量；put()过程中会调用resize()方法，resize()方法会在初始数组为空的时候，将初始容量定义为16；
（2）jdk 8底层的数组是：Node[]，而非Entry[]；
（3）首次调用put()方法时，底层才创建长度为16的数组；
（4）jdk 7底层结构只有：数组+链表；jdk 8中底层结构：数组+链表+红黑树。
当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64 时，
此时此索引位置上的所有数据会改为使用红黑树存储。

HashMap相关变量解析：
DEFAULT_INITIAL_CAPACITY：HashMap的默认容量：16
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
threadold：扩容的临界值=容量*填充因子：16*0.75 = 12
TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树：8
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量：64

以下附上HashMap的部分源码及其解析，主要是put()方法解析：

//底层使用的数组
transient Node<K,V>[] table;

//HashMap的默认容量：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final int MAXIMUM_CAPACITY = 1 << 30;

//HashMap的默认加载因子：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//Bucket中链表长度大于该默认值，转化为红黑树：8
static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

//桶中的Node被树化时最小的hash表容量：64
static final int MIN_TREEIFY_CAPACITY = 64;
//put方法
public V put(K key, V value) {
	//计算key的hash值传入putVal方法
	return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
	int h;
	//hash值计算方法
	//若key==null，hash=0;
	//key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值，然后做一次16位右位移异或混合计算得出hash值；
	//右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
    //tab = table;判断当前table数组是否为空
    if ((tab = table) == null || (n = tab.length) == 0)
        //若为空，调用resize方法，table为空时resize返回一个初始化过后的数组，长度为16
        n = (tab = resize()).length;
    //通过哈希值计算索引值，判断数组上该索引上是否有值
    if ((p = tab[i = (n - 1) & hash]) == null)
        //若为null，则直接插入新的数据
        tab[i] = newNode(hash, key, value, null);
    //若以上条件不满足，则需要比较hash值和key值是否相等
    else {
        HashMap.Node<K,V> e; K k;
        //先判断p处的hash值和传进来的hash值、再判断p.key和传进来的key的地址值是否相等、再通过equals方法判断两者的值是否相等
        //注意第一个逻辑与后面的条件，若地址值都相等了就不需要equals判断了
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            //将p指向的地址赋给e;
            e = p;
        //判断p处是否使用红黑树存储
        else if (p instanceof HashMap.TreeNode)
            e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //若以上条件不满足，进入以下
        else {
            for (int binCount = 0; ; ++binCount) {
                //判断node节点p是否存在下一个元素，即使判断p.next是否为空
                if ((e = p.next) == null) {
                    //若p.next为空，则把新的元素放到p.next里，原本的值还在数组索引的第一处
                    p.next = newNode(hash, key, value, null);
                    //判断链表长度，决定是否使用红黑树存储；若大于TREEIFY_THRESHOLD-1，则使用红黑树进行存储
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    //跳出循环，e=p.next;
                    break;
                }
                //先判断e=p.next处的hash值和传进来的hash值、再判断e.key和传进来的key的地址值是否相等、再通过equals方法判断两者的值是否相等
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    //若相等，跳出循环,e=p.next
                    break;
                //若以上条件不符合，则p=e;即p = p.next;
                p = e;
            }
        }
        //经过以上条件后，判断e是否为空
        if (e != null) { // existing mapping for key
            //若不为空，取出e的value值给变量oldValue;
            V oldValue = e.value;

            if (!onlyIfAbsent || oldValue == null)
                //更新e的value值
                e.value = value;
            afterNodeAccess(e);
            //返回旧的value值
            return oldValue;
        }
    }
    ++modCount;
    //添加新元素后，判断++size是否大于临界值
    if (++size > threshold)
        //若大于临界值，调用resize()扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

Map中的方法

添加、删除、修改操作：
Object put(Object key,Object value)：将指定的key-value添加到（或修改到）当前map对象中
void putAll(Map m)：将m中的所有key-value复制到当前map中
Object remove(Object key)：移除指定key的key-value数据，并返回value
void clear()：清空当前map的所有数据
元素查询的操作：
Object get(Object key)：获取指定key对应的value
boolean containsKey(Object key)：map对象中是否包含指定的key
boolean containsValue(Object value)：map对象中是否包含指定的value
int Size()：返回当前map中key-value键值对的个数
boolean isEmpty()：判断当前map是否为空
boolean equals(Object obj)：判断当前map和参数obj是否相等

元视图操作的方法：
Set keySet()：返回所有key构成的Set集合
Collection values()：返回所有value构成的Collection集合
Set entrySet()：返回所有key-value键值对构成的Set集合

线程安全的几种Map

ConcurrentHashMap - 推荐

• 当你程序需要高度的并行化的时候，你应该使用ConcurrentHashMap；
• 尽管没有同步整个Map，但是它仍然是线程安全的；
• 读操作非常快，而写操作则是通过加锁完成的；
• 在对象层次上不存在锁（即不会阻塞线程）；
• 锁的粒度设置的非常好，只对哈希表的某一个key加锁；
• ConcurrentHashMap不会抛出ConcurrentModificationException，即使一个线程在遍历的同时，另一个线程尝试进行修改；
• ConcurrentHashMap会使用多个锁。

SynchronizedMap

这种是直接使用工具类里面的方法创建SynchronizedMap，把传入进行的HashMap对象进行了包装同步。
用法：
Map<String, Object> map22 = Collections.synchronizedMap(new HashMap<String, Object>());

• 会同步整个对象；
• 每一次的读写操作都需要加锁；
• 对整个对象加锁会极大降低性能；
• 这相当于只允许同一时间内至多一个线程操作整个Map，而其他线程必须等待；
• 它有可能造成资源冲突（某些线程等待较长时间）；
• SynchronizedHashMap会返回Iterator，当遍历时进行修改会抛出异常。

HashTable

HashTable作为古老的实现类；线程安全的，效率低；不能存储null的key和value。
用法：Map<String, Object> map33 = new Hashtable<>();
通过查阅HashTable的源码可以知道，HashTable初始化的容量是11，加载因子为0.75：

 * Constructs a new, empty hashtable with a default initial capacity (11)
 * and load factor (0.75).
 */
public Hashtable() {
    this(11, 0.75f);
}

再继续查看HashTable的源码发现，get/put方法都被synchronized关键字修饰，说明它们是方法级别阻塞的，它们占用共享资源锁，所以导致同时只能一个线程操作get或者put，而且get/put操作不能同时执行，所以这种同步的集合效率非常低，一般不建议使用这个集合。

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

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;
}

Map相关面试题

HashMap 和 Hashtable 的区别

（1）线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
（2）效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
（3）对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。

HashMap为什么可以存储null键呢？HashMap在put null键的时候，会计算键的hash，在键为null的时候，hash值为置为0，这样就不会因为调用key.hashCode()方法而产生空指针异常。
HashTable为啥不允许有 null 键和 null 值呢？以下是HashTable的部分源码：

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;
}

从以上可以看到，HashTable本身就不允许有 null 键和 null 值，至于设计者为什么要这么设计，网上有两种说法：
1、当时不允许是因为希望每个 key 都会实现 hashCode 和 equals 方法。而 null 显然没有；
2、HashTable是支持并发的，在并发的情况下，get方法具有模糊行为。如果在映射中找不到键，则它可以返回null；如果找到键并且其值为null，则它也可以返回null。

（4）初始容量大小和每次扩充容量大小的不同 ：
① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始大小为 16。之后每次扩充，容量变为原来的 2 倍。
② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（可以看HashMap 中的tableSizeFor()方法源码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小，后面会介绍到为什么是 2 的幂次方。
（5）底层数据结构： JDK 1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 的长度为什么是 2 的幂次方？

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

这个算法应该如何设计呢？我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了：

• 取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方；）。
• 并且，采用二进制位操作 &，相对于 % 能够提高运算效率，

这就解释了 HashMap 的长度为什么是 2 的幂次方。

HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashSet 如何检查重复

由于HashSet 底层就是基于 HashMap 实现的，所以根据前面的put()流程图可以知道：
当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

hashCode()与 equals() 的相关规定：

（1）如果两个对象相等，则 hashcode 一定也是相同的；
（2）两个对象相等,对两个 equals() 方法返回 true；
（3）两个对象有相同的 hashcode 值，它们也不一定是相等的；
（4）综上，equals() 方法被覆盖过，则 hashCode() 方法也必须被覆盖；
（5）hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

== 与 equals 的区别

对于基本类型来说，== 比较的是值是否相等；
对于引用类型来说，== 比较的是两个引用是否指向同一个对象地址（两者在内存中存放的地址（堆内存地址）是否指向同一个地方）；
对于引用类型（包括包装类型）来说，equals 如果没有被重写，对比它们的地址是否相等；如果 equals()方法被重写（例如 String），则比较的是地址里的内容。

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

• 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
• 实现线程安全的方式（重要）：
  ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
  ② Hashtable(同一把锁) ：使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

到 JDK1.8 的时候，ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。
在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）；而且synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

附上ConcurrentHashMap的put方法的源码，可以看到并没有像Hashtable一样将整个方法进行加锁，相比之下也就没有那么重量级：

final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

HashMap遍历方式

HashMap 遍历从大的方向来说，可分为以下 4 类：

（1）迭代器（Iterator）方式遍历；
（2）For Each 方式遍历；
（3）Lambda 表达式遍历（JDK 1.8+）；
（4）Streams API 遍历（JDK 1.8+）。