HashMap 源码解析

首先看一下树节点构造

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
        /**
         * Returns the key.
         *
         * @return the key
         */
        public K getKey() {
            return key;
        }
        /**
         * Returns the value associated with the key.
         *
         * @return the value associated with the key
         */
        public V getValue() {
            return value;
        }
        /**
         * Replaces the value currently associated with the key with the given
         * value.
         *
         * @return the value associated with the key before this method was
         *         called
         */
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
        }
        public int hashCode() {
            int keyHash = (key==null ? 0 : key.hashCode());
            int valueHash = (value==null ? 0 : value.hashCode());
            return keyHash ^ valueHash;
        }
        public String toString() {
            return key + "=" + value;
        }
    }

一个节点由key,value对(TreeMap),左子节点,右子节点,父亲节点,标志位color,红黑树只有2种颜色(red,black)组成。节点初始化的时候默认为Black。 树节点比较函数:

public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
        }

首先类型比较,然后key,value分别进行比较

原文发布于微信公众号 - 编程坑太多(idig88)

原文发表时间:2018-04-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

Q110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a hei...

29450
来自专栏深度学习思考者

二叉树的遍历、查找、插入以及删除

二叉树的主要存储方式是链接存储,标准存储结构也称为二叉链表。 二叉链表结点类的定义 struct Node{ Node *left, *right;...

409100
来自专栏用户画像

4.3.1 二叉树的遍历

所谓二叉树的遍历,是指按照某条搜索路径访问树中的每个结点,使得每个几点均被访问一次,而且仅被访问一次。

9520
来自专栏WindCoder

二叉树的动态链式存储实现—C语言

36610
来自专栏Android机动车

数据结构学习笔记——树(上)

之前一直介绍的是一对一的线性结构,可现实中还有多一对多的情况需要处理,这就是今天要介绍的一对多的数据结构——树。

9520
来自专栏猿人谷

二叉树的遍历——递归和非递归

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义...

21780
来自专栏书山有路勤为径

二叉查找树

二叉查找树是一种数据结构,它是具有以下性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 2.若右子数不空,则右子树上所有...

6720
来自专栏calmound

110Balanced Binary Tree

问题:判断二叉树是否为平衡二叉树 分析:树上的任意结点的左右子树高度差不超过1,则为平衡二叉树。          搜索递归,记录i结点的左子树高度h1和右子树...

30060
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

19340
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

12120

扫码关注云+社区

领取腾讯云代金券