【转】Java 位运算处理

发表于 | 阅读次数：

位移动运算符

<< 表示左移，左移一位表示原来的值乘 2。

例如：3 << 2

  1. 把 3 转换为二进制数字 0000 0000 0000 0000 0000 0000 0000 0011，
  2. 把该数字高位（左侧）的两个零移出，其他的数字都朝左平移 2 位，
  3. 在低位（右侧）的两个空位补零。则得到的最终结果是 0000 0000 0000 0000 0000 0000 0000 1100，转换为十进制是 12。

同理，>>表示右移，右移一位表示除 2。

还有一种 >>> 叫无符号右移：

它的通用格式如：value >>> num，num 指定要移位值 value 移动的位数。

无符号右移的规则只记住一点：忽略了符号位扩展，0 补最高位。

无符号右移运算符 >>> 只是对 32 位和 64 位的值有意义。

位运算

位运算符包括:　与（&）、非（~）、或（|）、异或（^）

  • &：当两边操作数的位同时为 1 时，结果为 1，否则为 0。如 1100&1010=1000
  • | ：当两边操作数的位有一边为 1 时，结果为 1，否则为 0。如 1100|1010=1110
  • ~：0 变 1，1 变 0
  • ^：两边的位不同时，结果为 1，否则为 0. 如 1100^1010=0110

位运算与位移动运行符的一个场景

HashMap 的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下 HashMap 存数据的基本流程：

1，当调用 put(key,value)时，首先获取 key 的 hashcode，int hash = key.hashCode();

2，再把 hash 通过一下运算得到一个 int h：

1
2
hash ^= (hash >>> 20) ^ (hash >>> 12); 
int h = hash ^ (hash >>> 7) ^ (hash >>> 4);

为什么要经过这样的运算呢？这就是 HashMap 的高明之处。

先看个例子，一个十进制数 32768(二进制 1000 0000 0000 0000)，经过上述公式运算之后的结果是 35080(二进制 1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字 61440(二进制 1111 0000 0000 0000)，运算结果是 65263(二进制 1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。

3，得到 h 之后，把 h 与 HashMap 的承载量（HashMap 的默认承载量 length 是 16，可以自动变长。在构造 HashMap 的时候也可以指定一个长度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比 length 小的正数，我们把这个值叫做 index。其实这个 index 就是索引将要插入的值在数组中的位置。第 2 步那个算法的意义就是希望能够得出均匀的 index，这是 HashTable 的改进，HashTable 中的算法只是把 key 的 hashcode 与 length 相除取余，即 hash % length，这样有可能会造成 index 分布不均匀。还有一点需要说明，HashMap 的键可以为 null，它的值是放在数组的第一个位置。

4，我们用 table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是 HashMap 内部定义的一个类 Entity， 基本结构它包含三个类，key，value 和指向下一个 Entity 的 next），没有的话就创建一个 Entity<K,V> 对象，在 table[index]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的 key，有的话用新的 value 替 换老的 value；如果没有，则在 table[index]插入该 Entity，把原来在 table[index]位置上的 Entity 赋值给新的 Entity 的 next，这样插入结束。

文章转载自：https://www.cnblogs.com/highriver/archive/2011/08/15/2139600.html

相关文章