欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java Map及其实现类的底层原理

程序员文章站 2022-06-21 13:42:46
文章目录一、Map接口及其多个实现类的对比二、Map中存储的key-value特点三、HashMap在JDK7中的底层原理四、HashMap在JDK8中的底层原理五、HashMap在JDK7中的底层源码5.1 构造器5.2 put方法六、HashMap在JDK8的源码分析6.1 构造器6.2 put七、LinkedHashMap的底层实现笔记来源: 尚硅谷一、Map接口及其多个实现类的对比首先看下Map及其实现类的类图关系:Map:双列数据,存储key-value对的数据|实现类 |含义 |...


笔记来源: 尚硅谷

一、Map接口及其多个实现类的对比

首先看下Map及其实现类的类图关系:

java Map及其实现类的底层原理

Map:双列数据,存储key-value对的数据
|实现类 |含义 |
|:----|:----|:----|
|HashMap |一般来说作为Map的主要实现类, 线程不安全效率高可以存储null的key和value
① JDK7及以前:数组+链表
② JDK8:数组+链表+红黑树 |
|LinkedHashMap |保证在遍历map元素时,可以按照添加的顺序实现遍历。在原有的HashMap基础上,添加了一对指针,指向前一个和后一个元素。对于频繁的遍历操作,此类执行效率高于HashMap |
|Hashtable |古老的实现类【甚至命名都不规范】,现在已经不怎么用了, 线程安全,效率低,不能存储null的key和value |
|TreeMap |存储有序的键值对,实现排序遍历【按照key排】,底层使用红黑树 |
|Properties |Hashtable子类,常用来处理配置文件,key和value都是string类型 |

常见面试题:

  • HashMap的底层实现原理

  • HashMap 和 Hashtable异同

  • ConcurrentHashMap 与 Hashtable区别

二、Map中存储的key-value特点

java Map及其实现类的底层原理

  1. Map中的key是无序的,不可重复的 --> key所在的类要重写equals()和hashCode()方法【以HashMap为例】

  2. Map中的value是无序的,可重复的 --> value所在类要重写equals()fangfa1

一个键值对:key-value构成了一个Entry对象,是无序不可重复的,用set存放

三、HashMap在JDK7中的底层原理

HashMap map = new HashMap(); 

在实例化以后,底层创建了长度是16的一维数组 Entry[] table.

map.put(key1,value1) 

调用key1 所在类的hashCode()计算key1哈希值,此哈希值经过某种算法计算以后,得到在Entry数组中的存放位置。

① 如果此位置数据为空,则key1-value1添加成功 【情况1】
② 如果此位置数据不为空,(意味者此位置上存在一个或多个数据(以链表形式存在)),比较key1与已经存在的一个或多个数据的哈希值,

  • 如果key1的哈希值与已经存在的哈希值都不相同,此时添加成功 【情况2】
  • 如果key1的哈希值与已经存在的哈希值都相同,继续比较,调用key1所在类的equals方 法,如果equals返回false,则key1-value1添加成功;如果equals返回true,则用value1替换相同key的value值 【情况3】

补充:关于 情况2情况3 :此时key1-value1 和原来的数据以 链表 的方式存储。【见下图】
在不断的添加过程中,会涉及到扩容问题,默认的扩容方式:扩容为原来容量的2倍,并将原有的数据复制过来。

java Map及其实现类的底层原理

四、HashMap在JDK8中的底层原理

jdk8相较于jdk7在底层实现方面的不同:

1. new HashMap():底层没有创建一个长度为16的数组 
2. jdk8 底层的数组是:Node[],而非Entry[] 
3. 首次调用put()方法时,底层创建长度为16的数组 
4. 原来jdk7底层结构只有数组+链表,jdk8是数组+链表+红黑树 
   当数组的某一个索引位置上的元素以链表形式存在的个数 > 8,且 
   当前数组的长度 > 64时,此时此索引位置上的所有数据改为使用红黑树 
   存储【方便查找】。 

五、HashMap在JDK7中的底层源码

面试题:
谈谈你对 HashMap 中 put/get 方法的认识?如果了解再谈谈HashMap的扩容机制?默认大小是多少?什么是负载因子(或填充比)?什么是吞吐临界值(或阈值、threshold)?

HashMap源码中的重要常量 
DEFAULT_INITIAL_CAPACITY: HashMap的默认容量,16 
MAXIMUM_ CAPACITY : HashMap的最大支持容量,2^30 
DEFAULT_LOAD_FACTOR: HashMap的默认加载因子 0.75 
TREEIFY_THRESHOLD: Bucket中链表长度大于该默认值 8,转化为红黑树 
UNTREEIFY_THRESHOLD: Bucket中红 黑树存储的Node小于该默认值,转化为链表 
MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量。(当桶中Node的 
数量大到需要变红黑树时,若hash表容量小于MIN_TREEIFY_CAPACITY时,此时应执行 
resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4 
倍。) 

table: 存储元素的数组,总是2的n次幂 
entrySet: 存储具体元素的集 
size: HashMap中 存储的键值对的数量 
modCount: HashMap扩 容和结构改变的次数。 
threshold: 扩容的临界值,=容量*填充因子 
loadFactor: 填充因子 

5.1 构造器

//DEFAULT_INITIAL_CAPACITY: HashMap的默认容量,16 
//DEFAULT_LOAD_FACTOR: HashMap的默认加载因子,0.75 
public HashMap() ( 
this(DEFAULT_INITIAL_CAPACITY, 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); 
      // 找到一个大于等于initialCapacity并且是2的指数的值作为初始容量 
      // 所以你如果传进来15,那么容量为16 
      int capacity = 1; 
      while (capacity < initialCapacity) 
          capacity <<= 1; 

      this.loadFactor = loadFactor;//加载因子,默认0.75 
      // 初始化阈值【当占用到阈值的时候扩容】 
      threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 
      // 初始化Entry数组 
      table = new Entry[capacity]; 
      useAltHashing = sun.misc.VM.isBooted() && 
              (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 
      init(); 
  } 

5.2 put方法

解析都在代码里 ↓

public V put(K key, V value) { 
  //如果key为null,其实也往里面放了 
  if (key == null)  
      return putForNullKey(value); 
  //计算当前key的哈希值 
  int hash = hash(key); 
  // 查找对应的数组下标【hash & (length-1)】 
  int i = indexFor(hash, table.length); 
   
  for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
      //如果在i位置上已经有元素了,对比这个位置上的所有元素 
      Object k; 
      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
          //覆盖原有value 
          V oldValue = e.value; 
          e.value = value; 
          e.recordAccess(this); 
          return oldValue; 
      } 
  } 
  // 没有在相同hash值的链表中找到key相同的节点 
  modCount++; 
  addEntry(hash, key, value, i); // 在i位置对应的链表上添加一个节点 
  return null; 
} 

void addEntry(int hash, K key, V value, int bucketIndex) { 
    //如果数据大小已经超过阈值[16*0.75]并且数组对应的bucket不为空,则需要扩容 
    if ((size >= threshold) && (null != table[bucketIndex])) { 
        // 扩容2倍 
        resize(2 * table.length);  
        // key为null的时,hash值设为0 
        hash = (null != key) ? hash(key) : 0;  
        // 确定是哪一个链表(bucket下标) 
        bucketIndex = indexFor(hash, table.length);  
    } 
    createEntry(hash, key, value, bucketIndex); 
} 
//这里需要注意!!! 
//使用的是头插法 
void createEntry(int hash, K key, V value, int bucketIndex) { 
      Entry<K,V> e = table[bucketIndex]; 
      table[bucketIndex] = new Entry<>(hash, key, value, e); 
      size++; 
  } 
private static class Entry<K,V> implements Map.Entry<K,V> { 
    final int hash; 
    final K key; 
    V value; 
    Entry<K,V> next; 
    protected Entry(int hash, K key, V value, Entry<K,V> next) { 
        this.hash = hash; 
        this.key =  key; 
        this.value = value; 
        this.next = next; 
    } 
    //略 
    } 

六、HashMap在JDK8的源码分析

重要常量:

DEFAULT_INITIAL_CAPACITY: HashMap的默认容量,16 
MAXIMUM_ CAPACITY : HashMap的最大支持容量,2^30 
DEFAULT_LOAD_FACTOR: HashMap的默认加载因子0.75 
TREEIFY_THRESHOLD: Bucket中链表长度大于该默认值,转化为红黑树 

面试题:为什么不在HashMap快满的时候再扩?

尽量让数组出现链表的情况少一些

6.1 构造器

/** 
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity 
 * (16) and the default load factor (0.75). 
 */ 
public HashMap() { 
    // all other fields defaulted 
    //底层并没有创建长度为16的数组 
    this.loadFactor = DEFAULT_LOAD_FACTOR;  
} 

在JDK8中已经不是Entry数组了,而是Node数组

transient Node<K,V>[] table; 

6.2 put

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

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) 
        //首次调用或者长度为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; 
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k)))) 
            //hash值相等 
            e = p; 
        else if (p instanceof TreeNode) 
            //是否红黑树 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
        else { 
            //循环判断有没有hash相等的 
            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; 
                } 
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                    break; 
                p = e; 
            } 
        } 
        if (e != null) { // existing mapping for key 
        //替换 
            V oldValue = e.value; 
            if (!onlyIfAbsent || oldValue == null) 
                e.value = value; 
            afterNodeAccess(e); 
            return oldValue; 
        } 
    } 
    ++modCount; 
    if (++size > threshold) 
        resize(); 
    afterNodeInsertion(evict); 
    return null; 
} 
//当数组某个位置链表超过8时,且当前数组长度超过64时,做成红黑树 
final void treeifyBin(Node<K,V>[] tab, int hash) { 
    int n, index; Node<K,V> e; 
    //MIN_TREEIFY_CAPACITY=64 
    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 { 
            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); 
    } 
} 

七、LinkedHashMap的底层实现

LinkedHashMap 没有重写 put 和 putVal,而是重写了 putVal 中调用的 newNode 方法:

//专门用了一个数据结构 LinkedHashMap.Entry<K,V> 存储节点,并且存储了前一个和下一个元素 
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { 
    LinkedHashMap.Entry<K,V> p = 
        new LinkedHashMap.Entry<K,V>(hash, key, value, e); 
    linkNodeLast(p); 
    return p; 
} 
static 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); 
    } 
} 

本文地址:https://blog.csdn.net/qq_42098718/article/details/107697178