1、HashMap计算下标的方法

计算下标源码

Node<K,V>[] tab; Node<K,V> p; int n, i; 
if ((tab = table) == null || (n = tab.length) == 0)
   n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) 
   tab[i] = newNode(hash, key, value, null);

源码中n为数组长度，i为插入位置下标
第四行 tab[i = (n - 1) & hash] 得知 下标 = 数组长度-1 位与 hash
值

2、为什么做 & 操作

2.1、假如用十进制思想实现

我们思考数学计算的方式通常以十进制思想，我们先按通常人思路讲解，随后再引出为什么HashMap用 & 计算。
假如HashMap创建长度为16的数组(默认创建方式长度确实为16，稍后详细介绍)，hash值为32位以内任意数

32位int范围为-2147483648 - 2147483647，将如此庞大的数据范围散列的存放在长度为16的数组中，我们想到的是取余。
例
14%16 = 14 14存放在14下标位
18%16 = 2 18存放在2下标位
32%16 = 0 32存放在0下标位
当然在HashMap中还存在碰撞解决，再此不做讨论

十进制的思想告诉我们，想要将hash值均匀的分布在固定大小的数组中，要用到取余计算下标

2.2、更加效率的&运算

我们知道计算机底层是二进制运算，直接用二进制&计算去模拟取余操作，能够增加计算效率

2.3、取余 与 位与(&) 运算之间的关联

上面我们提到 下标 = 数组长度-1 位与 hash值
而创建HashMap的数组长度为2ⁿ，假设数组长度=16，hash=100

16-1 的二进制 1111
100 的二进制 1100100
两者做&运算
0001111
&
1100100
我们可以发现由于0001111高位为0
事实上就是
1111
&
0100
取余结果为100（二进制）= 4，由于100%16=4，结果与取余结果相同

我们可以看到利用&运算时，hash值高位数据不参与运算，低位数据便是取余结果
为什么会这样呢？？？
首先回顾一下将二进制转换十进制
11111111 转换为十进制 128+64+32+16+8+4+2+1 = 255，二进制的1从高位到低位分别代表 128、64、32、16、8、4、2、1
每一位代表的数 = 前面所有位代表数的合 + 1；

2 = 1+1
4 = 2+1+1
8 = 4+2+1+1
16 = 8+4+2+1+1
、、、

我们再回过头看HashMap中计算下标的算法，i = (n-1) & hash,在n值为2的k次幂条件下。hash值高于n-1的位无论是1或0都是n的倍数，而低于n-1的位本身便是余数
假如n(数组长度)不为2的k次幂，以上结论不成立

2.4、假如不为2的k次幂

刚刚一直强调数组长度为2的k次幂，假如不符合这特定条件会怎样
计算（2的k次幂-1）的二进制

2-1 = 1
4-1 = 11
8-1 = 111
16-1 = 1111
32-1 = 11111

可以看出符合特定条件的n-1所有位都为1
前面也介绍了技术下标算法是hash的低位与n-1做&运算
假设hash = 0101或hash = 0100，计算两种情况的结果

例一
1111
&
0101
等于 0101

例二
1111
&
0100
等于 0100

例三
1100
&
0101
等于 0100

例四
1100
&
0100
等于 0100

可以看出例三例四hash值不同但结果相同，n-1二进制全是1的情况下做&运算更有辨识度，更能有效将数据散列开

3、总结

1、用二进制&运算完全可以替代取余运算并且这么做是为了提高计算机运算效率
2、只有限定数组长度为2的k次幂才能用&运算模拟取余运算
3、通过对n-1 &运算 辨识度分析，反向推论出取余是最好的散列手段，避免造成数据堆积

公司项目中领导要求数据库的一个字段用int类型的二进制表示多种状态
每个下标对应不同的状态,1表示正常0表示不正常
如7的二进制是111,则表示三个状态都正常6的二进制110表示第一个不正常,第二第三个都正常.
要查询第二个状态是正常的,直接sql也能查出.
如要查出第3位是正常所有记录

select * from tableName where (column >> (3-1)) & 1 = 1;

这个样表示的好处就是便于以后扩展,以后的状态有增减不用修改数据库.

package com.base;

/**
 * @Authro: QYF
 * @Time:2021/2/26 21:38
 */
public class BinaryDemo {
    public static void main(String[] args) {
        //整数
        int num = 18;
        //转成二进制
        String binary = Integer.toString(num, 2);
        //从低位算,获取第几位是否为1
        int index = 2;
        boolean flag = getStatusType(num, index);
        System.out.println(num + "的二进制为:" + binary + ",二进制第:" + index + "位为:" + (flag ? 1 : 0));

        //状态
        int status = 0;
        int result = updateStatusType(num, index, status);
        System.out.println(num + "的二进制为:" + binary + ",把第" + index + "位改成" + status);
        System.out.println(result + "的二进制为:" + Integer.toString(result, 2));
    }

    /**
     * 判断第几位是否为1
     * <p>
     * 如18的二进制为10010,要获取第3位,则右移(3-1)位得100,第2位变成第1位,这样就可以和&1,最低位为1返回1,为0则返回0
     *
     * @param num   整数
     * @param index 低位起第几位下标
     * @return
     */
    private static boolean getStatusType(int num, int index) {
        return (num >> (index - 1) & 1) == 1;
    }

    /**
     * @param num    整数
     * @param index  低位起第几位下标
     * @param status 要修改的状态
     * @return
     */
    private static int updateStatusType(int num, int index, int status) {
        if (status != 0 && status != 1) {
            throw new IllegalArgumentException();
        }
        if (status == 1) {
            //1向左移(index-1) 和10010 或
            return (1 << (index - 1)) | num;
        } else {
            //先判断原来是不是0,原来是0则直接返回
            if (!getStatusType(num,index)){
                return num;
            }
            //10010 - 1向左移(index-1)
            return num - (1 << (index - 1));
        }

    }

}

输出结果:

18的二进制为:10010,二进制第:2位为:1
18的二进制为:10010,把第2位改成0
16的二进制为:10000

题目描述

获取数字 num 二进制形式第 bit 位的值。注意：
1、bit 从 1 开始
2、返回 0 或 1
3、举例：2 的二进制为 10，第 1 位为 0，第 2 位为 1

示例1

输入

复制

128, 8

输出

复制

1

我的解答：

function valueAtBit(num, bit) {
    var str=num.toString(2);
    return str[str.length-bit];

 }

利用toString()函数，将数字转化为了二进制字符串，然后字符串长度和位的关系将其取出

其他解答：

function valueAtBit(num, bit) {

    return (num >> (bit -1)) & 1;

}

利用了移位操作，之前没有接触过这种解法，理解之后感觉相当简洁

以上面的示例分析，128,8-》1；

128->1000 0000；要想将第八位上的数字取出，可以将她移到第一位上，也即是向右移动7位变成0000 0001，怎样将第一位上的1拿出来呢，可以利用与操作，让0000 0001，与1（0000 0001）与，除了第一位上的数是它本身，其余位全部变成了0，这样就将第一位取了出来。

自己可以写个二进制数字分析下，如：1000 0000 第八位是1，要想将他移到第一位上，移动的就是bit-1位，之后让它和1与，这样就能将除了第一位之外的其他位上的数字置0，输出的就只有第一位上的数字，也即是我们需要的那个