|
The hashing assignment ...
|
/*
* HashTest.java
*/
package testers;
import hashing.*;
import specialobject.*;
import java.awt.*;
public class HashTest
{
static public void main(String args[])
{
System.out.println("\nCREATE AND DISPLAY INITIAL HASH TABLE.");
HashTable ht = new HashTable(10);
ht.display();
System.out.println("\nADD OBJECTS TO THE HASH TABLE.");
SpecialObject color;
color = new SpecialObject("aliceblue",new Color(240,248,255));
ht.add(color);
color = new SpecialObject("antiquewhite",new Color(250,235,215));
ht.add(color);
color = new SpecialObject("aqua",new Color(0,255,255));
ht.add(color);
color = new SpecialObject("aquamarine",new Color(127,255,212));
ht.add(color);
color = new SpecialObject("azure",new Color(240,255,255));
ht.add(color);
color = new SpecialObject("beige",new Color(245,245,220));
ht.add(color);
color = new SpecialObject("bisque",new Color(255,228,196));
ht.add(color);
color = new SpecialObject("black",new Color(0,0,0));
ht.add(color);
color = new SpecialObject("blanchedalmond",new Color(255,235,205));
ht.add(color);
color = new SpecialObject("blue",new Color(0,0,255));
ht.add(color);
color = new SpecialObject("blueviolet",new Color(138,43,226));
ht.add(color);
color = new SpecialObject("brown",new Color(165,42,42));
ht.add(color);
color = new SpecialObject("burlywood",new Color(222,184,135));
ht.add(color);
color = new SpecialObject("cadetblue",new Color(95,158,160));
ht.add(color);
color = new SpecialObject("chartreuse",new Color(127,255,0));
ht.add(color);
color = new SpecialObject("chocolate",new Color(210,105,30));
ht.add(color);
System.out.println("\nDISPLAY THE HASH TABLE.");
ht.display();
}
}
init:
deps-jar:
compile-single:
run-single:
CREATE AND DISPLAY INITIAL HASH TABLE.
Bucket 0
[]
Bucket 1
[]
Bucket 2
[]
Bucket 3
[]
Bucket 4
[]
Bucket 5
[]
Bucket 6
[]
Bucket 7
[]
Bucket 8
[]
Bucket 9
[]
ADD OBJECTS TO THE HASH TABLE.
id = aliceblue
sum of squares of letter positions = 874
hash value of aliceblue = 4
id = antiquewhite
sum of squares of letter positions = 2532
hash value of antiquewhite = 2
id = aqua
sum of squares of letter positions = 732
hash value of aqua = 2
id = aquamarine
sum of squares of letter positions = 1528
hash value of aquamarine = 8
id = azure
sum of squares of letter positions = 1467
hash value of azure = 7
id = beige
sum of squares of letter positions = 184
hash value of beige = 4
id = bisque
sum of squares of letter positions = 1201
hash value of bisque = 1
id = black
sum of squares of letter positions = 279
hash value of black = 9
id = blanchedalmond
sum of squares of letter positions = 1210
hash value of blanchedalmond = 0
id = blue
sum of squares of letter positions = 614
hash value of blue = 4
id = blueviolet
sum of squares of letter positions = 1973
hash value of blueviolet = 3
id = brown
sum of squares of letter positions = 1278
hash value of brown = 8
id = burlywood
sum of squares of letter positions = 2533
hash value of burlywood = 3
id = cadetblue
sum of squares of letter positions = 1065
hash value of cadetblue = 5
id = chartreuse
sum of squares of letter positions = 1974
hash value of chartreuse = 4
id = chocolate
sum of squares of letter positions = 1102
hash value of chocolate = 2
DISPLAY THE HASH TABLE.
Bucket 0
[[blanchedalmond:java.awt.Color[r=255,g=235,b=205]]]
Bucket 1
[[bisque:java.awt.Color[r=255,g=228,b=196]]]
Bucket 2
[[antiquewhite:java.awt.Color[r=250,g=235,b=215]],
[aqua:java.awt.Color[r=0,g=255,b=255]],
[chocolate:java.awt.Color[r=210,g=105,b=30]]]
Bucket 3
[[blueviolet:java.awt.Color[r=138,g=43,b=226]],
[burlywood:java.awt.Color[r=222,g=184,b=135]]]
Bucket 4
[[aliceblue:java.awt.Color[r=240,g=248,b=255]],
[beige:java.awt.Color[r=245,g=245,b=220]],
[blue:java.awt.Color[r=0,g=0,b=255]],
[chartreuse:java.awt.Color[r=127,g=255,b=0]]]
Bucket 5
[[cadetblue:java.awt.Color[r=95,g=158,b=160]]]
Bucket 6
[]
Bucket 7
[[azure:java.awt.Color[r=240,g=255,b=255]]]
Bucket 8
[[aquamarine:java.awt.Color[r=127,g=255,b=212]],
[brown:java.awt.Color[r=165,g=42,b=42]]]
Bucket 9
[[black:java.awt.Color[r=0,g=0,b=0]]]
BUILD SUCCESSFUL (total time: 1 second)
|
/*
* SpecialObjectADT.java
*/
package specialobject;
public interface SpecialObjectADT
{
public String key();
public Object object();
public String toString();
}
/*
* SpecialObject.java
*/
package specialobject;
public class SpecialObject implements SpecialObjectADT
{
String key;
Object object;
public SpecialObject(String k, Object o)
{
key = k;
object = o;
}
public String key()
{
return key;
}
public Object object()
{
return object;
}
public String toString()
{
return "["+key+":"+object+"]";
}
}
|
/*
* HashTableADT.java
*/
package hashing;
import specialobject.*;
public interface HashTableADT
{
public void add(SpecialObject object);
public void delete(String key);
public SpecialObject lookup(String key);
public boolean memberp(String key);
public void display();
}
/*
* HashTable.java
*/
package hashing;
import specialobject.*;
import hashing.HashTableADT;
import java.util.*;
public class HashTable implements HashTableADT
{
Vector[] hashtable;
public HashTable(int n)
{
hashtable = new Vector[n];
for ( int x = 0; x < n; x++ ) {
hashtable[x] = new Vector();
}
}
public void add(SpecialObject object)
{
String key = object.key();
int a = hash(key);
hashtable[a].addElement(object);
}
public boolean memberp(String key)
{
int a = hash(key);
return memberp(hashtable[a],key);
}
private boolean memberp(Vector v,String k)
{
for ( int i = 0; i < v.size(); i++ ) {
SpecialObject so = (SpecialObject)v.elementAt(i);
if ( so.key().equals(k) ) return true;
}
return false;
}
public SpecialObject lookup(String key)
{
int a = hash(key);
return lookup(hashtable[a],key);
}
private SpecialObject lookup(Vector v,String k)
{
for ( int i = 0; i < v.size(); i++ ) {
SpecialObject so = (SpecialObject)v.elementAt(i);
if ( so.key().equals(k) ) return so;
}
return null;
}
public void delete(String key)
{
int a = hash(key);
delete(hashtable[a],key);
}
private void delete(Vector v,String k)
{
for ( int i = 0; i < v.size(); i++ ) {
SpecialObject so = (SpecialObject)v.elementAt(i);
if ( so.key().equals(k) ) {
v.removeElementAt(i);
break;
}
}
}
public void display()
{
for ( int i = 0; i < hashtable.length; i++ ) {
System.out.println("Bucket " + i );
System.out.println(hashtable[i].toString());
}
}
private int hash(String s)
{
System.out.println("id = " + s);
int sum = 0;
for ( int i = 0; i < s.length(); i++ ) {
String c = s.substring(i,i+1);
int x = alphaPos(c);
sum = sum + ( x * x );
}
System.out.println("sum of squares of letter positions = " + sum);
int h = modulo(sum,hashtable.length);
System.out.println("hash value of " + s + " = " + h);
return h;
}
private int alphaPos(String c)
{
int result = "abcdefghigklmnopqrstuvwxyz".indexOf(c.toLowerCase()) + 1;
return result;
}
private int modulo(int a, int b)
{
if ( a < b ) {
return a;
} else {
return modulo(a-b,b);
}
}
}
|
|