Created
November 17, 2011 02:38
-
-
Save tedpennings/1372209 to your computer and use it in GitHub Desktop.
awful java hashtable implementation
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.BufferedReader; | |
import java.io.File; | |
import java.io.FileInputStream; | |
import java.io.FileNotFoundException; | |
import java.io.IOException; | |
import java.io.InputStream; | |
import java.io.InputStreamReader; | |
import java.math.BigDecimal; | |
import java.math.RoundingMode; | |
import java.util.ArrayList; | |
import java.util.List; | |
/** | |
* A programming exercise for an algorithms course | |
* | |
* This code is awful because there were a few constraints that made it hard to write nice code (ie one class file). | |
* | |
* @author Ted Pennings | |
*/ | |
public class P1Pennings { | |
private static int LINEAR_COLLISIONS = 0; | |
private static int QUADRATIC_COLLISIONS = 0; | |
private static int DOUBLE_HASHING_COLLISIONS = 0; | |
private static BigDecimal LINEAR_COLLISION_PROBABILITY = BigDecimal.ZERO; | |
private static BigDecimal QUADRATIC_COLLISION_PROBABILITY = BigDecimal.ZERO; | |
private static BigDecimal DOUBLE_HASHING_COLLISION_PROBABILITY = BigDecimal.ZERO; | |
public static void main(String[] args) { | |
System.out.println("Ted Pennings - CS 566 L3"); | |
if (args.length != 1) { | |
throw new IllegalArgumentException( | |
"Please run this program with 1 argument, the path to a file containing numbers to store"); | |
} | |
resetStaticFields(); | |
String location = args[0]; | |
List<String> lines = readFile(location); | |
List<Integer> parsed = parseIntegers(lines); | |
int tableSize = getTableSize(parsed.get(0)); | |
System.out.println("Table size is " + tableSize + " (padded by 20%)"); | |
List<Integer> integers = getIntegers(parsed); | |
System.out.println("Storing the input sequence " + integers); | |
doLinear(tableSize, integers); | |
doQuadratic(tableSize, integers); | |
doDoubleHashing(tableSize, integers); | |
System.out.println(""); | |
System.out.println(""); | |
System.out.println("-----------------------------------"); | |
System.out.println("Overall collision statistics totals"); | |
System.out.println("-----------------------------------"); | |
printLinearCollisions(); | |
printQuadraticCollisions(); | |
printDoubleHashingCollisions(); | |
} | |
private static void resetStaticFields() { | |
LINEAR_COLLISIONS = 0; | |
QUADRATIC_COLLISIONS = 0; | |
DOUBLE_HASHING_COLLISIONS = 0; | |
LINEAR_COLLISION_PROBABILITY = BigDecimal.ZERO; | |
QUADRATIC_COLLISION_PROBABILITY = BigDecimal.ZERO; | |
DOUBLE_HASHING_COLLISION_PROBABILITY = BigDecimal.ZERO; | |
} | |
private static void printQuadraticCollisions() { | |
System.out.println("Quadratic hashing encountered " | |
+ QUADRATIC_COLLISIONS | |
+ " collision(s) for a collision average of " | |
+ QUADRATIC_COLLISION_PROBABILITY); | |
} | |
private static void printLinearCollisions() { | |
System.out.println("Linear hashing encountered " + LINEAR_COLLISIONS | |
+ " collision(s) for a collision average of " | |
+ LINEAR_COLLISION_PROBABILITY); | |
} | |
private static void printDoubleHashingCollisions() { | |
System.out.println("Double hashing encountered " | |
+ DOUBLE_HASHING_COLLISIONS | |
+ " collision(s) for a collision average of " | |
+ DOUBLE_HASHING_COLLISION_PROBABILITY); | |
} | |
private static void doDoubleHashing(int tableSize, List<Integer> integers) { | |
System.out.println("-----------------------------------"); | |
System.out.println("Beginning double hashing probing insertion"); | |
Integer[] hashing = new Integer[tableSize]; | |
insertDoubleHashing(hashing, integers); | |
System.out.println("Double hashing table now contains"); | |
printTable(hashing); | |
System.out.println("-----------------------------------"); | |
printDoubleHashingCollisions(); | |
System.out.println("-----------------------------------"); | |
System.out.println(""); | |
} | |
private static void doQuadratic(int tableSize, List<Integer> integers) { | |
System.out.println("-----------------------------------"); | |
System.out.println("Beginning quadratic probing insertion"); | |
Integer[] quadratic = new Integer[tableSize]; | |
insertQuadratic(quadratic, integers); | |
System.out.println("Quadratic table now contains"); | |
printTable(quadratic); | |
System.out.println("-----------------------------------"); | |
printQuadraticCollisions(); | |
System.out.println("-----------------------------------"); | |
System.out.println(""); | |
} | |
private static void doLinear(int tableSize, List<Integer> integers) { | |
System.out.println("-----------------------------------"); | |
System.out.println("Beginning linear probing insertion"); | |
Integer[] linear = new Integer[tableSize]; | |
insertLinear(linear, integers); | |
System.out.println("Linear table now contains"); | |
printTable(linear); | |
System.out.println("-----------------------------------"); | |
printLinearCollisions(); | |
System.out.println("-----------------------------------"); | |
System.out.println(""); | |
} | |
private static List<Integer> getIntegers(List<Integer> parsed) { | |
return parsed.subList(1, parsed.size()); | |
} | |
private static void insertDoubleHashing(Integer[] table, List<Integer> ints) { | |
for (int current : ints) { | |
boolean inserted = false; | |
int attempts = 0; | |
while (!inserted) { | |
int index = doubleHash(current, table.length, attempts); | |
if (table[index] == null) { | |
table[index] = current; | |
inserted = true; | |
} else if (attempts == table.length) { | |
// this can wrap past Integer.MAX_VALUE back to negative | |
// numbers and result in an ArrayIndexOutOfBoundsException | |
throw new RuntimeException("Table full. Unable to insert " | |
+ current + " after " + attempts + " attempts"); | |
} else { | |
DOUBLE_HASHING_COLLISIONS++; | |
attempts++; | |
} | |
} | |
} | |
DOUBLE_HASHING_COLLISION_PROBABILITY = BigDecimal | |
.valueOf(DOUBLE_HASHING_COLLISIONS).setScale(2) | |
.divide(BigDecimal.valueOf(ints.size()), RoundingMode.HALF_UP); | |
} | |
private static int doubleHash(int current, int length, int i) { | |
int h1 = current % length; | |
int h2 = 1 + (current % (length - 1)); | |
return (h1 + (i * h2)) % length; | |
} | |
private static int quadraticHash(int current, int length, int i) { | |
final int c1 = 1; | |
final int c2 = 3; | |
int h = current % length; | |
return (h + (c1 * i) + (c2 * i * i)) % length; | |
} | |
private static void insertQuadratic(Integer[] table, List<Integer> ints) { | |
for (int current : ints) { | |
boolean inserted = false; | |
int attempts = 0; | |
while (!inserted) { | |
int index = quadraticHash(current, table.length, attempts); | |
if (table[index] == null) { | |
table[index] = current; | |
inserted = true; | |
} else if (attempts == table.length) { | |
// this can wrap past Integer.MAX_VALUE back to negative | |
// numbers and result in an ArrayIndexOutOfBoundsException | |
throw new RuntimeException("Table full. Unable to insert " | |
+ current + " after " + attempts + " attempts"); | |
} else { | |
QUADRATIC_COLLISIONS++; | |
attempts++; | |
} | |
} | |
} | |
QUADRATIC_COLLISION_PROBABILITY = BigDecimal | |
.valueOf(QUADRATIC_COLLISIONS).setScale(2) | |
.divide(BigDecimal.valueOf(ints.size()), RoundingMode.HALF_UP); | |
} | |
private static void insertLinear(Integer[] table, List<Integer> ints) { | |
for (int current : ints) { | |
boolean inserted = false; | |
int attempts = 0; | |
while (!inserted) { | |
int index = linearHash(current, table.length, attempts); | |
if (table[index] == null) { | |
table[index] = current; | |
inserted = true; | |
} else if (attempts == table.length) { | |
// this can wrap past Integer.MAX_VALUE back to negative | |
// numbers and result in an ArrayIndexOutOfBoundsException | |
throw new RuntimeException("Table full. Unable to insert " | |
+ current + " after " + attempts + " attempts"); | |
} else { | |
LINEAR_COLLISIONS++; | |
attempts++; | |
} | |
} | |
} | |
LINEAR_COLLISION_PROBABILITY = BigDecimal.valueOf(LINEAR_COLLISIONS) | |
.setScale(2) | |
.divide(BigDecimal.valueOf(ints.size()), RoundingMode.HALF_UP); | |
} | |
private static int linearHash(int value, int tableSize, int attempts) { | |
return (value + attempts) % tableSize; | |
} | |
private static void printTable(Integer[] table) { | |
for (int i = 0; i < table.length; i++) { | |
System.out.println(i + " - " + table[i]); | |
} | |
} | |
private static int getTableSize(int integer) { | |
BigDecimal factor = new BigDecimal("1.2"); | |
return BigDecimal.valueOf(integer).multiply(factor) | |
.setScale(0, RoundingMode.HALF_UP).intValue(); | |
} | |
static List<String> readFile(String location) { | |
try { | |
InputStream stream = streamFor(location); | |
BufferedReader br = new BufferedReader( | |
new InputStreamReader(stream)); | |
List<String> lines = new ArrayList<String>(); | |
String strLine; | |
while ((strLine = br.readLine()) != null) { | |
lines.add(strLine); | |
} | |
br.close(); | |
System.out.println("Read input sequence " + lines); | |
return lines; | |
} catch (IOException e) { | |
throw new RuntimeException("Error reading file " + location, e); | |
} | |
} | |
static InputStream streamFor(String location) throws FileNotFoundException { | |
File file = new File(location); | |
if (file.exists()) { | |
return new FileInputStream(file); | |
} | |
return P1Pennings.class.getResourceAsStream(location); | |
} | |
static List<Integer> parseIntegers(List<String> strings) { | |
List<Integer> integers = new ArrayList<Integer>(); | |
for (String string : strings) { | |
if (string == null || string.trim().isEmpty()) { | |
continue; | |
} | |
try { | |
integers.add(Integer.valueOf(string.trim())); | |
} catch (NumberFormatException nfe) { | |
throw new RuntimeException( | |
"Caught unparseable line, " + string, nfe); | |
} | |
} | |
return integers; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment