什么是Map

Map集合体系全景图

Map调集是一种存储键值对的数据结构,其间每个键都仅有且对应一个值。Map调集一般用于需求快速查找和拜访数据的场景,例如字典、缓存、配置文件等。

Java中的Map调集有多种完成,包括HashMap、TreeMap、LinkedHashMap等。其间,HashMap是最常用的完成,它运用哈希表来存储键值对,能够快速查找和拜访数据。TreeMap运用红黑树来存储键值对,能够确保键的有序性。LinkedHashMap则运用双向链表来保护键值对的刺进次序

Map调集供给了一系列办法来操作键值对,例如put()办法用于增加键值对,get()办法用于获取指定键对应的值,containsKey()办法用于判别是否包括指定键等。

运用Map调集时需求留意键的仅有性,假如增加了重复的键,则会掩盖原有的值。此外,Map调集的键和值能够是恣意类型,但一般运用根本类型或其包装类、字符串等常见类型作为键和值。

HashMap特点

  1. HashMap是依据哈希表完成的,能够快速地进行刺进、查找和删去操作
  2. HashMap答应存储键和值
  3. HashMap是无序的,即元素的次序不是依照刺进次序或许其他次序排列的
  4. HashMap的功能受到哈希函数的影响,假如哈希函数欠好,可能会导致哈希抵触,影响功能
  5. HashMap的默许初始容量为16,负载因子为0.75,当HashMap中的元素数量超过容量*负载因子时,会主动扩容
  6. HashMap是线程不安全的,假如多个线程一起对同一个HashMap进行操作,可能会导致数据不一致的问题。能够运用ConcurrentHashMap来解决线程安全问题

JDK1.8,哈希表选用的数据结构:

哈希表选用的数据结构是数组+链表/红黑树的组合结构。详细来说,哈希表中的每个元素都是一个链表或红黑树,数组中的每个元素指向一个链表或红黑树的根节点。当哈希表中的元素数量较少时,每个元素都是一个链表;当元素数量较多时,会将链表转化为红黑树,以进步查找功率

Map集合体系全景图

JDK1.8之前,哈希表选用的数据结构:

哈希表选用的数据结构是数组和链表的组合,也就是链表散列。每个数组元素都是一个链表的头节点,当产生哈希抵触时,新的元素会被刺进到对应数组元素的链表中。这种数据结构的缺陷是在哈希抵触严峻时,链表会变得很长,导致查询功率下降。 HashMap优缺陷

Map集合体系全景图

数组和链表+红黑树为什么比数组+链表更高效

  • 数组:随机拜访元素的时刻复杂度为O(1),刺进和删去元素的时刻复杂度为O(n)
  • 链表:刺进和删去元素的时刻复杂度为O(1),随机拜访元素的时刻复杂度为O(n)
  • 红黑树的时刻复杂度为O(log n),具有较好的平衡性和查找功能,适用于需求频频刺进、删去和查找的场景。 因此,红黑树相比于数组和链表,具有更高的功率,尤其是在需求频频刺进、删去和查找的场景下。

HashMap的优点:

  1. 快速的查找和刺进操作,时刻复杂度为O(1);
  2. 能够存储很多的键值对;
  3. 支撑键和值;
  4. 能够经过迭代器遍历键值对;
  5. 能够经过键快速查找对应的值。

HashMap的缺陷:

  1. HashMap是非线程安全的,需求在多线程环境下运用时进行同步处理;
  2. HashMap的初始容量和负载因子需求合理设置,不然会影响功能;
  3. HashMap的遍历次序是不确定的,不适合需求依照次序拜访元素的场景;
  4. 当HashMap中的元素数量到达一定程度时,会呈现哈希抵触,影响功能;
  5. HashMap的完成是依据哈希表的,因此在存储空间上比较浪费。

HashMap运用场景

  1. 快速查找:假如需求快速查找键值对,能够运用HashMap。
  2. 高效刺进和删去:假如需求高效刺进和删去键值对,能够运用HashMap。
  3. 存储不同类型的键值对:假如需求存储不同类型的键值对,能够运用HashMap。
  4. 缓存:HashMap能够用于缓存数据,能够将数据存储在HashMap中,避免频频地从数据库或许其他存储介质中读取数据。

HashMap和List是两种不同的数据结构,各自有自己的优缺陷。

HashMap的优点:

  1. 快速查找:HashMap是依据哈希表完成的,能够快速查找元素,时刻复杂度为O(1)。
  2. 高效刺进和删去:HashMap的刺进和删去操作也很高效,时刻复杂度为O(1)。
  3. 能够存储键值对:HashMap能够存储键值对,能够依据键快速查找对应的值。

HashMap的缺陷:

  1. 内存占用较大:HashMap需求保护哈希表,需求占用较多的内存空间。
  2. 不支撑次序拜访:HashMap是无序的,不支撑依照刺进次序或许其他次序拜访元素。
  3. 哈希抵触:假如哈希函数欠好,可能会呈现哈希抵触,影响查找功率。

List的优点:

  1. 支撑次序拜访:List是有序的,支撑依照刺进次序或许其他次序拜访元素。
  2. 内存占用较小:List只需求存储元素本身,不需求保护哈希表,占用内存较小。
  3. 能够存储重复元素:List能够存储重复元素。

List的缺陷:

  1. 查找功率低:List的查找功率较低,需求遍历整个列表,时刻复杂度为O(n)。
  2. 刺进和删去功率低:List的刺进和删去操作功率较低,需求移动其他元素,时刻复杂度为O(n)。
  3. 不支撑快速查找:List不支撑快速查找元素,需求遍历整个列表才干找到对应的元素。

HashMap和List的运用场景:

  1. 假如需求快速查找元素,能够运用HashMap。
  2. 假如需求依照次序拜访元素,能够运用List。
  3. 假如需求存储键值对,而且需求快速查找对应的值,能够运用HashMap。
  4. 假如需求存储重复元素,能够运用List。

HashMap简略运用案例教学

假设咱们要核算一篇文章中每个单词呈现的次数,能够运用HashMap来完成。详细步骤如下:

