Last active
December 15, 2015 05:19
-
-
Save johno/5208191 to your computer and use it in GitHub Desktop.
I don't like Java very much.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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