• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Calculating hashcode in double hashing

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello,

I'm using double hashing functions in my hashtable.
I have two following hashfuctions.

public int hashFunction1(int key)
{
return key % arraysize;
}

public int hashFunction2(int key)
{
// Less than array size.
return 5 - key % 5 // returns StepSize
}

The question is that if I'm going to pass the key as String
containing URL (http://localhost/mypage.html) to e.g. WWW page,
how should I actually convert that string to int? I am not sure.

Function declaration would then be following:

public int hashFunction1(String key)
public int hashFunction2(String key)

Can anyone give advise?

Thanks!
 
Ranch Hand
Posts: 2937
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The question is that if I'm going to pass the key as String
containing URL (http://localhost/mypage.html) to e.g. WWW page,
how should I actually convert that string to int?


The most obvious solution would be to use the hashCode of your String to come up with the int key. I am curious, however -- are you doing this double-hashing for research purposes, or are you planning to achieve some performance gains by presumably reducing the clustering of the keys? If the latter, I have some serious doubts whether it will really help.
 
Alvin Amilo
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm doing this "double hashing" because I have to implement
a HashTable for both Java and C/C++. C/C++ environment does not support e.g. STL so, I can not use STL and Java's Hashtable class and it's methods
(or actually try to port in into C/C++) to make code that look same in both Java and C/C++ versions. That is the reason why I have to code it without
any classlibrary support.

I read from the book by Mark Allen Weiss (Data Structures and
Algorithm Analysin in Java) that in double hashing there are two hashing functions. The second hashing function should have rules below:
- HashTable size should be prime (count of buckets)
- Hash2 function could be following: Hash2(x) = R - (x mod R), with R a prime smaller than tablesize (count of buckets)

So, what I don't actually know is that if my key to HashTable is e.g. URL
string and I'm saving www pages into that HashTable, how should I calculate
key from URL like http://localhost/mypage.html?

That's why I'm interested in it.

So, if some one have code snippets or somethig that calculates
hashvalue using double hashing using Java(without using "too much" Java's Collection API) or C I'm very interested in it.

Thanks!
 
Alvin Amilo
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Jep, I had bug in my hash function, the part that converted string based key
to integer....
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic