Assume m is a prime around 232. We compute a hash value of a very long key k usi

Question

Assume m is a prime around 232. We compute a hash value of a very long key k using the dot product, by splitting k into L 'characters', as explained in the slide, and then compute ( k^ai) mod m However we compute it by first computing the value s (-1 kiai) and then compute s mod m (a) Assume s is stored as a variable of type long int represented by 32 bits. How large should L be so there is a danger of overflow with s? (b) Repeat the question, but now s is stored as a long long int (64 bits) (c) It is reasonable to store a hash table that has m cells, for the value of m mentioned above, all in the main memory of your cellphone, or would you have to use paging? Assume each cell in the table contains 2 long long ints, each requires 64 bits.

Explanation / Answer

1)

For 32 bits long int the maximum possible value of S is 4294967295 (232-1). Which is the sum of L many characters.

One character need 8 bit, So for L we 32-8=24 bits.

So,

if L>224-1 than there is danger of overflow with s.

2)

For 64 bits long int the maximum possible value of S is 18446744073709551616 (264-1). Which is the sum of L many characters.

One character need 8 bit, So for L we 64-8=56 bits.

So,

if L>256-1 than there is danger of overflow with s.

3) If m is aroun 232 so we have aprox 4294967295 different value of hash value.

So there are 42949672958*64 bits required to store hash table. which very large for cellphone memory. So we would have to use paging.

Your comment is most welcome.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.