Code to Test Hash Code

Discussion:

(too old to reply)

Gohulan

2005-01-20 06:58:21 UTC

Here is a piece of code that prints out to a text file hashcodes of
randomly generated rational numbers. You can use excel to import the
file and then analyze the results. Currently it generates 1000 random
rational numbers but you can change the amount by changing the loop
variable.
---------------------------------------------------------------------

import java.util.Random;
import java.io.*;

public void setNumerator(int n) {
this.numerator = n;
}

public void setDenominator(int d) {
this.denominator = d;
}

public static void main(String[] args) throws IOException {

File fileName = new File("C:\\hashcodes.txt");
FileWriter out = new FileWriter(fileName);

Rational r = new Rational(0, 1);
Random rn = new Random();
Random rn2 = new Random();

for (int i = 0; i <= 1000; i++) {
r.setNumerator(rn.nextInt());
r.setDenominator(rn.nextInt());
out.write(r + "," + r.hashCode() + "\n");
System.out.println(r + "," + r.hashCode());

}

out.close();
}
------------------------------------------------------------------------

Cheers,
Gohulan.

prashant

2005-01-20 15:21:17 UTC

Permalink

The process used by Random class is :

public Random() { this(System.currentTimeMillis()); }

Two Random objects created within the same millisecond will have the same
sequence of random numbers.

Your implementation creates the 2 random objects, one after the other, and
the chances for the 2 objects created at the same time increase. Therefore
giving me 1,1 for rn,rn2 in most cases (maybe all cases but i am not sure).

This was my result when the 2 objects were created one after the other

1/1,5004

1/1,5004

1/1,5004

1/1,5004

1/1,5004

1/1,5004

1/1,5004

1/1,5004

1/1,5004

1/1,5004

1/1,5004

Since to solve the problem all you have to do is somehow increase the time,
all I did was create rn object first then some set of instructions and
finally create rn2.

File fileName = new
File("N:\\2A\\ECE250\\Project1\\Rational\\Outp1.txt");

Random rn = new Random(); // Creating rn
FileWriter out = new FileWriter(fileName);// the something taking time

Random rn2 = new Random();// creating rn2

for (int i = 0; i <= 10; i++) {
Rational r = new Rational(rn.nextInt(16), rn2.nextInt(16));
out.write(r + "," + r.hashCode() + " \n");
}

out.close();

This was my result when the 2 objects were created after a short interval
(creating the FileWriter).

1/1 ,5004

15/7 ,75052

1/13 ,5016

18/25,90079

1/1 ,5004

3/5 ,15014

9/8 ,45035

25/12,125087

23/29,115098

15/16,75061

11/2 ,55035

I am not sure if what i just said is completely correct or not because this
explanation made the most sense to fix the problem in my case. So can
someone please clarify on why was I getting 1/1,5004 as all my results (the
loop count did not matter).

thanks

- Prashant

Post by Gohulan
Here is a piece of code that prints out to a text file hashcodes of
randomly generated rational numbers. You can use excel to import the
file and then analyze the results. Currently it generates 1000 random
rational numbers but you can change the amount by changing the loop
variable.
---------------------------------------------------------------------
import java.util.Random;
import java.io.*;
public void setNumerator(int n) {
this.numerator = n;
}
public void setDenominator(int d) {
this.denominator = d;
}
public static void main(String[] args) throws IOException {
File fileName = new File("C:\\hashcodes.txt");
FileWriter out = new FileWriter(fileName);
Rational r = new Rational(0, 1);
Random rn = new Random();
Random rn2 = new Random();
for (int i = 0; i <= 1000; i++) {
r.setNumerator(rn.nextInt());
r.setDenominator(rn.nextInt());
out.write(r + "," + r.hashCode() + "\n");
System.out.println(r + "," + r.hashCode());
}
out.close();
}
------------------------------------------------------------------------
Cheers,
Gohulan.

A slight change in the above would ensure that the random rationals are
stored in their lowest form (provided the constructor takes care of
reducing rationals).This will be extremely slow as GCDs of large numbers
public static void main(String[] args) throws IOException {
File fileName = new File("C:\\hashcodes.txt");
FileWriter out = new FileWriter(fileName);
Random rn = new Random();
Random rn2 = new Random();
for (int i = 0; i <= 1000; i++) {
Rational r = new Rational(rn.nextInt(), rn2.nextInt());
out.write(r + "," + r.hashCode() + "\n");
}
out.close();
}
Gohulan.

Gohulan

2005-01-20 17:21:15 UTC

Permalink

Post by prashant
public Random() { this(System.currentTimeMillis()); }
Two Random objects created within the same millisecond will have the same
sequence of random numbers.
Your implementation creates the 2 random objects, one after the other, and
the chances for the 2 objects created at the same time increase. Therefore
giving me 1,1 for rn,rn2 in most cases (maybe all cases but i am not sure).
This was my result when the 2 objects were created one after the other
1/1,5004
1/1,5004
1/1,5004
1/1,5004
1/1,5004
1/1,5004
1/1,5004
1/1,5004
1/1,5004
1/1,5004
1/1,5004
Since to solve the problem all you have to do is somehow increase the time,
all I did was create rn object first then some set of instructions and
finally create rn2.
File fileName = new
File("N:\\2A\\ECE250\\Project1\\Rational\\Outp1.txt");
Random rn = new Random(); // Creating rn
FileWriter out = new FileWriter(fileName);// the something taking time
Random rn2 = new Random();// creating rn2
for (int i = 0; i <= 10; i++) {
Rational r = new Rational(rn.nextInt(16), rn2.nextInt(16));
out.write(r + "," + r.hashCode() + " \n");
}
out.close();
This was my result when the 2 objects were created after a short interval
(creating the FileWriter).
1/1 ,5004
15/7 ,75052
1/13 ,5016
18/25,90079
1/1 ,5004
3/5 ,15014
9/8 ,45035
25/12,125087
23/29,115098
15/16,75061
11/2 ,55035
I am not sure if what i just said is completely correct or not because this
explanation made the most sense to fix the problem in my case. So can
someone please clarify on why was I getting 1/1,5004 as all my results (the
loop count did not matter).
thanks
- Prashant

That's strange. I am not sure why you got 1/1 for all of them. Here are
my sample results and they were reasonable (yeah I didn't limit the
range).I didn't also include a work around for cases when rn2.nextInt()
generates 0.

-38933287/1536695,1238428128
2071315257/1798021474,1782430199
-792235720/1188728403,-1946509801
1370830819/307312535,-329376430
-25390677/12404971,655716062
1855980557/948632825,-1295475666
-530376807/556109344,-1445295027
-206022549/406110436,-1622415845
-516789376/889797333,626389705
-804068634/1881235381,959396167
1915419621/1806961661,-193382022
71726804/71743275,355380891
259289219/1059573766,-867604483
726932605/87489058,102909131
265140887/292022954,-2127991339
1156500577/965269009,1379671562
-1900897520/108998537,-887239779
398442933/369208765,-1652384182
-855385205/452963898,1616402473
454848715/573405444,622853787
394301815/258926273,1404610312
739412933/471368553,1988854646
-200450947/1858445508,2015299381
-251467897/1406775361,2144978904
-694336358/511361293,399600963
-725779351/861269536,1885010781
-236199653/159916367,-1613078142
14987881/42858263,778916496
-479930400/857041993,923253357
2056348363/30273072,-1330805257

Gohulan

2005-01-20 17:25:57 UTC

Permalink

The best way to guarantee unique sequences is to provide your own seed
value for the generator.

Random rn = new Random(78523656);
Random rn2 = new Random(89563215);

Gohulan.

Adam Bertrand

2005-01-20 19:21:13 UTC

Permalink

You can also use the Math.random() method...though you'll have to
multiply it by the max integer value, and cast it as an int...

I have some code that generates x number of hashes, and stores them in
an array, in another array I store the rational, keepig the indices the
same.

Then, I sort the arrays using a shamelessly stolen quicksort algorithm
(author released it as open source, and it's for testing anyways...)

once sorted, you can more easily check for collisions, and the rationals
that caused them, as long as you modify BOTH arrays at the same time. IE
one operation is done to both arrays... It's all hopelessly
inefficient ^_^, but it's for testing, and it works, I think... Just
don't try to run it with more than 2 000 000 or 3 000 000 or so
Rationals...unless of course you have a crapload of memory. :)

-Adam

[CODE]
//Add this to main method:
System.out.println("\nHash Code Test Mk II");
int n = 100; //create 100 rationals
int[] a = new int[n];
Rational[] b = new Rational[a.length];
int rndNumber1;
int rndNumber2;
for(int i=0;i<a.length;i++)
{
rndNumber1 = (int)(Math.random()*2147483647)+1; //max int, and
avoid zeros.
rndNumber2 = (int)(Math.random()*2147483647)+1;
Rational rTmp = new Rational(rndNumber1, rndNumber2);
b[i]=rTmp;
a[i]=rTmp.hashCode();
}
sort(a, b);
int collisions = 0;
int match = 0;
for(int i=a.length-1;i>=1;i--)
{
if(a[i] == a[i-1])
{
collisions++;
System.out.println("Collision at index: " + i);
System.out.println("Hash Values: " + a[i] + " and " + a[i-1]);
System.out.println("Rational Values: " + b[i] + " and " + b[i-1]);
}
if(b[i].equals(b[i-1]))
{
match++;
System.out.println("Match at index: " + i);
System.out.println("Rational Values: " + b[i] + " and " + b[i-1]);
}
}
System.out.println("Number of Collisions:" + collisions);
System.out.println("Number of Matches:" + match);

//END MAIN CODE
//Code hereafter shamelessly stolen and tweaked a bit...
static void QuickSort(int a[], Rational b[], int lo0, int hi0) throws
RuntimeException
{
int lo = lo0;
int hi = hi0;
int mid;
int mid2;

if ( hi0 > lo0)
{

/* Arbitrarily establishing partition element as the midpoint of
* the array.
*/
mid = a[ ( lo0 + hi0 ) / 2 ];

// loop through the array until indices cross
while( lo <= hi )
{
/* find the first element that is greater than or equal to

* the partition element starting from the left Index.
*/
while( ( lo < hi0 ) && ( a[lo] < mid ) )
++lo;

/* find an element that is smaller than or equal to
* the partition element starting from the right Index.
*/
while( ( hi > lo0 ) && ( a[hi] > mid ) )
--hi;

// if the indexes have not crossed, swap
if( lo <= hi )
{
swap(a, lo, hi);
swap(b, lo, hi);

++lo;
--hi;
}
}

/* If the right index has not reached the left side of array
* must now sort the left partition.
*/
if( lo0 < hi )
QuickSort( a, b, lo0, hi );

/* If the left index has not reached the right side of array
* must now sort the right partition.
*/
if( lo < hi0 )
QuickSort( a, b, lo, hi0 );

}
}

private static void swap(int a[], int i, int j)
{
int T;
T = a[i];
a[i] = a[j];
a[j] = T;

}
private static void swap(Rational a[], int i, int j)
{
Rational T;
T = a[i];
a[i] = a[j];
a[j] = T;

}

public static void sort(int a[], Rational b[]) throws RuntimeException
{
QuickSort(a, b, 0, a.length - 1);
}
//END OF QUICKSORT METHODS

[/CODE]