10 Replies - 2282 Views - Last Post: 23 April 2011 - 08:51 PM Rate Topic: -----

#1 Zargoon  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 52
  • Joined: 28-November 10

How does java's .hashCode() work and is Wiess hash faster?

Posted 22 April 2011 - 06:27 PM

Hello all,

I am working on a project where I use a hash table that uses a Wiess hash that I wrote. The program is graded on performance, so my question is this--is my own Wiess hash faster than java's built in hash code generator?

The positions have to be completely unique, as collisions are not an issue. Any ideas on what the fastest hash function I could write would be?
Is This A Good Question/Topic? 0
  • +

Replies To: How does java's .hashCode() work and is Wiess hash faster?

#2 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 2006
  • View blog
  • Posts: 4,171
  • Joined: 11-December 07

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 22 April 2011 - 06:40 PM

I don't know what a Wiess hash is but can't you time your entire application running wiess hashing then java hashing?

Generally you can't 100% guarantee no collisions. If you store 100 items in a hashtable of size 100 you would be very lucky to get no collisions!
Was This Post Helpful? 0
  • +
  • -

#3 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 22 April 2011 - 07:42 PM

View PostZargoon, on 22 April 2011 - 08:27 PM, said:

Hello all,

I am working on a project where I use a hash table that uses a Wiess hash that I wrote. The program is graded on performance, so my question is this--is my own Wiess hash faster than java's built in hash code generator?

Would seriously doubt about it or you would have a job at Sun Oracle engineering :)
Was This Post Helpful? 0
  • +
  • -

#4 Zargoon  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 52
  • Joined: 28-November 10

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 22 April 2011 - 07:49 PM

Is it really that difficult to get a hash function that only produces unique values? Right now I'm using java's hash function and it doesn't seem to give me any duplicates..... could this be because I'm simply never filling up the whole table?
Was This Post Helpful? 0
  • +
  • -

#5 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 22 April 2011 - 08:07 PM

View PostZargoon, on 22 April 2011 - 09:49 PM, said:

Right now I'm using java's hash function

Which one ?
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10574
  • View blog
  • Posts: 39,151
  • Joined: 27-December 08

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 22 April 2011 - 09:10 PM

The Java hashCode() is designed to return unique values for Objects where their equals() methods return false. So contrapositively, if a.equals©, then a.hashCode().equals(c.hashCode()). When hashCode() isn't overridden in child classes of Object, then the Object hashCode() method is used, which returns memory addresses. That's why you are seeing the unique values.

From what I've found from Googling, Weiss is either your professor or the author of your textbook, I'm assuming. I've never heard of him before, and I'm betting he's using an existing hash function. At the undergraduate level, I can't imagine a textbook or professor having you all work with brand-new hash functions for this project.

@cfoley: There are perfect hash functions. :)
Was This Post Helpful? 1
  • +
  • -

#7 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 22 April 2011 - 09:17 PM

View Postmacosxnerd101, on 22 April 2011 - 11:10 PM, said:

textbook, I'm assuming. I've never heard of him before, and I'm betting he's using an existing hash function.

lol :)
Was This Post Helpful? 0
  • +
  • -

#8 Zargoon  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 52
  • Joined: 28-November 10

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 22 April 2011 - 09:19 PM

Our professor just taught us to use a hash called Weiss Hash, which just uses the ascii value of strings to generate a unique hash table code. Here it is:


    public int hash(String item) {
		int hashVal = 0;
		for (int i = 0; i < item.length(); i++)
			hashVal = (hashVal * 128 + item.charAt(i));
		return Math.abs(hashVal % array.length);
	}


It doesn't seem to always work though, which is what caused me to start using java's hash function in the first place....

This post has been edited by Zargoon: 22 April 2011 - 09:20 PM

Was This Post Helpful? 0
  • +
  • -

#9 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 22 April 2011 - 09:25 PM

Kind of a primitive hashing algorithm (like a checksum compared to a CRC) but don't see why it wouldn't work in your context.
Was This Post Helpful? 0
  • +
  • -

#10 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 2006
  • View blog
  • Posts: 4,171
  • Joined: 11-December 07

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 23 April 2011 - 01:13 AM

Oh yeah I agree there are perfect hash functions. But they still don't guarantee no collisions in your table see my example of a full hash table.
Was This Post Helpful? 0
  • +
  • -

#11 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: How does java's .hashCode() work and is Wiess hash faster?

Posted 23 April 2011 - 08:51 PM

exactly what I said in my previous post
"a primitive hashing algorithm"

This algorithm dates from the middle 70's and is like a checksum
CRC are a lot better and are less collision prone
Depends how "efficient/effective" your teacher wants your code to be
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1