Skip to content

Instantly share code, notes, and snippets.

@johno
Last active December 15, 2015 05:19
Show Gist options
  • Save johno/5208191 to your computer and use it in GitHub Desktop.
Save johno/5208191 to your computer and use it in GitHub Desktop.
I don't like Java very much.
import java.util.*;
import java.math.*;
public class HashTable {
private int tableSize;
private int debugLevel;
private BigInteger maxSize = new BigInteger("96000");
private BigInteger minSize = new BigInteger("95500");
private boolean weAreDoubleHashing;
private Object[] hashTable;
public HashTable(boolean useDoubleHash) {
setTableSize();
hashTable = new Object[tableSize];
weAreDoubleHashing = useDoubleHash;
debugLevel = 0;
}
public void insert(Object obj) {
if(weAreDoubleHashing) {
doubleHashingInsert(obj);
}
else {
linearProbingInsert(obj);
}
}
public void linearProbingInsert(Object obj) {
int i = 0;
boolean done = false;
while(!done) {
done = tryInsert(obj, linearProbing(((HashObject)obj).getKey(), i));
i++;
}
}
public void doubleHashingInsert(Object obj) {
int i = 0;
boolean done = false;
while(!done) {
done = tryInsert(obj, doubleHashing(((HashObject)obj).getKey(), i));
i++;
if(i > tableSize + 1) {
//printTable();
System.err.println("There was a key that could not be placed in a slot.");
System.err.println(weAreDoubleHashing ? "Double Hashing" : "Linear Probing");
System.err.println(((HashObject)obj).toString());
isTableFull();
System.err.println("Skipping element.");
done = true;
}
}
}
// Attempts to insert an object to the hashtable at the specified index.
//
// = If it is unsuccessful it returns false and nothing else happens.
// = If there already is an equal object there, it increments frequency.
// = If the slot is empty, it adds object and increments probes and frequency.
public boolean tryInsert(Object obj, int index) {
if(hashTable[index] == null) {
// Empty slot.
hashTable[index] = obj;
((HashObject)obj).probes++;
return true;
}
else if(((HashObject)obj).equals(hashTable[index])) {
// Filled with an equal object.
((HashObject)hashTable[index]).frequency++;
return true;
}
else {
// Filled with something else.
((HashObject)obj).probes++;
return false;
}
}
// h(k) = k+i mod m
public int linearProbing(int key, int iter) {
return ((key + iter) % tableSize);
}
// h(k) = (h1(k) + i*h2(k)) mod m
public int doubleHashing(int key, int iter) {
return ((calcPrimaryHashIndex(key) + iter*calcSecondaryHashIndex(key)) % tableSize);
}
// h(k) = k mod m
public int calcPrimaryHashIndex(int key) {
return (key % tableSize);
}
// h(k) = 1 + k mod m-2
public int calcSecondaryHashIndex(int key) {
return 1 + (key % (tableSize - 2));
}
// =========================================
// Calculates a prime number that is within
// maxSize and minSize.
//
// It also attempts to find a twin prime.
// That is less than the max size. If that
// search is unsuccessful it merely returns
// the next probable prime after minSize
//
// If the next prime number after minSize is
// greater than the maxSize, it will still
// return the value. So before creating the
// table a check must be made.
// =========================================
private int calculateTableSize() {
int first, second, max;
max = Integer.parseInt(maxSize.toString());
BigInteger firstPrime = minSize;
while((first = Integer.parseInt((firstPrime = firstPrime.nextProbablePrime()).toString())) < max) {
second = Integer.parseInt(firstPrime.nextProbablePrime().toString());
if((second - first) == 2) {
return second;
}
}
return Integer.parseInt(minSize.nextProbablePrime().toString());
}
// Returns true if tableSize is valid.
// Otherwise false.
private boolean validateTableSize() {
if(tableSize > Integer.parseInt(maxSize.toString())) {
return false;
}
return true;
}
public int tableSize() {
return hashTable.length;
}
// Sets the tablesize. Assigns it as a prime
// number based upon calculateTableSize().
// Then ensures that it is within the specified
// Table sizes, if not. It sets it to be the
// minSize.
private void setTableSize() {
tableSize = calculateTableSize();
if(!validateTableSize()) {
tableSize = Integer.parseInt(minSize.toString());
}
}
public void printTable() {
for(int i = 0; i < tableSize; i++) {
if(hashTable[i] != null) {
String str = "table[" + i + "]: "+ ((HashObject)hashTable[i]).toString();
if(debugLevel == 2) {
str += " " + ((HashObject)hashTable[i]).probes;
}
System.out.println(str);
}
}
}
public float calculateProbeRatio() {
float probes = 0;
int numElements = 0;
for(int i = 0; i < tableSize; i++) {
if(hashTable[i] != null) {
probes += ((HashObject)hashTable[i]).probes;
numElements++;
}
}
return ((float)probes)/((float)numElements);
}
public int numberOfInserts() {
int numElements = 0;
for(int i = 0; i < tableSize; i++) {
if(hashTable[i] != null) {
numElements++;
}
}
return numElements;
}
public int numberOfDupes() {
int numDupes = 0;
for(int i = 0; i < tableSize; i++) {
if(hashTable[i] != null && ((HashObject)hashTable[i]).frequency > 1) {
numDupes += ((HashObject)hashTable[i]).frequency;
}
}
return numDupes;
}
public void setDebugLevel(int level) {
if(level < 0 || level > 2) {
return;
}
debugLevel = level;
}
public int debugLevel() {
return debugLevel;
}
public void clear() {
for(int i = 0; i < tableSize; i++) {
hashTable[i] = null;
}
}
public void isTableFull() {
boolean full = true;
for(int i = 0; i < tableSize; i++) {
if(hashTable[i] == null) {
full = false;
}
}
System.err.println(full ? "Table full" : "Table not full");
}
// ======================================================== //
// ======================================================== //
// ======================================================== //
// Embedded classes are the only badass thing about Java //
// ======================================================== //
public class HashObject {
private Object key;
private int frequency;
private int probes;
// Hey look, a constructor.
public HashObject(Object newKey) {
key = newKey;
frequency = 1;
probes = 0;
}
@Override // Use the equals method to compare keys.
public boolean equals(Object compareMe) {
if(key.equals(((HashObject)compareMe).key)) {
return true;
}
return false;
}
@Override // Let's make the to string method perty.
public String toString() {
String str = "";
str += key + " " + frequency;
return str;
}
public int getKey() {
int code = key.hashCode();
if(code < 0) {
code = code*-1;
}
return code;
}
}
}
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class HashTest {
public static void main(String[] args) {
KeyGen keyGen = new KeyGen();
float alphaValue = (float)0.5;
int inputType = 1;
HashTable linearProbing = new HashTable(false);
HashTable doubleHashing = new HashTable(true);
if(args.length == 2) {
inputType = parseInputType(args[0]);
alphaValue = parseLoadLevel(args[1]);
}
else if(args.length == 3) {
inputType = parseInputType(args[0]);
alphaValue = parseLoadLevel(args[1]);
int debugLevel = parseDebugLevel(args[2]);
linearProbing.setDebugLevel(debugLevel);
doubleHashing.setDebugLevel(debugLevel);
}
else {
raiseInvalidArgumentError();
}
if(inputType == 1) {
for(int i = 0; i < Math.round(alphaValue*linearProbing.tableSize()); i++) {
int key = keyGen.randomInt();
HashTable.HashObject linearProbingInt = linearProbing.new HashObject(key);
HashTable.HashObject doubleHashingInt = doubleHashing.new HashObject(key);
linearProbing.insert(linearProbingInt);
doubleHashing.insert(doubleHashingInt);
}
}
else if(inputType == 2) {
for(int i = 0; i < Math.round(alphaValue*linearProbing.tableSize()); i++) {
long key = keyGen.currentTime();
HashTable.HashObject linearProbingLong = linearProbing.new HashObject(key);
HashTable.HashObject doubleHashingLong = doubleHashing.new HashObject(key);
linearProbing.insert(linearProbingLong);
doubleHashing.insert(doubleHashingLong);
}
}
else {
parseFilenameFromInput("word-list", alphaValue, linearProbing, doubleHashing);
}
if(linearProbing.debugLevel() > 0) {
System.out.println("Linear Probing Table: ");
linearProbing.printTable();
System.out.println("Double Hashing Table: ");
doubleHashing.printTable();
}
System.out.println("Table Size Found: " + linearProbing.tableSize());
if(inputType == 1) {
System.out.println("Input Type: Random number generator.");
}
else if(inputType == 2) {
System.out.println("Input Type: Longs based off current time.");
}
else if(inputType == 3) {
System.out.println("Input Type: word-list");
}
System.out.println("\n\n");
System.out.println("Using linear probing...");
System.out.println("Inserted " + linearProbing.numberOfInserts() + " elements.");
System.out.println(linearProbing.numberOfDupes() + " duplicates.");
System.out.println("Average number of probes: " + linearProbing.calculateProbeRatio());
System.out.println("\n\n");
System.out.println("Using double hashing...");
System.out.println("Inserted " + doubleHashing.numberOfInserts() + " elements.");
System.out.println(doubleHashing.numberOfDupes() + " duplicates.");
System.out.println("Average number of probes: " + doubleHashing.calculateProbeRatio());
}
public static int parseInputType(String inputType) {
int selection;
try {
selection = Integer.parseInt(inputType);
if(selection < 1 || selection > 3) {
System.err.println("Error with input selection.");
throw new NumberFormatException();
}
else {
return selection;
}
} catch(NumberFormatException e) {
raiseInvalidArgumentError();
}
return 1;
}
public static void parseFilenameFromInput(String filename, float alphaValue, HashTable linearProbing, HashTable doubleHashing)
{
Scanner scan = null;
try
{
scan = new Scanner(new File(filename));
} catch(FileNotFoundException e) {
raiseInvalidFileError();
return;
}
for(int i = 0; i < Math.round(alphaValue*linearProbing.tableSize()); i++) {
if(scan.hasNextLine())
{
parseLine(scan.nextLine(), linearProbing, doubleHashing);
}
}
scan.close();
}
public static void parseLine(String line, HashTable linearProbing, HashTable doubleHashing)
{
Scanner scan = null;
scan = new Scanner(line);
while(scan.hasNext())
{
String key = scan.next();
HashTable.HashObject linearProbingString = linearProbing.new HashObject(key);
HashTable.HashObject doubleHashingString = doubleHashing.new HashObject(key);
linearProbing.insert(linearProbingString);
doubleHashing.insert(doubleHashingString);
}
scan.close();
}
public static float parseLoadLevel(String loadLevel) {
try {
float selection = Float.parseFloat(loadLevel);
if(selection < 0 || selection > 0.9999) {
System.err.println("Error with load level selection.");
throw new NumberFormatException();
}
else {
return selection;
}
} catch(NumberFormatException e) {
raiseInvalidArgumentError();
}
return (float)0.0;
}
public static int parseDebugLevel(String debugLevel) {
try {
int selection = Integer.parseInt(debugLevel);
if(selection < 0 || selection > 3) {
System.err.println("Error with debug level selection.");
throw new NumberFormatException();
}
else {
return selection;
}
} catch(NumberFormatException e) {
raiseInvalidArgumentError();
}
return 0;
}
public static void raiseInvalidArgumentError() {
System.err.println("Usage: java HashTest <input type> <load factor> [<debug level>]");
System.exit(0);
}
public static void raiseInvalidFileError()
{
System.err.println("The specified file could not be found");
System.err.println("This program searched for the filename 'word-list' in the main directory.");
System.exit(0);
}
}
import java.util.*;
public class KeyGen {
Random random;
public KeyGen() {
random = new Random();
}
public long randomLong() {
long tmp = random.nextLong();
// Make sure it's positive.
if(tmp < 0) {
tmp = tmp*-1;
}
return tmp;
}
public int randomInt() {
int tmp = random.nextInt();
// Make sure it's positive.
if(tmp < 0) {
tmp = tmp*-1;
}
return tmp;
}
public long currentTime() {
return System.currentTimeMillis();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment