[数据结构与算法] 浅谈Map源码

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 浅谈Map源码 -> 正文阅读

[数据结构与算法]浅谈Map源码

简介

在这里插入图片描述
Map接口：双列数据，存储key-value对的数据

HashMap：作为Map的主要实现类，线程不安全，效率高；可以存储key-value都为null
LinkedHashMap：HashMap的子类，在HashMap底层原理上，添加一对指针，指向前一个和后一个元素，对于频繁的遍历操作，效率高于HashMap。（遍历map元素是，可以按照添加顺序遍历）
TreeMap：保证按照添加的key-value对进行排序，实现遍历操作，考虑key的自然排序和定制排序。底层红黑树
Hashtable：作为古老的实现类，线程安全，效率低，不能存储key-value任意为null
Properties：Hashtable的子类，常用来处理配置文件，key-value都是String类型

一、HashMap底层实现原理描述

1. jdk7

Map map = new HashMap();实例化以后，底层创建长度为16的数组Entry[] table。
map.put(key1,value1);调用key1所在类的hashCode()方法计算哈希值出code。
此哈希值通过某种算法（code & (16 -1)），可以理解为取模，计算出在数组table中的存放位置（数组下标）
如果此位置的数据为空，则此时的key1-value1添加成功
如果此位置上的数据不为空，（意味着此位置上存在一个key2或者多个（单向链表形式）），比较哈希值
①如果hash值不相同，则肯定不是相同对象，添加成功。
②如果hash相同，则比较key1和key2的的equals()方法，返回false，添加成功。返回true，value1替换value2
③以上两种方式以单向链表的方式存储
新添加的元素放到数组中，指向原来的元素。（next = 原来数据）
默认扩容方式：扩容为原来的2倍，并将原有的数据复制过来
底层结构：数组+单向链表

2. jdk8

Map map = new HashMap();实例化以后，底层没有创建默认长度数组。
jdk8底层是Node[]数据，而非Entry；只是改了个名字。
底层结构：数组+单向链表+红黑树
扩容及红黑树：当某一个索引上的元素以单向链表形式存在数据 > 8 且当前数据长度 > 64时，此索引上的以单向链表形式的元素改为使用红黑树存储。

二、HashMap源码的重要常量

DEFAULT_INITIAL_CAPACITY：HashMap的默认容量，16
MAXIMUM_CAPACITY：HashMap的最大支持容量，2的30次方
DEFAULT_LOAD_FACTOR：Bucket中链表长度大于该默认值，转化为红黑树
UNTTREEIFY_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扩容和结构改变的次数
10.threshold：扩容的临界值 = 容量 * 填充因子
11.loadFacTor：填充因子

三、JDK7源码

1、Map map = new HashMap() 实例化

//HashMap的默认容量，16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//this方法，初始化HashMap为数组容量16，加载因子0.75
public HashMap(int initialCapacity, float loadFactor) {
	//容量小于0报错
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    //容量大于最大值，则赋值最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //加载因子小于0或者不是数字报错
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +  loadFactor);

    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}

2、put操作

public V put(K key, V value) {
	//如果table数组为空，则初始化Entry[]数据长度和临界值
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //如果key为null,在数组0索引下创建元素Entry,key为null，value = value
    if (key == null)  return putForNullKey(value);
    //通过key所在类hashCode方法，再通过默写位运算得的哈希值
    int hash = hash(key);
    //哈希值通过某种算法（hash & (16 -1)），可以理解为取模，计算出在数组table中的存放位置（数组下标）
    int i = indexFor(hash, table.length);
    //如果下标的数据为空则跳过for循环（此下标没值），添加成功，在addEntry中
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //（如果哈希值一样，equals也一直，则替换value）否则添加到链表中，在addEntry中
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //添加操作（数组或者链表）
    addEntry(hash, key, value, i);
    return null;
}

3、添加操作

void addEntry(int hash, K key, V value, int bucketIndex) {
	//如果数组中元素数量大于等于临界值 而且 本次添加的数据不在数组中而在链表中 则扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
    	//数组和临界值扩容为原来的2倍，将原来数据复制到新数组中
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        //从新计算下标
        bucketIndex = indexFor(hash, table.length);
    }
    //创建操作
    createEntry(hash, key, value, bucketIndex);
}

4、创建操作

//jdk7新添加元素会放到数组红，然后next指向原来的元素
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    //新创建Entry在数组中，e原来的元素放到新元素的next中
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

三、JDK8源码

1、Map map = new HashMap()

//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//只初始化加载因子，没有初始化数组
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

2、put操作

public V put(K key, V value) {
	//通过key所在类hashCode()和某些为运算符计算哈希值
    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;
    //table = Node[]，首次put进入此if，初始化数组
    if ((tab = table) == null || (n = tab.length) == 0)
    	//初始化操作
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
    	//哈希值通过某种计算得到下标值，获取数组下标没数据，则直接添加成功newNode
        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))))
        	//哈希值相同，equals也相同，替换value，这里先赋值e;后面添加Node会使用e
            e = p;
        else if (p instanceof TreeNode)
        	//如果是树类型，则使用红黑树存储
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        	//一个数据或者多个数据以单向链表存储
            for (int binCount = 0; ; ++binCount) {
            	//如果e的next有值，则证明链表的下一个还有值，一直循环到下一个没值，则到了链表的末端，添加到后面即可
                if ((e = p.next) == null) {
                	//将链表最后一个元素赋值本次添加Node对象元素
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    	//binCount循环的数（链表的长度+1） >  链表最大长度 -1
                    	//即链表长度>8  来确定扩容还是转为树（添加元素为空或者数据长度小于64扩容，否则转为红黑树）
                        treeifyBin(tab, hash);
                    break;
                }
                //上面说的哈希值相同，equals相同，替换
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //只有哈希和equals都相等，e才不为空，其他情况都为空
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //为linkedList预留实现方法，它去重写，hashmap这里为空实现
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //数组元素个数大于临界值，则扩容
    if (++size > threshold)  （）resize();
    afterNodeInsertion(evict);
    return null;
}

3、初始化及扩容

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) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //如果长度*2小于最大值，且长度大于等于16 则新数组和新临界值扩容2倍
        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 {               // zero initial threshold signifies using defaults
    	//数据赋值16，临界值为12
        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;
    //以下赋值旧数据都新数组中省略
	....
    return newTab;
}

四、HashMap方法

1、get()方法

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //数组不为空 且 元素个数大约0 且 通过哈希值计算下标获取数组的值不为空
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
    	//哈希值相同，equals也相同，则直接返回
        if (first.hash == hash && ((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 {
            	哈希值相同，equals也相同，则直接返回
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

2、keySet()方法

 public Set<K> keySet() {
     Set<K> ks = keySet;
     if (ks == null) {
     	 //ks获取到KeySet对象
         ks = new KeySet();
         keySet = ks;
     }
     return ks;
 }

final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (Node<K,V> e : tab) {
                for (; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}