using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace problem75
{
class Num
{
public Num(long a, long b, long c, long total)
{
this.a = a;
this.b = b;
this.c = c;
this.total = total;
}
public long a;
public long b;
public long c;
public long total;
public override bool Equals(object obj)
{
Num n = (Num)obj;
if (total == n.total)
{
if (c == n.c)
{
if (a == n.a && b == n.b)
return true;
if (b == n.a && a == n.b)
return true;
return false;
}
else
return false;
}
else
return false;
}
public override int GetHashCode()
{
//the hashcode must be the same for 3^2 + 4^2 = 5^2
//and 4^2 + 3 ^2 = 5^2.
//the hashcode must be the same for a + b and b + a
return (int)((a ^ 21) + (b ^ 21) + (c ^ 21));
}
}
class Program
{
static void Main(string[] args)
{
int[] arr = new int[1500001];
Hashtable hashT = new Hashtable();
HashSet<Num> hashset = new HashSet<Num>();
for (long m = 2; m < 1000; m++)
{
for (long n = 1; n < m; n++)
{
for (long k = 1; k < 100000000; k++)
{
long a = ((m * m) - (n * n)) * k;
long b = (2 * m * n) * k;
long c = ((m * m) + (n * n)) * k;
long total = a + b + c;
if (total >= 0 && total <= 1500000)
{
Num n2 = new Num(a, b, c, total);
if (hashset.Add(n2))
arr[total]++;
}
else
break;
}
}
}
int sum = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == 1)
sum++;
}
Console.WriteLine(sum);
}
}
}
Category Archives: HashCode
HashCode in C#
Another hashcode example
class Program
{
class Person
{
public Person(String fname, String lname)
{
this.fname = fname;
this.lname = lname;
}
String fname;
String lname;
public int hashCode()
{
return (fname.GetHashCode() * 1021) ^ lname.GetHashCode();
}
public bool equals(Object obj)
{
return this.fname.Equals(((Person)obj).fname) &&
this.lname.Equals(((Person)obj).lname);
}
}
class Point
{
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
int x;
int y;
public int hashCode()
{
return (x * 31) ^ y;
}
public bool equals(Object obj)
{
return x == ((Point)obj).x &&
y == ((Point)obj).y;
}
}
static char[] getLowerCase()
{
char[] temp = new char[26];
for (int i = 0; i < 26; i++)
temp[i] = (char)(i + 97);
return temp;
}
static char[] getUpperCase()
{
char[] temp = new char[26];
for (int i = 0; i < 26; i++)
temp[i] = (char)(i + 65);
return temp;
}
static String getName(char[] lower, char[] upper)
{
Random r = new Random();
StringBuilder sb = new StringBuilder();
int count = r.Next(10);
for (int j = 0; j < count; j++)
{
int index = r.Next(25);
if (j == 0)
sb.Append(upper[index]);
else
sb.Append(lower[index]);
}
return sb.ToString();
}
static void AnalyzePerson()
{
char [] lower = getLowerCase();
char [] upper = getUpperCase();
Hashtable table = new Hashtable();
Person []list = new Person[500000];
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for(int i = 0; i < 500000; i++)
{
String fname = getName(lower, upper);
String lname = getName(lower, upper);
Person p = new Person(fname, lname);
table.Add(p, i);
list[i] = p;
}
stopwatch.Stop();
Console.WriteLine("putting: " + stopwatch.ElapsedMilliseconds + " ms");
stopwatch.Restart();
for(int i = 0; i < 500000; i++)
{
Person p = list[i];
object o = table[p];
}
stopwatch.Stop();
Console.WriteLine("getting: " + stopwatch.ElapsedMilliseconds + " ms");
}
static void AnalyzePoint()
{
Hashtable table = new Hashtable();
Point []list = new Point[500000];
Random r = new Random();
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for(int i = 0; i < 500000; i++)
{
Point p = new Point(r.Next(50), r.Next(100));
table.Add(p, i);
list[i] = p;
}
stopwatch.Stop();
Console.WriteLine("putting: " + stopwatch.ElapsedMilliseconds + " ms");
stopwatch.Restart();
for(int i = 0; i < 500000; i++)
{
Point p = list[i];
object o = table[p];
}
stopwatch.Stop();
Console.WriteLine("getting: " + stopwatch.ElapsedMilliseconds + " ms");
}
static void Main(string[] args)
{
AnalyzePoint();
AnalyzePerson();
}
}
HashCode in Java
import java.util.Hashtable;
import java.util.Random;
public class HashCode {
static class Person
{
public Person(String fname, String lname) {
this.fname = fname;
this.lname = lname;
}
String fname;
String lname;
public int hashCode()
{
return (fname.hashCode() * 1021) ^ lname.hashCode();
}
public boolean equals(Object obj)
{
return this.fname.equals(((Person)obj).fname) &&
this.lname.equals(((Person)obj).lname);
}
}
static class Point
{
public Point(int x, int y) {
this.x = x;
this.y = y;
}
int x;
int y;
public int hashCode()
{
return (x * 31) ^ y;
}
public boolean equals(Object obj)
{
return x == ((Point)obj).x &&
y == ((Point)obj).y;
}
}
static Character [] getLowerCase()
{
Character []temp = new Character[26];
for(int i = 0; i < 26; i++)
temp[i] = (char)(i + 97);
return temp;
}
static Character [] getUpperCase()
{
Character []temp = new Character[26];
for(int i = 0; i < 26; i++)
temp[i] = (char)(i + 65);
return temp;
}
static String getName(Character[] lower, Character[] upper)
{
Random r = new Random();
StringBuilder sb = new StringBuilder();
int count = r.nextInt(10);
for(int j = 0; j < count; j++)
{
int index = r.nextInt(25);
if(j == 0)
sb.append(upper[index]);
else
sb.append(lower[index]);
}
return sb.toString();
}
static void AnalyzePerson()
{
Character [] lower = getLowerCase();
Character [] upper = getUpperCase();
Hashtable<Person, Integer> table = new Hashtable<Person, Integer>();
Person []list = new Person[500000];
long pastTime = System.currentTimeMillis();
for(int i = 0; i < 500000; i++)
{
String fname = getName(lower, upper);
String lname = getName(lower, upper);
Person p = new Person(fname, lname);
table.put(p, i);
list[i] = p;
}
long currentTime = System.currentTimeMillis();
System.out.println("putting: " + (currentTime - pastTime));
pastTime = System.currentTimeMillis();
for(int i = 0; i < 500000; i++)
{
Person p = list[i];
table.get(p);
}
currentTime = System.currentTimeMillis();
System.out.println("getting: " + (currentTime - pastTime));
}
static void AnalyzePoint()
{
Hashtable<Point, Integer> table = new Hashtable<Point, Integer>();
Point []list = new Point[500000];
Random r = new Random();
long pastTime = System.currentTimeMillis();
for(int i = 0; i < 500000; i++)
{
Point p = new Point(r.nextInt(50), r.nextInt(100));
table.put(p, i);
list[i] = p;
}
long currentTime = System.currentTimeMillis();
System.out.println("putting: " + (currentTime - pastTime));
pastTime = System.currentTimeMillis();
for(int i = 0; i < 500000; i++)
{
Point p = list[i];
table.get(p);
}
currentTime = System.currentTimeMillis();
System.out.println("getting: " + (currentTime - pastTime));
}
public static void main(String[] args) {
AnalyzePoint();
AnalyzePerson();
}
}
Random Code Generator 