cyub.vip - Tink's Blog

Description: 一只船孤独地航行在海上,它既不寻求幸福,也不逃避幸福。它只是向前航行,底下是沉静碧蓝的大海,而头顶是金色的太阳

Example domain paragraphs

在基于哈希表实现的Map中一个常用技巧就是将哈希桶的数量设置为2的n次方,也就是 2 n 2^n 2 n ,此后通过取余操作定位key所在桶的位置可以转换成与运算。之所以将取余运算改成与运算,一方面这两者计算的结果是一样的,另外一方面是因为与运算具有更好的性能,因为与运算指令周期是小于取余运算的。Java中的 HashMap 和Go中 map 都使用到这个技巧。

基于哈希表实现的Map中的取余运算转换成与运算的技巧,用数学语言来表达:

对于正整数x, y,如果x为2的n次方,n为正整数,那么 y    %    x = y    &    ( x − 1 ) y\;\%\;x = y \;\&\; (x-1) y % x = y & ( x − 1 ) 表达式是成立的。