hashmap扰动函数、黑红树

位运算

二进制

5转换位二进制:

​ 5 = 2^+2^0 ==> 101 然后高位补0 ==> 00000101

-5转为位二进制:

  1. 先算出二进制码101
  2. 然后高位补0:00000101
  3. 然后取反码(1变成0,0变成1):11111010
  4. 反码+1得到补码:11111011 (最终结果)

java 运算

相关方法

//System.out.println(Integer.toBinaryString(-1));
//System.out.println(Integer.parseInt("1101",2));
复制代码

左移( << )

5<<2

首先会将5转为2进制表示形式(java中,整数默认就是int类型,也就是32位):

0000 0000 0000 0000 0000 0000 0000 0101 然后左移2位后,低位补0

0000 0000 0000 0000 0000 0000 0001 0100 换算成10进制为20

右移( >> )

5>>2

首先会将5转为2进制表示形式(java中,整数默认就是int类型,也就是32位):

0000 0000 0000 0000 0000 0000 0000 0101 然后右移2位后,高位补0

000000 0000 0000 0000 0000 0000 0000 01 换算成10进制为1

无符号右移( >>> )

我们知道在Java中int类型占32位,可以表示一个正数,也可以表示一个负数。正数换算成二进制后的最高位为0,负数的二进制最高为为1(重点最高位【最左边的那位】为1)

例如 -5换算成二进制后为:

1111 1111 1111 1111 1111 1111 1111 1011

我们分别对5进行右移3位、 -5进行右移3位和无符号右移3位:

5>>3

首先会将5转为2进制表示形式

0000 0000 0000 0000 0000 0000 0000 0101 然后右移3位后,高位补0

0000 0000 0000 0000 0000 0000 0000 0000 换算成10进制为0

-5>>3

-5右移3位后结果为-1,-1的二进制为: 1111 1111 1111 1111 1111 1111 1111 1111 // (用1进行补位)

-5>>>3

-5无符号右移3位后的结果 536870911 换算成二进制: 0001 1111 1111 1111 1111 1111 1111 1111 // (用0进行补位)

小结:

通过其结果转换成二进制后,我们可以发现,正数右移,高位用0补,负数右移,高位用1补,当负数使用无符号右移时,用0进行部位(自然而然的,就由负数变成了正数了)

位与( & )

5&3

&就是按位与,1&1等于1,其他都是0(1&0,0&1,0&0)

5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101

3转换为二进制:0000 0000 0000 0000 0000 0000 0000 0011

按位与之后: 0000 0000 0000 0000 0000 0000 0000 0001 转化为10进制就是1

位或( | )

5|3

| 就是按位或,只要对应位置上有一个1,那就是1

5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101

3转换为二进制:0000 0000 0000 0000 0000 0000 0000 0011

按位或之后: 0000 0000 0000 0000 0000 0000 0000 0111 转化为10进制就是7

位异或( ^ )

5^3

简单的思考异或就是:异 和 或的结合,要上下不一样,结果为1,如果上下相同则为0

5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101

3转换为二进制:0000 0000 0000 0000 0000 0000 0000 0011

按位异或之后: 0000 0000 0000 0000 0000 0000 0000 0110 转化为10进制就是6

位非( ~ )

就是取反

~5

5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101

~5就是: 1111 1111 1111 1111 1111 1111 1111 1010 转化为10进制就是-6

hash扰动函数

理论上来说字符串的 hashCode 是⼀个int类型值,那可以直接作为数组下标了,且不会出现碰撞。但是这个hashCode 的取值范围是[-2147483648, 2147483647],有将近40亿的长度,谁也不能把数组初始化的这么大,内存也是放不下的。
我们默认初始化的Map大小是16个长度 DEFAULT_INITIAL_CAPACITY = 1 << 4 ,所以获取的Hash值并不能直接作为下标使用,需要与数组长度进行取模运算得到⼀个下标值,也就是我们上⾯做的散列列子。

那么,hashMap源码这里不只是直接获取哈希值,还进行了⼀次扰动计算, (h = key.hashCode())^ (h >>> 16) 。把哈希值右移16位,也就正好是自己长度的⼀半,之后与原哈希值做异或运算,这样就混合了原哈希值中的⾼位和低位,增大了随机性。计算方式如下图;

hash.webp

使用扰动函数就是为了增加随机性,让数据元素更加均衡的散列,减少碰撞。

黑红树

红黑树定义和性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质:

​ 性质1:每个节点要么是黑色,要么是红色。

​ 性质2:根节点是黑色。

​ 性质3:每个叶子节点(NIL)是黑色。

​ 性质4:每个红色结点的两个子结点一定都是黑色。

性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

旋转

**左旋:**对节点x进行左旋,意味着将“x的右孩子变成x的父亲”,而将“x原先的右孩子的左孩子变成x的右孩子”。即左旋中的“左”是指将别旋转的节点变成一个左节点。

**右旋:**对节点x进行右旋,意味着将“x的左孩子变成x的父亲,而将”x原先的左孩子的右孩子变成x的右孩子“。即右旋中的”右“是指将被旋转的节点变成一个右节点。

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        //父节点
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;    //左节点
        TreeNode<K,V> right;   //右节点
        //用来删除下一个节点用的,因此prev也就是上一个节点
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;  //是否位红色
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }   
   }
复制代码

红黑树插入的4种情形

  1. 新节点位于根节点,其没有父节点时,处理思路:将该节点直接设为黑色即可。

  2. 新节点的父节点已然是黑色时,处理思路:不用动,这已然是一颗红黑树。

  3. 父节点和叔节点都是红色时,处理思路:a.将父节点和叔节点设为黑色;b.将祖父节点设为红色;c.将祖父节点设为当前节点,并继续对新当前节点进行操作。

  4. 父节点是红色,叔节点不存在或是黑色时,又分如下四种情况:

    当前节点是父亲的左孩子,父亲是祖父的左孩子(Left-Left),处理思路:a.将祖父节点右旋;b.交换父节点和祖父节点的颜色。

    当前节点是父亲的右孩子,父亲是祖父的左孩子(Right-Left),处理思路:a.将父节点左旋,并将父节点作为当前节点; b.然后再使用Left Left情形。

    当前节点是父亲的右孩子,父亲是祖父的右孩子(Right-Right),处理思路:a.将祖父节点左旋;b.交换父节点和祖父节点的颜色。

    当前节点是父亲的左孩子,父亲是祖父的右孩子(Left-Right),处理思路:a.将父节点右旋,并将父节点作为当前节点; b.然后再使用Right Right情形。

    // 保证插入节点后,红黑树仍然是平衡的 
    static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
             //新插入的节点都为红色
            x.red = true;
           // xp是x的父节点,xpp是x的祖父节点,xppl是xpp的左子节点,xppr是xpp的右子节点
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                //情景1:如果x是根节点,则把它设为黑色,并返回根节点
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                 // 情景2:父节点是黑色的(不是红色就是黑色),或者父节点为根节点,就说明x是第二层节点,
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                // 如果父节点是祖父节点的左子节点
                if (xp == (xppl = xpp.left)) {
                    // 情景3:祖父节点的右侧孩子,也就是x的叔叔不为空,且为红色
                    if ((xppr = xpp.right) != null && xppr.red) {
                        //叔叔节点为黑
                        xppr.red = false;
                        //父节点为黑
                        xp.red = false;
                        //祖父节点为红
                        xpp.red = true;
                        //祖父节点设为当前节点,继续当前操作
                        x = xpp;
                    }
                    else {
                        //插入情景4:叔叔结点不存在或为黑结点
                        //插入情景4.2:插入结点是其父结点的右子结点,需要左旋
                        if (x == xp.right) {
                            //左旋,并把x替换为xp进行递归
                            root = rotateLeft(root, x = xp);
                            // x替换后修改xp和xpp
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        // 经过左旋x为左节点
                        // 插入情景4.1:插入结点是其父结点的左子结点
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                // 如果父节点是祖父节点的右子节点
                else {
                    // 情景3:左右都为红,也就是x的叔叔不为空,且为红色
                    if (xppl != null && xppl.red) {
                         //叔叔节点为黑
                        xppl.red = false;
                         //父节点为黑
                        xp.red = false;
                        //祖父节点为红
                        xpp.red = true;
                        //祖父节点设为当前节点,继续当前操作
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                            //右旋
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                         // 插入情景4.3:插入结点是其父结点的右子结点
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                //以祖父节点为支点左旋
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }
 
       //左旋 
       static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
           // pp是祖父结点;p是待旋转结点;r是p的右孩子结点;rl是r的左孩子结点
            TreeNode<K,V> r, pp, rl;
            //该节点不为null并且右节点不为null
            if (p != null && (r = p.right) != null) {
                  //因为是左旋,所以如果右节点的左节点如果不为null,则rl的根节点设为p
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                //如果左旋后的头节点为根节点,则根据红黑树的性质,颜色为黑色
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                //然后r的left是p,p的父节点是r
                r.left = p;
                p.parent = r;
            }
            return root;
        }

       static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }
复制代码

树化

      //把链表生成红黑树,返回头节点    
      final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
                next = (TreeNode<K,V>)x.next;
                x.left = x.right = null;
                //先设定 root为头节点,parent为null,根节点为黑色,
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    //遍历红黑树
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                         //如果当前树节点的hash > 链表节点的hash则dir值为-1
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);

                        TreeNode<K,V> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            //插入节点,并且不破坏红黑树的性质
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            //设置头节点
            moveRootToFront(tab, root);
        }
复制代码

参考资料

www.cnblogs.com/ylxn/p/1010… 红黑树源码分析

www.cnblogs.com/aspirant/p/… 红黑树原理以及插入、删除算法 附图例说明

blog.csdn.net/qq_27788177… HashMap 源码分析 -- 红黑树

小傅哥的第 4 HashMap 扰动函数