import java.util.HashMap;
public class HashMapExample {
    public static void main(String[] args) {
    String article = "Java is a programming language and computing platform first released by Sun Microsystems in 1995. It is the underlying technology that powers state-of-the-art programs including utilities, games, and business applications. Java runs on more than 1 billion devices worldwide, including PCs, mobile phones, and smart TVs.";
    //1.  将文章内容依照空格切割成单词,并存储到一个字符串数组中。
    String[] words = article.split(" ");
    //2.创立一个HashMap目标,用于存储每个单词呈现的次数
    HashMap<String, Integer> wordCount = new HashMap<>();
    //3.  遍历单词数组,核算每个单词呈现的次数,并将成果存储到HashMap中。
    for (String word : words) {
        if (wordCount.containsKey(word)) {
            wordCount.put(word, wordCount.get(word) + 1);
        } else {
            wordCount.put(word, 1);
        }
    }
    //遍历HashMap打印每个单词呈现的次数
    for (String word : wordCount.keySet()) {
        System.out.println(word + ": " + wordCount.get(word));
    }
}

HashMap源码剖析

//界说了一个泛型类HashMap,它继承了AbstractMap类,并完成了Map接口,一起也完成了Cloneable和Serializable(序列化)接口
//AbstractMap是一个抽象类,完成了Map接口的大部分办法,但是将一些办法留给详细的子类去完成
public class HashMap<K,V> extends AbstractMap<K,V>  
implements Map<K,V>, Cloneable, Serializable {}
//默许的初始容量,即HashMap创立时的默许容量巨细为16。
//<< 是Java中的位运算符,表明左移运算符
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
//HashMap的最大容量,即2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;  
//负载因子,默许到达多少进行扩容那
static final float DEFAULT_LOAD_FACTOR = 0.75f;  
//当链表长度到达该值时,链表会转化为红黑树
static final int TREEIFY_THRESHOLD = 8;  
//当红黑树节点数小于该值时,红黑树会转化为链表
static final int UNTREEIFY_THRESHOLD = 6;  
//当HashMap的容量小于该值时,不会将链表转化为红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
//下面这段代码界说了HashMap中的节点(Node)类,
//每个节点包括了键(key)、值(value)、哈希值(hash)和指向下一个节点的指针(next)。
//节点类完成了Map.Entry接口,供给了getKey()、getValue()、setValue()等办法,
//一起还重写了hashCode()、equals()和toString()办法,以便在HashMap中运用。
static class Node<K,V> implements Map.Entry<K,V> {  
    final int hash;  
    final K key;  
    V value;  
    Node<K,V> next;  
    Node(int hash, K key, V value, Node<K,V> next) {  
    this.hash = hash;  
    this.key = key;  
    this.value = value;  
    this.next = next;  
    }  
    public final K getKey() { return key; }  
    public final V getValue() { return value; }  
    public final String toString() { return key + "=" + value; }  
    public final int hashCode() {  
    return Objects.hashCode(key) ^ Objects.hashCode(value);  
    }  
    public final V setValue(V newValue) {  
    V oldValue = value;  
    value = newValue;  
    return oldValue;  
    }  
    public final boolean equals(Object o) {  
    if (o == this)  
    return true;  
    if (o instanceof Map.Entry) {  
    Map.Entry<?,?> e = (Map.Entry<?,?>)o;  
    if (Objects.equals(key, e.getKey()) &&  
    Objects.equals(value, e.getValue()))  
    return true;  
    }  
    return false;  
    }  
}

为什么要界说节点类

在HashMap中,每个键值对都被封装在一个节点(Node)目标中。节点目标包括了键、值、哈希值和指向下一个节点的引证。界说节点类的目的是为了在HashMap中存储键值对,而且能够经过哈希值快速定位到对应的节点。一起,节点类还完成了Map.Entry接口,使得节点目标能够被视为一个键值对。

继续HashMap源码剖析

//并回来一个int类型的哈希值
static final int hash(Object key) {  
    int h;  
//它首要判别传入的目标是否为空,假如是则回来0
//不然调用目标的hashCode()办法得到一个int类型的哈希码h
//然后将h右移16位并与原来的h进行异或运算,最终得到一个int类型的哈希值,拉链法办法来进行核算
//它能够削减哈希抵触的概率
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
}
//用于获取一个目标的Comparable类型
static Class<?> comparableClassFor(Object x) {  
    //instanceof是Java中的一个关键字,用于判别一个目标是否属于某个类或其子类的实例
    if (x instanceof Comparable) {  
    Class<?> c;  //表明一个不知道类型的类,能够经过调用其办法获取类的信息。
    Type[] ts, as; Type t;
    //Type[] ts 表明一个不知道类型的数组,用于存储类型信息
    //Type t:表明一个不知道类型的类型,用于存储类型信息。
    ParameterizedType p;  //表明一个不知道类型的参数类型
    if ((c = x.getClass()) == String.class) 
    // 将变量x的类型赋值给变量c,假如x的类型是String类,则直接回来String类,不进行其他的检查。
    return c;  
    //getGenericInterfaces() 办法回来的是 Type 目标的数组,表明该类所完成的泛型接口的类型。
    if ((ts = c.getGenericInterfaces()) != null) {  
    for (int i = 0; i < ts.length; ++i) {  
    //判别是否为ParameterizedType类型
    if (((t = ts[i]) instanceof ParameterizedType) &&  
    //判别其原始类型是否为Comparable.class
    ((p = (ParameterizedType)t).getRawType() ==  
    Comparable.class) &&  
    //其实践类型参数假如as不为空 ,而且长度为 1,且第一个参数为 c,
    //则阐明该类型完成了Comparable接口,而且泛型参数类型为c
    (as = p.getActualTypeArguments()) != null &&  
    as.length == 1 && as[0] == c)
    return c;  
        }  
       }  
    }  
    return null;  
}

ParameterizedType是 Java 中的一个接口,表明一个参数化类型,即一个泛型类型实例化后的类型。例如,List<String>就是一个参数化类型,它实例化了List泛型类型,其间的类型参数为StringParameterizedType接口供给了获取实践类型参数的办法,能够经过它来获取泛型类型实例化后的详细类型。

//该办法用于比较两个目标的巨细关系
    static int compareComparables(Class<?> kc, Object k, Object x) {  
    //两个目标类型不一致回来0,不然进行进行比较俩个目标
    return (x == null || x.getClass() != kc ? 0 :  
    ((Comparable)k).compareTo(x));  
    }
    //这个办法一般用于核算哈希表的巨细,确保哈希表的巨细是2的幂次方,以便于哈希函数的核算。
    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;  
    }
  // 存储元素的数组,总是2的幂次倍
    transient Node<K,V>[] table;
  // 存放详细元素的集
    transient Set<Map.Entry<K,V>> entrySet;
   // 存放元素的个数,留意这个不等于数组的长度。
    transient int size;
 // 每次扩容和更改map结构的计数器
    transient int modCount;
// 阈值(容量*负载因子) 当实践巨细超过阈值时,会进行扩容
    int threshold;
 // 负载因子
    final float loadFactor;
    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;  
    //用于核算大于等于给定整数的最小2的幂次方数。
    //这个办法的作用是为了确保HashMap的桶的数量始终是2的幂次方,这样能够更高效地进行哈希核算
    this.threshold = tableSizeFor(initialCapacity);  
}
//创立一个具有指定初始容量的 HashMap 实例,并运用默许的负载因子
public HashMap(int initialCapacity) {  
this(initialCapacity, DEFAULT_LOAD_FACTOR);  
}
//段代码中设置为默许的负载因子,而其他字段则运用默许值
public HashMap() {  
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted  
}
//创立一个包括指定map中所有键值对的新HashMap目标
public HashMap(Map<? extends K, ? extends V> m) {  
//负载因子为默许
this.loadFactor = DEFAULT_LOAD_FACTOR;  
//调用putMapEntries办法将指定map中的键值对增加到新的HashMap目标中
putMapEntries(m, false);  
}
//HashMap结构函数中用来将一个已有的Map中的键值对增加到新的HashMap中的办法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
//获取map巨细
    int s = m.size();  
    if (s > 0) {  
    if (table == null) {
    //则依据 s 核算出初始容量 ft
    float ft = ((float)s / loadFactor) + 1.0F;  
    //并将其设置为当时 HashMap 的 threshold。
    //threshold是一个阈值,表明当哈希表中的元素数量到达这个值时,
    //需求进行扩容操作。在这段代码中,假如s大于threshold,就会调用resize()办法进行扩容
    int t = ((ft < (float)MAXIMUM_CAPACITY) ?  
    (int)ft : MAXIMUM_CAPACITY);  
    if (t > threshold)  
    threshold = tableSizeFor(t);  
    }  
    else if (s > threshold)  
    resize();  
    //遍历另一个 Map 中的所有键值对,将其增加到当时 HashMap 中
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {  
    K key = e.getKey();  
    V value = e.getValue();  
    putVal(hash(key), key, value, false, evict);  
    }  
    }  
}

Map源码重点扩容

