首页 > 代码库 > hashcode做任务切分
hashcode做任务切分
一共M个任务以及N个线程,我们需要将M个任务均匀地分配到N个线程。
假设各个任务有自己的任务id,简单的做法是i=id%N(i指分配到哪个线程处理)。
但如果任务id分布不均衡将导致任务的最终分配不均衡,为了解决这一问题,一个简单的方法是对任务id进行一个hashcode转换,使得转换后的值随机分布,即i=hashcode(id)%N。
下图是java string hashcode的代码,很简单,假设一个string=“ok”,那么对应的hashcode为(‘o’*31 + ‘b’)。
public int hashCode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; for (int i = 0; i < len; i++) { h = 31*h + val[off++]; } hash = h; } return h; }
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
s[i]是string的第i个字符,n是String的长度。那为什么这里用31,而不是其它数呢?
Effective Java :The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i
. Modern VMs do this sort of optimization automatically.
《Effective Java》是这样说的:之所以选择31,是因为它是个奇素数,如果乘数是偶数,并且乘法溢出的话,信息就会丢失,因为与2相乘等价于移位运算。使用素数的好处并不是很明显,但是习惯上都使用素数来计算散列结果。31有个很好的特性,就是用移位和减法来代替乘法,可以得到更好的性能:31*i==(i<<5)-i。现在的VM可以自动完成这种优化。
非常巧妙的方法,但是如果我们的线程数为31(即N=31)会产生什么问题呢?
i = hashcode(id)%N =(s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1])%31
取个极端情况, 假设有3个任务,id分别为“o1”、“o2”、“o3”,那么其映射的线程将都是i=‘o’,即没有实现我们将任务均匀切分的目的。
解决的方式有两个:1)不使用hashcode;2)避免将任务切分成31个