文档章节

HashMap源码分析

V
 V丶zxw
发布于 10/21 22:14
字数 2275
阅读 19
收藏 0

HashMap源码分析

  1. // 类的继承实现关系
    // Map -> 内置Entry接口
    public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable {
    

1.字段

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

    /**
     * 最大容量,如果想隐式指定更高的值,则使用带两个参数的构造函数
     */
    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;
	// 可以对树进行树化的最小表容量。(否则,如果容器中的节点过多,则调整表的大小。)应至少为4 * TREEIFY_THRESHOLD,以避免调整大小和树化阈值之间的冲突。
	static final int MIN_TREEIFY_CAPACITY = 64;
	// 下一个要调整大小的大小值(容量*负载系数)
	// 如果table array尚未分配,这个字段保留数组初始容量或者为0
	int threshold;
	// 结构修改次数
 	transient int modCount;
	// hash表的负载因子
	final float loadFactor;
	// map中的键值映射数
	transient int size;
	// 保存缓存的entrySet().请注意,使用AbstractMap字段用于keySet()和values().
	transient Set<Map.Entry<K,V>> entrySet;
	// 该表在首次使用时初始化,并根据需要调整大小。 分配后,长度始终是2的幂。 
	transient Node<K,V>[] table;

2.构造方法

!-----------------! 
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;
        this.threshold = tableSizeFor(initialCapacity);
    }

!-----------------! 
  public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

!-----------------! 
 //构造一个列表,该列表包含指定集合的元素,其顺序由集合的迭代器返回。
 public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

!-----------------! 
public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

3.put方法

3.1 put(K,V)

// 末尾添加元素 
public V put(K key, V value) {
    	/ **
      	*实现Map.put和相关方法。
      	*
      	* @param hash hash for key
      	* @param key the key
      	* @param value放置的值
      	* @param onlyIfAbsent如果为true,请不要更改现有值
      	* @param evict,如果为false,则表处于创建模式。
      	* @return 返回上一个值,如果没有则返回null
      	* /            
        return putVal(hash(key), key, value, false, true);
    }

3.2 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

3.2.1put方法流程

-> 判断链表数组table是否为空

​ -> 调用resize方法进行初始化

if-> 判断p=(n-1)&hash位置是否为空

​ -> 直接赋值

else->判断该节点的hash和key或者key值是否相等

​ -> 直接覆盖该value

else->判断是否为树节点

else->for循环

​ ->判断该节点的下一个链表节点是否为空

​ ->直接赋值给next节点

​ ->判断链表节点数是否大于8

​ ->判断key和hash是否相等

​ ->判断e节点是否为空,获取旧值,覆盖新值

-> modCount++

-> 判断size是否大于临界值

​ ->扩容

-> 返回null

3.2.2resize 方法流程

->获取旧容量

->获取旧临界值

->定义新容量和新临界值

if->判断旧容量是否大于0

​ if->判断旧容量是否大于最大容量

​ else->判断扩容后容量是否小于最大容量并且旧容量是否大于默认容量,newThr = oldThr << 1

else->判断旧临界值是否大于0

​ ->新容量值=旧临界值

else->新容量=默认容量,新临界值=默认负载因子*默认容量

if->新临界值=0

​ ->ft=newCap*加载因子

->临界值=新临界值

->Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]

->table = newTab;

if->判断旧容量是否不为空

​ ->循环判断,j<旧容量

​ ->判断旧表该值是否不为空

​ ->判断下一个节点是否为空

​ ->newTab[e.hash & (newCap - 1)] = e;

​ ->判断是否为树节点

​ -> dowhile

->return newTab;

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是否为空 或者 长度是否为0
        if ((tab = table) == null || (n = tab.length) == 0)
            // 调用resize方法初始化
            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;
            // 判断hash与key是否相同或者key的值是否等于k
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 将节点p赋值给e
                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
                        p.next = newNode(hash, key, value, null);
                        // 判断是否大于树节点临界值
                        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;
                // LinkedHashMap的回调方法
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
    	// 修改次数+1
        ++modCount;
    	//  判断元素个数大小是否大于临界值
        if (++size > threshold)
            // 扩容
            resize();
    	//允许LinkedHashMap后处理的回调
        afterNodeInsertion(evict);
        return null;
    }

// 计算hash值
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

