hash tables: multiplicative method with non-binary keys

I'm trying to create a hash table and use the multiplicative method as a collision resolution. Our convention for the conversion of string data to numeric key is: a=01, b=02, c=03... So if the input to the table is "easy", the corresponding numeric key is 05011925 or 5011925. I've done research on the multiplicative method for collision resolution, but all sources present the process with the assumption that the numeric key is expressed in binary digits. The problem is we haven't covered bitwise operations. The help I need from you is in "translating" the following statements (which explains multiplicative method with binary numeric keys) into statements which explains the process on non-binary keys i.e. without the bitwise operations which we haven't covered yet.
The process is as follows:
1. Set all bits to the left of the imaginary radix point (of the binary key) to zero.
2. Shift left p bits (where p is log to base 2 of the size of the table) e.g. shift left 5 bits if the size of the table is 32.
3. Set the rightmost of the p bits to 1 (to make sure that h(k) is odd).

Quote:

---

Originally Posted by chickenandfries

I'm trying to create hash tables and use the multiplicative method as a collision resolution. Our convention for the conversion of string data to numeric key is: a=01, b=02, c=03... So if the input to the table is "easy", the corresponding numeric key is 05011925 or 5011925. I've done research on the multiplicative method for collision resolution, but all sources present the process with the assumption that the numeric key is expressed in binary digits. The problem is we haven't covered bitwise operations. The help I need from you is in "translating" the following statements (which explains multiplicative method with binary numeric keys) into statements which explains the process on non-binary keys i.e. without the bitwise operations which we haven't covered yet.
The process is as follows:
1. Set all bits to the left of the imaginary radix point (of the binary key) to zero.
2. Shift left p bits (where p is log to base 2 of the size of the table) e.g. shift left 5 bits if the size of the table is 32.
3. Set the rightmost of the p bits to 1 (to make sure that h(k) is odd).

---

1. You'll have to first tell us how you set the "imaginary radix point (of the binary key)". Is that supposed to go in front of the entire number, somewhere in the middle, or what. (I'm guessing it's supposed to go in front of the entire number, so you get 0.05011925 (notice that beginning zero matters again).)

2. This step has actually gone full circle. The point is to multiply by the size of the table, i.e., x*= 32. In the old days, people didn't trust their compilers to do that efficiently (with bit shifts), so they did x <<= 5 instead. Nowadays, people trust their compilers, so they do x*= 32 again (because it says what you mean, saving confusion).

3. You add 1 if its even and don't if it isn't.

Quote:

---

Originally Posted by tabstop

The point is to multiply by the size of the table, i.e., x*= 32.

---

Multiply what by 32? the key?

Quote:

---

Originally Posted by chickenandfries

Multiply what by 32? the key?

---

The magic number from step 1 (remember step 1? it comes right before step 2?) which you haven't told us what it supposed to be yet.

Quote:

---

Originally Posted by tabstop

1. You'll have to first tell us how you set the "imaginary radix point (of the binary key)". Is that supposed to go in front of the entire number, somewhere in the middle, or what. (I'm guessing it's supposed to go in front of the entire number, so you get 0.05011925 (notice that beginning zero matters again).)

---

The process I posted is for producing the secondary hash function to resolve collision. Before that is the process of producing the primary hash function; That could be the reason why the 1st step is confusing. Here is what comes before the process I posted first. Accoding to Knuth:
Take theta to be I/w where w is the word size of the computer (for instance, 2^32) and I is an integer relatively prime to w. Multiply K by I to obtain a 2w-bit product in which the lower w bits contain the fractional part of the product K*theta, that is, K*theta mod1.

Okay. So you need to choose w and I (or theta and w, I suppose). There's a bit of an inconsistency here, since w went from being 2^32 to just 32. (If that's really in Knuth, hurry and get the $2.56!)

But anyway, that's telling you you want the remainder (the fractional part) when you divide by 2^w, so take the remainder of dividing (K*I) by 2^w. (Again, Knuth is going to assume you're programming on the bare metal, but we've got modulus built into the language! Exciting!)

Quote:

---

Originally Posted by tabstop

Nowadays, people trust their compilers, so they do x*= 32 again (because it says what you mean, saving confusion).

---

Why is "x <<= 5" less indicative of what I mean than "x *= 32" ?

Quote:

---

Originally Posted by brewbuck

Why is "x <<= 5" less indicative of what I mean than "x *= 32" ?

---

I have to think of 2^5 = 32, plus there's no way in heck I've got "32" in my code in place of "number_of_buckets" or at least #define SIZE 32. So 5 just sort of magically appears, and if 32 ever changes you have to remember to change 5 too. (And if I want to compute 5, I get the marvelous looking "x <<= (int)log2(SIZE)", which is just getting silly.) Plus, I don't know where we're going with this, but we might be able to apply this when the number of buckets isn't a power of 2.

Quote:

---

Originally Posted by tabstop

Okay. So you need to choose w and I (or theta and w, I suppose). There's a bit of an inconsistency here, since w went from being 2^32 to just 32. (If that's really in Knuth, hurry and get the $2.56!)

But anyway, that's telling you you want the remainder (the fractional part) when you divide by 2^w, so take the remainder of dividing (K*I) by 2^w. (Again, Knuth is going to assume you're programming on the bare metal, but we've got modulus built into the language! Exciting!)

---

Wait, I'm kinda confused. How do I choose w? Put in another way, how do I know the word size of the computer?
Another thing, to generate the secondary hash function for double hashing, I need to take the reaminder of (K*I)/(2^w). Is this what you mean?

Quote:

---

Originally Posted by tabstop

so take the remainder of dividing (K*I) by 2^w.

---

Quote:

---

Originally Posted by chickenandfries

Another thing, to generate the secondary hash function for double hashing, I need to take the reaminder of (K*I)/(2^w). Is this what you mean?

---

Looks like it.

Quote:

---

Originally Posted by chickenandfries

Wait, I'm kinda confused. How do I choose w? Put in another way, how do I know the word size of the computer?

---

32-bit or 64-bit? It gets a little weird/redundant here, since Knuth is assuming that you have direct access to the registers (that's how you'll get a twice-as-long answer to a multiply). If you choose w to be the sizeof(int), for example, then you won't need to (in fact, won't be able to) do the division, since 2^w won't be representable in an int. (But that's ok, since overflow/truncation will do the right thing; just make sure your variable is unsigned.)

Quote:

---

Originally Posted by tabstop

32-bit or 64-bit? It gets a little weird/redundant here, since Knuth is assuming that you have direct access to the registers (that's how you'll get a twice-as-long answer to a multiply). If you choose w to be the sizeof(int), for example, then you won't need to (in fact, won't be able to) do the division, since 2^w won't be representable in an int. (But that's ok, since overflow/truncation will do the right thing; just make sure your variable is unsigned.)

---

So w is just w=sizeof(int);?

Quote:

---

Originally Posted by chickenandfries

So w is just w=sizeof(int);?

---

I'm not really familiar with the method; technically a word these days is still 16 bits, but it appears that he wants it to be the "natural size of a number" which is sizeof(int). I would probably choose sizeof(int) based on what I've seen in the thread.

What does setting all bits to the left binary point to zero? What does it mean in "decimal language"?

That is decimal language. Set everything to the left of the decimal point to zero? What do you think that's going to mean?