首页 > 代码库 > 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个