Java Map集合之HashMap ,Map集合是Collection集合之外的另一个集合接口,将键(Key)映射到值(Value)的对象,一个Map里面不允许有重复的键,每个键最多只能映射一个值。下面先给大家看一下Map接口对应的继承和实现关系图。

我们常用到的主要是Hashmap、LinkedHashMap、HashTable、TreeMap这几个,而其中最重要的就是HashMap底层的相关数据结构和机制。

1.Map

概述

该集合存储键(key)值(value)对,一对一对往里存,而且要保证键(key)的唯一性。Map集合和Set集合很像,其实Set集合底层就是使用了Map集合。

常用方法

添加

  1. put(K key, V value):将指定的值与此映射中的指定键关联,添加键值对 。
  2. void putAll(Map<? extends K,? extends V> m):从指定映射中将所有映射关系复制到此映射中,批量添加键值对。

删除

  1. void clear():从此映射中移除所有映射关系,清空所有键值对。
  2. remove(Object key):如果存在一个键的映射关系,则将其从此映射中移除,删除单个键值对。

判断

  1. boolean containsKey(Object key):如果此映射包含指定键的映射关系(是否包含该键),则返回 true。
  2. boolean containsValue(Object value):如果此映射将一个或多个键映射到指定值(是否包含该值),则返回 true。
  3. boolean isEmpty():如果此映射未包含键-值映射关系,该map集合为空,则返回 true。

获取

  1. get(Object key):返回指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null。
  2. int size():返回此映射中的键-值映射关系(键值对)数。
  3. Collection<V> values():返回此映射中包含的值的 Collection 视图(集合)。
  4. 【重点】Set<K> keySet():返回此映射中包含的键的 Set 视图(集合)。
  5. 【重点】Set<Map.Entry<K,V>> entrySet():返回此映射中包含的映射关系的 Set 视图(集合)。

Map.Entry是Map接口的一个内部接口

interface Map{
	public static interface Entry{
		public abstract Object getKey();
		public abstract Object getValue();
	}
}
 
class HashMap implements Map{
	class Hahs implements Map.Entry{
		public Object getKey(){};
		public Object getValue(){};
	}
}

示例

keySet()entrySet()这两个方法比较重要,下面看一先 代码演示一下他们的基础使用:

package Collection;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MapTest {
    public static void main(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        map.put("张三",1);
        map.put("李四",2);
        map.put("王五",3);
        map.put("赵六",4);

       //使用KetSet()先获取map中的key集合,然后遍历
        Set<String> keys = map.keySet();
        for(String key:keys){
            System.out.println(key+","+map.get(key));
        }
        //使用Map.Entry将键值对放入集合,然后通过Entry的getKey、getValue方法获取
        Set<Map.Entry<String,Integer>> entrys =map.entrySet();
        for (Map.Entry entry:entrys){
            System.out.println(entry.getKey()+","+entry.getValue());
        }
    }
}

keySet方法的作用就是将map的键全部放到一个集合中去,在遍历Set的时候用map的get()方法就可以通过key获取对应的Value,其原理如下:

keySet

entrySet的原理如下图:

entrySet

2.HashMap

HashMap是Map接口的一个实现类,它的底层是数组+链表+红黑树完成的。HashMap增删、查找的性能是都比较好的,是一个综合性能的集合。下面会以JDK1.8以后的版本来讲。

数据结构

先来看一下Hash Map存贮的数据结构 :

HashMap中数据结构

部分源码

下面是HashMap的部分源码:常量和属性定义

public class HashMap<K,V> extends AbstractMap<K,V>
 2     implements Map<K,V>, Cloneable, Serializable {
 3         
 4         /**
 5          * 默认初始化容量,必须是2的次方。这个容量就是table的长度
 6          */
 7         static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 8 
 9         /**
10          * 这里指定了一个容量的上限,如果自己指定的值大于上限的话,就采用该默认值
11          */
12         static final int MAXIMUM_CAPACITY = 1 << 30;
13 
14         /**
15          * 默认加载因子,当没有指定加载因子的时候会采用该值,这个值的意义在于,当有效值比容量大于加载因子时
16          * 会扩容table数组
17          */
18         static final float DEFAULT_LOAD_FACTOR = 0.75f;
19 
20         /**
21          * 这个是一个链表在多长时转化为红黑树,默认为8
22          */
23         static final int TREEIFY_THRESHOLD = 8;
24 
25         /**
26          * 当一颗树的节点少于6个的时候,将这棵树转化为链表
27          */
28         static final int UNTREEIFY_THRESHOLD = 6;
29 
30         /**
31          * 当哈希表中的容量大于这个值时,表中的桶才能进行树形化 否则桶内元素太多时会扩容,而不是树形化 为了
32          * 避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD
33          */
34         static final int MIN_TREEIFY_CAPACITY = 64;
35         /**
36          * 这个数组会在第一次使用时初始化,并且在条件合适的时候重构,它的长度一定是2的整数次方
37          */
38         transient Node<K,V>[] table;
39     
40         /**
41          * 一个包含所有节点的Set
42          */
43         transient Set<Map.Entry<K,V>> entrySet;
44     
45         /**
46          * Map中的当前元素数量
47          */
48         transient int size;
49     
50         /**
51          * 这个是Map当中元素的修改次数(这里的修改只是说增加和减少元素时,该量会加一)
52          */
53         transient int modCount;
54     
55         /**
56          * 当大于这个值的时候会执行重构数组操作(capacity * load factor).
57          */
58         int threshold;
59     
60         /**
61          * 自定义的加载因子
62          */
63         final float loadFactor;
64     }

