my dog learned polymorphism*
The moose likes Java in General and the fly likes Hash Function Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Hash Function" Watch "Hash Function" New topic
Author

Hash Function

Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
Posts: 72
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?


Greg Roberts<br />CIS Student<br />University of West Florida
Jeff Albertson
Ranch Hand

Joined: Sep 16, 2005
Posts: 1780
1. Was it a requirement not to use java.util.HashMap?
2. Are you allowed to use String's hashCode?


There is no emoticon for what I am feeling!
Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
Posts: 72
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

Joined: Sep 16, 2005
Posts: 1780
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

Joined: Feb 05, 2005
Posts: 72
Turns out we cannot use hashCode(). We have to build a hash table and hash function ourselves.
Jaap Vermeer
Greenhorn

Joined: Apr 04, 2006
Posts: 16
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

Joined: Feb 05, 2005
Posts: 72
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

Joined: Feb 05, 2005
Posts: 72
Does anybody here know how to implement a hash function specific like this one?
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

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.


[Jess in Action][AskingGoodQuestions]
Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
Posts: 72
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
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

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

Joined: Feb 05, 2005
Posts: 72
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.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18553
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
Posts: 72
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Hash Function
 
Similar Threads
If two different objects have same hashcode, how HashMap will retrieve these two objects?
Problem with hashcode etc
Prototype and script.aculo.us ToC
How can I set variable in backing bean directly from jspx page?
Hash Tables