//对哈希表进行扩容的办法
//获取旧表的长度和阈值,然后依据旧表的长度和阈值核算出新表的长度和阈值。
//假如旧表的长度大于0,则判别是否到达了最大容量,假如是则直接回来旧表;不然将旧表长度左移一位得到新表长度
//假如新表长度小于最大容量且旧表长度大于等于默许初始容量,则将阈值也左移一位,行将阈值翻倍
//假如旧表长度为0但阈值大于0,则将阈值作为新表长度;不然运用默许初始容量和默许负载因子核算出新表长度和阈值
//最终依据新表长度创立一个新的哈希表,将旧表中的元素转移到新表中,假如元素的哈希值在旧表长度范围内,则直接放入新表中
//最终依据新表长度创立一个新的哈希表,将旧表中的元素转移到新表中,假如元素的哈希值在旧表长度范围内,则直接放入新表中
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        //旧表的长度大于0
        if (oldCap > 0) {
        //旧表是否到达了最大容量
            if (oldCap >= MAXIMUM_CAPACITY) {
            //阈值等于Integer的最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
              //假如当时 HashMap 的容量小于最大容量,而且当时容量大于等于默许初始容量
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     //则将新容量设置为原容量的两倍
                newThr = oldThr << 1; // double threshold
        }
        //假如旧阈值在大于0,则将新容量设置为旧阈值
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {   //不然,假如旧阈值为0,则表明运用默许值,将新容量设置为默许初始容量,一起将新阈值设置为默许初始容量乘以默许负载因子。          
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
      //  假如新的阈值为0,则依据新的容量和负载因子来核算新的阈值。假如新的容量小于最大容量
      //而且新的容量乘以负载因子小于最大容量,则运用新的容量乘以负载因子作为新的阈值。
      //不然,新的阈值将被设置为Integer.MAX_VALUE,表明运用最大的阈值
        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) {
                //新表长度创立一个新的哈希表,将旧表中的元素转移到新表中
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e; 
                    else if (e instanceof TreeNode)
                    //假如元素e是一个树节点,则调用其split()办法将其子节点也刺进到新哈希表中
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {
                    // 将元素e刺进到新哈希表中,并坚持原有的次序
                    //还界说了四个节点变量loHead、loTail、hiHead和hiTail
                    //用于保存元素e的前驱和后继节点
                        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;
                            }
                            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;
    }

Map源码重点将键值对刺进到HashMap

 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;
            //依据哈希值hash核算出键在哈希表中的索引i指针p指向哈希表中索引为i的方位。
            //&是按位与运算符,用于将n - 1和hash进行按位与运算,得到一个在0到n - 1范围内的整数
        if ((p = tab[i = (n - 1) & hash]) == null)
        //为空,则直接将新节点刺进
            tab[i] = newNode(hash, key, value, null);
        else {
        //不为空则遍历链表或红黑树
            Node<K,V> e; K k;
            //查找是否现已存在相同的key,假如存在,则更新对应的value值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)//用于判别p是否是TreeNode类型的实例
            //强制转换为TreeNode<K,V>类型,然后调用putTreeVal办法将参数传递给它
            //表明将一个键值对刺进到树形结构中
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            //binCount 表明当时链表的长度
                for (int binCount = 0; ; ++binCount) {
                // 假如当时节点的下一个节点为空,阐明当时节点是链表的最终一个节点
                //将新节点刺进到当时节点的下一个节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //假如链表长度大于等于该值8,则将链表转化为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);
                        break;
                    }
                    //-   假如找到了相同的键值对,则不进行刺进操作。
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //哈希表中某个键值对进行更新操作的代码
            if (e != null) { 
            //哈希表中某个键值对进行更新操作的代码
                V oldValue = e.value;
                //假如onlyIfAbsent为false或许oldValue为
                if (!onlyIfAbsent || oldValue == null)
                //则将该键值对的值更新为新值value
                    e.value = value;
                    //则将该键值对的值更新为新值value
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    //链表转换为红黑树的办法
    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)
            resize();//扩容办法
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {//replacementTreeNode 是一个办法,用于将链表节点转换为红黑树节点
                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); 转换为红黑树
        }
    }