|
hi! I was wondering, if anyone would be kind enough to help me with my task (source below). I have to implement a multiplicative method of hashing in Java using only 2 shifts and integer multiplication. The thing is, that when i try to do it according to Knuth, it won`t work, beacause java has only the signed int-type. Ok, it could work (a bit worse, but still), wenn I would choose w = 31, the function then returns the results that are |abs| <= m. The thing is, that they do vary in sign (Example: Let m = 1024. then hash-function (with w=31) returns 23,32,345,-234,1023,-984...).
what should i do?! Is there perhaps a way one could implement it with w=31?
static double A =(Math.sqrt(5)-1)/2; //Knuth`s choise :)
static int w = 32; //anzahl von bits per int
static int s =1327217884;// s = A * 2^w = 2654435769;
// won`t compile unless w = 31
static int p = 10; //m = 2^p
public static int hash(int key){
int x = key*s; //integer multiplikation
return x >> (w-p);} |
