从零开始学习 Java:简单易懂的入门指南之HashMap及TreeMap源码解读(二十四)

简介: 从零开始学习 Java:简单易懂的入门指南之HashMap及TreeMap源码解读(二十四)


HashMap源码

1.看源码之前需要了解的一些内容
Node<K,V>[] table   哈希表结构中数组的名字
DEFAULT_INITIAL_CAPACITY:   数组默认长度16
DEFAULT_LOAD_FACTOR:        默认加载因子0.75
HashMap里面每一个对象包含以下内容:
1.1 链表中的键值对对象
    包含:  
      int hash;         //键的哈希值
            final K key;      //键
            V value;          //值
            Node<K,V> next;   //下一个节点的地址值
1.2 红黑树中的键值对对象
  包含:
      int hash;             //键的哈希值
            final K key;          //键
            V value;            //值
            TreeNode<K,V> parent;   //父节点的地址值
      TreeNode<K,V> left;   //左子节点的地址值
      TreeNode<K,V> right;  //右子节点的地址值
      boolean red;      //节点的颜色
2.添加元素
HashMap<String,Integer> hm = new HashMap<>();
hm.put("aaa" , 111);
hm.put("bbb" , 222);
hm.put("ccc" , 333);
hm.put("ddd" , 444);
hm.put("eee" , 555);
添加元素的时候至少考虑三种情况:
2.1数组位置为null
2.2数组位置不为null,键不重复,挂在下面形成链表或者红黑树
2.3数组位置不为null,键重复,元素覆盖
//参数一:键
//参数二:值
//返回值:被覆盖元素的值,如果没有覆盖,返回null
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);
}
//参数一:键的哈希值
//参数二:键
//参数三:值
//参数四:如果键重复了是否保留
//       true,表示老元素的值保留,不会覆盖
//       false,表示老元素的值不保留,会进行覆盖
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
      //定义一个局部变量,用来记录哈希表中数组的地址值。
        Node<K,V>[] tab;
    //临时的第三方变量,用来记录键值对对象的地址值
        Node<K,V> p;
    //表示当前数组的长度
    int n;
    //表示索引
        int i;
    //把哈希表中数组的地址值,赋值给局部变量tab
    tab = table;
        if (tab == null || (n = tab.length) == 0){
      //1.如果当前是第一次添加数据,底层会创建一个默认长度为16,加载因子为0.75的数组
      //2.如果不是第一次添加数据,会看数组中的元素是否达到了扩容的条件
      //如果没有达到扩容条件,底层不会做任何操作
      //如果达到了扩容条件,底层会把数组扩容为原先的两倍,并把数据全部转移到新的哈希表中
      tab = resize();
      //表示把当前数组的长度赋值给n
            n = tab.length;
        }
    //拿着数组的长度跟键的哈希值进行计算,计算出当前键值对对象,在数组中应存入的位置
    i = (n - 1) & hash;//index
    //获取数组中对应元素的数据
    p = tab[i];
        if (p == null){
      //底层会创建一个键值对对象,直接放到数组当中
            tab[i] = newNode(hash, key, value, null);
        }else {
            Node<K,V> e;
            K k;
      //等号的左边:数组中键值对的哈希值
      //等号的右边:当前要添加键值对的哈希值
      //如果键不一样,此时返回false
      //如果键一样,返回true
      boolean b1 = p.hash == hash;
            if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){
                e = p;
            } else if (p instanceof TreeNode){
        //判断数组中获取出来的键值对是不是红黑树中的节点
        //如果是,则调用方法putTreeVal,把当前的节点按照红黑树的规则添加到树当中。
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            } else {
        //如果从数组中获取出来的键值对不是红黑树中的节点
        //表示此时下面挂的是链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
            //此时就会创建一个新的节点,挂在下面形成链表
                        p.next = newNode(hash, key, value, null);
            //判断当前链表长度是否超过8,如果超过8,就会调用方法treeifyBin
            //treeifyBin方法的底层还会继续判断
            //判断数组的长度是否大于等于64
            //如果同时满足这两个条件,就会把这个链表转成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
          //e:        0x0044  ddd  444
          //要添加的元素: 0x0055   ddd   555
          //如果哈希值一样,就会调用equals方法比较内部的属性值是否相同
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
             break;
          }
                    p = e;
                }
            }
      //如果e为null,表示当前不需要覆盖任何元素
      //如果e不为null,表示当前的键是一样的,值会被覆盖
      //e:0x0044  ddd  555
      //要添加的元素: 0x0055   ddd   555
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null){
          //等号的右边:当前要添加的值
          //等号的左边:0x0044的值
          e.value = value;
        }
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //threshold:记录的就是数组的长度 * 0.75,哈希表的扩容时机  16 * 0.75 = 12
        if (++size > threshold){
       resize();
    }
    //表示当前没有覆盖任何元素,返回null
        return null;
    }

TreeMap源码

1.TreeMap中每一个节点的内部属性
K key;          //键
V value;        //值
Entry<K,V> left;    //左子节点
Entry<K,V> right;   //右子节点
Entry<K,V> parent;    //父节点
boolean color;      //节点的颜色
2.TreeMap类中中要知道的一些成员变量
public class TreeMap<K,V>{
    //比较器对象
    private final Comparator<? super K> comparator;
  //根节点
    private transient Entry<K,V> root;
  //集合的长度
    private transient int size = 0;
3.空参构造
  //空参构造就是没有传递比较器对象
   public TreeMap() {
        comparator = null;
    }
4.带参构造
  //带参构造就是传递了比较器对象。
  public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
5.添加元素
  public V put(K key, V value) {
        return put(key, value, true);
    }
参数一:键
参数二:值
参数三:当键重复的时候,是否需要覆盖值
    true:覆盖
    false:不覆盖
  private V put(K key, V value, boolean replaceOld) {
    //获取根节点的地址值,赋值给局部变量t
        Entry<K,V> t = root;
    //判断根节点是否为null
    //如果为null,表示当前是第一次添加,会把当前要添加的元素,当做根节点
    //如果不为null,表示当前不是第一次添加,跳过这个判断继续执行下面的代码
        if (t == null) {
      //方法的底层,会创建一个Entry对象,把他当做根节点
            addEntryToEmptyMap(key, value);
      //表示此时没有覆盖任何的元素
            return null;
        }
    //表示两个元素的键比较之后的结果
        int cmp;
    //表示当前要添加节点的父节点
        Entry<K,V> parent;
    //表示当前的比较规则
    //如果我们是采取默认的自然排序,那么此时comparator记录的是null,cpr记录的也是null
    //如果我们是采取比较去排序方式,那么此时comparator记录的是就是比较器
        Comparator<? super K> cpr = comparator;
    //表示判断当前是否有比较器对象
    //如果传递了比较器对象,就执行if里面的代码,此时以比较器的规则为准
    //如果没有传递比较器对象,就执行else里面的代码,此时以自然排序的规则为准
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else {
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }
            } while (t != null);
        } else {
      //把键进行强转,强转成Comparable类型的
      //要求:键必须要实现Comparable接口,如果没有实现这个接口
      //此时在强转的时候,就会报错。
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
        //把根节点当做当前节点的父节点
                parent = t;
        //调用compareTo方法,比较根节点和当前要添加节点的大小关系
                cmp = k.compareTo(t.key);
                if (cmp < 0)
          //如果比较的结果为负数
          //那么继续到根节点的左边去找
                    t = t.left;
                else if (cmp > 0)
          //如果比较的结果为正数
          //那么继续到根节点的右边去找
                    t = t.right;
                else {
          //如果比较的结果为0,会覆盖
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }
            } while (t != null);
        }
    //就会把当前节点按照指定的规则进行添加
        addEntry(key, value, parent, cmp < 0);
        return null;
    } 
   private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (addToLeft)
            parent.left = e;
        else
            parent.right = e;
    //添加完毕之后,需要按照红黑树的规则进行调整
        fixAfterInsertion(e);
        size++;
        modCount++;
    }
  private void fixAfterInsertion(Entry<K,V> x) {
    //因为红黑树的节点默认就是红色的
        x.color = RED;
    //按照红黑规则进行调整
    //parentOf:获取x的父节点
    //parentOf(parentOf(x)):获取x的爷爷节点
    //leftOf:获取左子节点
        while (x != null && x != root && x.parent.color == RED) {
      //判断当前节点的父节点是爷爷节点的左子节点还是右子节点
      //目的:为了获取当前节点的叔叔节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
        //表示当前节点的父节点是爷爷节点的左子节点
        //那么下面就可以用rightOf获取到当前节点的叔叔节点
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
          //叔叔节点为红色的处理方案
          //把父节点设置为黑色
                    setColor(parentOf(x), BLACK);
          //把叔叔节点设置为黑色
                    setColor(y, BLACK);
          //把爷爷节点设置为红色
                    setColor(parentOf(parentOf(x)), RED);
          //把爷爷节点设置为当前节点
                    x = parentOf(parentOf(x));
                } else {
          //叔叔节点为黑色的处理方案
          //表示判断当前节点是否为父节点的右子节点
                    if (x == rightOf(parentOf(x))) {
            //表示当前节点是父节点的右子节点
                        x = parentOf(x);
            //左旋
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
        //表示当前节点的父节点是爷爷节点的右子节点
        //那么下面就可以用leftOf获取到当前节点的叔叔节点
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
    //把根节点设置为黑色
        root.color = BLACK;
    }

Tip:

1.TreeMap添加元素的时候,键是否需要重写hashCode和equals方法?

此时是不需要重写的。

2.HashMap是哈希表结构的,JDK8开始由数组,链表,红黑树组成的。既然有红黑树,HashMap的键是否需要实现Compareable接口或者传递比较器对象呢?

不需要的。

因为在HashMap的底层,默认是利用哈希值的大小关系来创建红黑树的

3.TreeMap和HashMap谁的效率更高?

如果是最坏情况,添加了8个元素,这8个元素形成了链表,此时TreeMap的效率要更高

但是这种情况出现的几率非常的少。

一般而言,还是HashMap的效率要更高。

4.你觉得在Map集合中,java会提供一个如果键重复了,不会覆盖的put方法呢?

此时putIfAbsent本身不重要。

传递一个思想:

代码中的逻辑都有两面性,如果我们只知道了其中的A面,而且代码中还发现了有变量可以控制两面性的发生。

那么该逻辑一定会有B面。

习惯:

boolean类型的变量控制,一般只有AB两面,因为boolean只有两个值

int类型的变量控制,一般至少有三面,因为int可以取多个值。

5.三种双列集合,以后如何选择?

HashMap LinkedHashMap TreeMap

默认:HashMap(效率最高)

如果要保证存取有序:LinkedHashMap

如果要进行排序:TreeMap

后记
👉👉💕💕美好的一天,到此结束,下次继续努力!欲知后续,请看下回分解,写作不易,感谢大家的支持!! 🌹🌹🌹

相关文章
|
3天前
|
运维 Java
Java版HIS系统 云HIS系统 云HIS源码 结构简洁、代码规范易阅读
云HIS系统分为两个大的系统,一个是基层卫生健康云综合管理系统,另一个是基层卫生健康云业务系统。基层卫生健康云综合管理系统由运营商、开发商和监管机构使用,用来进行运营管理、运维管理和综合监管。基层卫生健康云业务系统由基层医院使用,用来支撑医院各类业务运转。
22 5
|
4天前
|
JavaScript Java 测试技术
基于Java的电影评论系统的设计与实现(源码+lw+部署文档+讲解等)
基于Java的电影评论系统的设计与实现(源码+lw+部署文档+讲解等)
19 0
|
4天前
|
JavaScript Java 测试技术
基于Java的在线日语培训平台的设计与实现(源码+lw+部署文档+讲解等)
基于Java的在线日语培训平台的设计与实现(源码+lw+部署文档+讲解等)
21 0
|
4天前
|
JavaScript Java 测试技术
基于Java的同城蔬菜配送管理系统的设计与实现(源码+lw+部署文档+讲解等)
基于Java的同城蔬菜配送管理系统的设计与实现(源码+lw+部署文档+讲解等)
10 0
|
4天前
|
JavaScript Java 测试技术
基于Java的心理预约咨询管理系统的设计与实现(源码+lw+部署文档+讲解等)
基于Java的心理预约咨询管理系统的设计与实现(源码+lw+部署文档+讲解等)
20 0
基于Java的心理预约咨询管理系统的设计与实现(源码+lw+部署文档+讲解等)
|
4天前
|
JavaScript Java 测试技术
基于Java的税务门户网站的设计与实现(源码+lw+部署文档+讲解等)
基于Java的税务门户网站的设计与实现(源码+lw+部署文档+讲解等)
3 0
|
4天前
|
JavaScript Java 测试技术
基于Java的高校毕业生就业管理系统的设计与实现(源码+lw+部署文档+讲解等)
基于Java的高校毕业生就业管理系统的设计与实现(源码+lw+部署文档+讲解等)
17 0
基于Java的高校毕业生就业管理系统的设计与实现(源码+lw+部署文档+讲解等)
|
4天前
|
JavaScript Java 测试技术
基于Java的家纺用品销售管理系统的设计与实现(源码+lw+部署文档+讲解等)
基于Java的家纺用品销售管理系统的设计与实现(源码+lw+部署文档+讲解等)
15 0
|
4天前
|
JavaScript Java 测试技术
基于Java的教务管理系统的设计与实现(源码+lw+部署文档+讲解等)
基于Java的教务管理系统的设计与实现(源码+lw+部署文档+讲解等)
19 0
|
4天前
|
JavaScript Java 测试技术
基于Java的西安旅游管理系统的设计与实现(源码+lw+部署文档+讲解等)
基于Java的西安旅游管理系统的设计与实现(源码+lw+部署文档+讲解等)
16 0