/ **
      *初始化或增加表大小。 如果为null,则分配
      *符合在现场阈值中保持的初始容量目标。
      *否则,因为我们使用的是二次幂扩展,所以
      *每个bin中的元素必须保持相同的索引或移动
      *在新表中具有两个偏移量的幂。
      *
      * @返回表格
      * /
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;
            }
            // 将新容量扩大为原来的两倍并小于最大容量并且旧容量大于默认容量
            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
            newCap = DEFAULT_INITIAL_CAPACITY;// 16	
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
        }
    	// 如果新临界值为空
        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"})
    	// 定义一个链表数组,长度为16
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    	// 将新数组赋值给table
        table = newTab;
    	// 如果旧table为空,则直接返回	
        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)
                        // 如果为空,则将该节点通过新容量的hash赋值
                        newTab[e.hash & (newCap - 1)] = e;
                    // 如果是否为树节点
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            // 将下个节点赋值给next
                            next = e.next;
                            // 如果hash值与旧容量与操作等于0
                            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;
    }

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

4.get方法

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

 final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
     	// 判断table是否为空并且长度大于0并且该hash节点不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
          	// 判断该key和hash是否相同  
            if (first.hash == hash && // always check first node
                ((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);
                // 循环指导key和hash相等
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
     return null;
    }

5.remove方法

  public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true, true) != null;
    }

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
    	// 判断table是否为空并且该索引位置是否为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            // 如果hash和key值相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            // 判断下一个节点是否为空
            else if ((e = p.next) != null) {
                // 判断是否为树节点
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    // 循环找到key和hash对应的值
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 如果node不为空
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

© 著作权归作者所有

V
粉丝 0
博文 4
码字总数 10093
作品 0
中山
程序员
私信 提问
手把手带你源码分析 HashMap 1.7

前言 HashMap 在 Java 和 Android 开发中非常常见 今天,我将带来 HashMap 的全部源码分析,希望你们会喜欢。 目录 1. 简介 类定义 3. 具体使用 3.1 主要使用API(方法、函数) 3.2 使用流程...

烂猪皮
2018/04/21
57
1
JDK1.8HashMap源码分析

HashMap和Hashtable的主要区别是: 1. Hashtable是线程安全,而HashMap则非线程安全,Hashtable的实现方法里面大部分都添加了synchronized关键字来确保线程同步,因此相对而言HashMap性能会高...

小小明童鞋
2018/10/16
87
2
JDK 1.7 HashMap原理及源码解析

简介 类定义 3. 具体使用 3.1 主要使用API(方法、函数) 3.2 使用流程 在具体使用时,主要流程是: 声明1个 HashMap 的对象 向 HashMap 添加数据(成对 放入 键 - 值对) 获取 HashMap 的某...

TonyStarkSir
2018/08/08
38
0
搞懂 HashSet & LinkedHashSet 源码以及集合常见面试题目

HashSet & LinkedHashSet 源码分析以及集合常见面试题目 经过上两篇的 HashMap 和 LinkedHashMap 源码分析以后,本文将继续分析 JDK 集合之 Set 源码,由于有了之前的 Map 源码分析的铺垫,S...

群星纪元
03/31
42
0
Java容器源码分析-HashMap vs TreeMap vs LinkedHashMap

这里我采用的分析方式是帖子博客加上自己翻看jdk源码。有些情况下写一些测试的算法小例子加深印象。我这里只描述一下自己的总结想法 上一篇文章我们研究了set接口下的几个容器,由于其Set集合...

贾浩v
2017/10/19
30
0

没有更多内容

加载失败,请刷新页面

加载更多

BigDecimal 去后面无用的0的方法

BigDecimal a=new BigDecimal("0.1000"); System.out.println(a.stripTrailingZeros().toPlainString());...

xiaodong16
20分钟前
5
0
JAVA--高级基础开发

[集合版双色球] 十二、双色球规则:双色球每注投注号码由6个红色球号码和1个蓝色球号码组成。红色球号码从1—33中选择;蓝色球号码从1—16中选择;请随机生成一注双色球号码。(要求同色号码...

李文杰-yaya
昨天
16
0
聊聊rocketmq broker的CONSUMER_SEND_MSG_BACK

序 本文主要研究一下rocketmq broker的CONSUMER_SEND_MSG_BACK CONSUMER_SEND_MSG_BACK rocketmq/common/src/main/java/org/apache/rocketmq/common/protocol/RequestCode.java public class......

go4it
昨天
3
0
API常见接口(下)

system类 StringBuilder和StringBuffer 包装类 1.System类 (java.lang包中) 提供了大量的静态方法,可以获取与系统相关的信息或系统级操作。 常用方法: public static long currentTimeMi...

Firefly-
昨天
4
0
MySQL系列:一句SQL,MySQL是怎么工作的?

对于MySQL而言,其实分为客户端与服务端。 服务端,就是MySQL应用,当我们使用net start mysql命令启动的服务,其实就是启动了MySQL的服务端。 客户端,负责发送请求到服务端并从服务端获取数...

杨小格子
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部