相关算法

散列定位

当我们要把一个<K,V>键值对放入map,就要把他的Key通过hashCode()方法获取hash值,我们如何定位到对应数组里面呢?一般有两种算法:hash是元素的hash值,n为当前HashMap的数组大小

  1. hash%n
  2. (n-1)&hash

其实上面两种算法得到的结果都是一样的,得到的结果对应数组的下标,下面我们以图的形式给大家举例演示。hash值一般是32位的二进制,下面为了方便起见,我就随意选一个数作为得到的hash值演示:

高位为0的部分省略

由图可知二者运算的结果是相同的,那么应该采用哪一种呢?对于我们人类来讲,一般会觉得第一种方式更容易理解,实际上计算机更依赖二进制运算,十进制运算在计算机底层也是转换成二进制的运算,所以第二种效率更高。

哈希算法

在上面的例子中,我只选取了一个很小的数字20,转换为二进制为10100只有5位有效,前面说过hashCode实际的位数为32位,当数组长度较小时,我们的hashcode实际上只用到了低位部分进行&运算,如下图:

hash值只有地位参与运算

虽然我用了一个任意一个hash值进行运算,如上图所示,只有低位进行了&运算,高位的并没有参与运算即没有作用,这样会导致很多不同的hash值结果得到的运算结果却相同,也就是增加了hash冲突的概率,并且数组长度越小这种情况越明显。JDK1.8中实际上对has值又进行了异或(^)运算,使原本的hash值高位也起到作用,下面是部分HashMap的源码:

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    //key取hash之后再和其右移16位经行异或运算
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

在hash()方法中,首先通过hashCode()方法获取到key的hash值,然后再对hash值的高位逻辑右移16位和原来的hash值进行异或运算(相同为0,不同为1)。下面我们就以之前的例子进行演示推导这个过程:

通过异或运算之后再使用(n-1)&hash,得到结果明显和之前不同,但是为什么要hash^(hash>>>16)而不是其他运算呢?这个主要是通过分析异或的结果1、0分布是最均匀的,能最低的降低hash冲突的概率,下面几种运算对比结果

几种运算的对比

上面分别接着上一个示例取hash和hash>>>16的结果采用不同运算方式去看结果,&运算是0多较的,| 运算是1多一些的,^虽然也没达到让结果中1和0的数量相同但是接近1:1,因为这里示例具有局限性,实际上如果使用大量数据去测试,^总是能让结果中1和0的比例更加均衡,可以降低(n-1)&hash得到的结果相同的概率,也就是减少hash冲突,最大程度保证数组能够均匀被使用。

put的过程

  1. 通过hash找到对应数组下标
  2. 如果数组为空直接插入
  3. 如果不为空则插入链表尾部或者红黑树中

下面就是put方法对应的源码

     public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
 
    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相同
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;//把e指向p的地址
            //判断p是红黑树节点
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //binCount:统计链表长度
                for (int binCount = 0; ; ++binCount) {
                    //循环遍历链表,知道找到next为空的节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //链表长度>=树化阈值8就进行树化,-1:此时新插入的还没有被算入总长度,比如现在7,插入当前链表长度变为8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //链表中存在key和插入的key相同,退出循环并且覆盖
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // 处理key相同的情况
                V oldValue = e.value; //保存旧的value
                if (!onlyIfAbsent || oldValue == null) 
                    e.value = value; //覆盖原来的值
                afterNodeAccess(e);
                return oldValue; //返回旧的value
            }
        }
        ++modCount;
        
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

另外当我们put()一个已经存在的的key的键值对,那么则会覆盖原来的值,返回oldVaule,其在HashMap源码中也可以分析出来。

扩容机制

HashMap默认大小为1<<4,即16,当我们不断放入新的元素,数组使用达到当前最大容量的3/4时,就会触发扩容机制,看一下面一个map的结构:

触发扩容以后如下:

扩容对于原来的元素来说只有两种情况

  1. 原有位置
  2. 原有位置+原有的数组大小

下面是扩容代码的过程:

扩容对应的源码resize()方法源码:

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // oldThr左移1位,容量整变为原来的2倍
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            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;
                //数组对应[j]不为空
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null) //新的数组对应index位置直接指向e
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)  //树节点操作
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // 链表处理
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //不需要移动位置,例如上面图示中的hash值为4的
                            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;
    }

线程安全问题

HashMap是线程不安全的,例如两个线程同时put,他们对应数组位置相同,有可能发生下面的情况:

2和18同时要指向数组下标为2的地址,假如2先完成,18接着完成,那么18就会覆盖掉2的指向,最终只有18成功插入。这就是HashMap中存在的线程不安全问题。Map接口的另一个实现类,ConcurrentHashMap采用CAS机制解决了HashMap中线程不安全的问题。

标签云

ajax AOP Bootstrap cdn Chevereto CSS Docker Editormd GC Github Hexo IDEA JavaScript jsDeliver JS樱花特效 JVM Linux Live2D markdown Maven MyBatis MyBatis-plus MySQL Navicat Oracle Pictures QQ Sakura SEO Spring Boot Spring Cloud Spring Cloud Alibaba SpringMVC Thymeleaf Vue Web WebSocket Wechat Social WordPress Yoast SEO 代理 分页 图床 小幸运 通信原理

Java Map集合之HashMap
Java Map集合之HashMap