• 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

Hash Function

 
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I need a hash function to use in a program I'm writing. I know exactly how big the table needs to be (88,799). I need to store strings in the table, with strings as the keys for those elements being stored.

Basically I'm storing a list of names and passwords associated with those names. I need to be able to enter the name in the hash table and have it return the password. Security isn't an issue because this is a school project (we have to employ some weak encryption to the passwords before they are put in the hash table anyway). I am planning on implementing an externally chained hash table, but I'm having a hard time coming up with a good hash function. I've heard its good that I know exactly how big the table will be, so I can come up with a better function.

I'm planning on using an array for the table and storing a linked list in each location to deal with collisions.

Can anyone possibly point me in the right direction?
 
Ranch Hand
Posts: 1780
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
1. Was it a requirement not to use java.util.HashMap?
2. Are you allowed to use String's hashCode?
 
Greg Roberts
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
1. Was it a requirement not to use java.util.HashMap?

I believe we have to build our own hash table. The exact wording is "You will build an externally chained hash table of userids and passwords." He's also asking to detail how we came up with the load factor. The way this prof works, we'll have to write a custom hash table. I did just email him about it though. I'll post again as soon as I get a response.

2. Are you allowed to use String's hashCode?

We should be able to use String's hashCode.


Here's the URL for the project page:
Hashing Project
 
Jeff Albertson
Ranch Hand
Posts: 1780
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Greg Roberts:

2. Are you allowed to use String's hashCode?

We should be able to use String's hashCode.
[/URL]



Problem solved?
 
Greg Roberts
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Turns out we cannot use hashCode(). We have to build a hash table and hash function ourselves.
 
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How about an md5 or other standard hashing mechanism?
http://java.sun.com/j2se/1.5.0/docs/api/java/security/MessageDigest.html
 
Greg Roberts
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Jaap Vermeer:
How about an md5 or other standard hashing mechanism?
http://java.sun.com/j2se/1.5.0/docs/api/java/security/MessageDigest.html



We have to write our own hash function for this problem. One that will (hopefully) evenly distribute all 88,799 names across a hash table. Another problem is how big to make the hash table. The table doesn't need to be 88,799 long, because there will be linked lists to deal with collisions. I just need to figure out how big to make the table and what hash function to use to maximize efficiency.
 
Greg Roberts
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Does anybody here know how to implement a hash function specific like this one?
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Did you google "string hash function"? The first hit shows a couple of classics, and this looks like a great page with a lot of the theory that you'd find in an algorithms text.
 
Greg Roberts
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Isn't that what this forum is for? I'd rather get advice from you guys than reading what some yahoo put on the internet. I'd rather have discussion about different functions than copy and paste from a website.

I've been to both sites and looked at what they have to offer, but I'm not supposed to use an algorithm off the internet. I'm supposed to come up with an efficient algorithm specific to this project, not generic hash algorithms somebody else came up with. I'm looking for advice on ways to come up with project-specific algorithms.
 
Ernest Friedman-Hill
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Greg Roberts:
Isn't that what this forum is for?



Arguably, not so much. Maybe the "General Computing" forum down the list. In "real" Java programming, it's very uncommon to use anything but String.hashCode() to hash a String. Now, implementing hashCode() for other classes, that does come up, but even there, most of the time the solution is to compose the results of calling hashCode() on members.
 
Greg Roberts
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I totally understand what you're saying. But I'm not in what you would call a "real" Java programming situation. I'm still a student at a university. Their intention is for us to learn a little bit about hashing. In the learning process, they want us to design our own hash function to implement our own hash table. Which is why I am seeking advice on creating a custom hash function.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Regardless of whether this is a "real" programming situation, or merely theoretical, isn't it better to show up to a discussion with some context than empty handed?

At the very least, that algorithm that some "yahoo put on the internet" can be used as the straw-man, or to discuss a specific point. Open-ended discussions from scratch, has limited usefulness.

Henry
 
Greg Roberts
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I posted all the requirements that I had for the hash function. I tried to get it across that I had to write a custom hash function for the project. All I got was suggestions on built-in Java functions.

Really, let's just drop it. I got a hash function working that I didn't lift from some web site. Trial and error. And got no help from anybody here.

I don't want anybody to go to any trouble and help out a student anyway.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic