Class TTT_HC

java.lang.Object

TTT_HC

public class TTT_HC
extends java.lang.Object

The TTT_HC method accomplishes a similar purpose as TicTacToeHashCode except the hash code method in this class is intended to cause collisions and deals with these collisions through chaining. This class uses HashNodes to accomplish this, as the HashNodes essentially have the functions of a node in a linked list but are specialized for use with methods that have hash functions in them because they hold a String value and a hash number. The main of this method creates an object of this class, and analyzes the efficiency of the winners array in a number of fields ranging from load factor to collisions per tenth.

Author:

AnneMarie Caballero (annemariecabs)

Field Summary

Fields

Modifier and Type	Field	Description
private static int	ARRAY_SIZE	Length of the winner array.
private static int	ERROR_CODE	An integer constant holding the number (1) that is passed to System.exit() after certain conditions occur
private static int	NUMBER_OF_WINNERS	The number of winning TicTacToe Strings
private static char	O	A char holding an o
private static int[]	POWERS_OF_THREE	A lookup table with powers of three where the each spot holds three ^ index
private static char	SPACE	A char holding a space
private static java.lang.String	WINNER_FILE	The name of the file with the TicTacToe winners
private static java.lang.String	WINNER_FILE_NOT_FOUND	The error message used if the file with the winners is not found
private HashNode[]	winners	The winners array which will store the Strings of all the possible TicTacToe winners using HashNodes
private static char	X	A char holding an x

Constructor Summary

Constructors

Constructor	Description
TTT_HC()	This creates a TTT_HC by instantiating and filling the winners array of HashNodes which should hold all of the winning Strings at their proper hash code index.

Method Summary

Modifier and Type	Method	Description
static void	analyzeAndPrint(int arraySize, java.util.ArrayList<java.lang.Integer> chainLengths, java.util.ArrayList<HashNode> entrySpots, java.util.ArrayList<HashNode> collisionSpots, int emptySpaces)	Analyzes and prints the required information surrounding the winners method which is: size of the array, load factor, the number of chains, the maximum chain length, the average chain length, the number of entries per quarter and the number of collisions per tenth.
static void	main(java.lang.String[] args)
int	tttHashCode(java.lang.String str)	Returns a hash code for each winner to be stored.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

winners

private HashNode[] winners

The winners array which will store the Strings of all the possible TicTacToe winners using HashNodes

WINNER_FILE

private static final java.lang.String WINNER_FILE

The name of the file with the TicTacToe winners

See Also:

Constant Field Values

WINNER_FILE_NOT_FOUND

private static final java.lang.String WINNER_FILE_NOT_FOUND

The error message used if the file with the winners is not found

See Also:

Constant Field Values

POWERS_OF_THREE

private static final int[] POWERS_OF_THREE

A lookup table with powers of three where the each spot holds three ^ index

SPACE

private static final char SPACE

A char holding a space

See Also:

Constant Field Values

X

private static final char X

A char holding an x

See Also:

Constant Field Values

O

private static final char O

A char holding an o

See Also:

Constant Field Values

ERROR_CODE

private static final int ERROR_CODE

An integer constant holding the number (1) that is passed to System.exit() after certain conditions occur

See Also:

Constant Field Values

NUMBER_OF_WINNERS

private static final int NUMBER_OF_WINNERS

The number of winning TicTacToe Strings

See Also:

Constant Field Values

ARRAY_SIZE

private static final int ARRAY_SIZE

Length of the winner array. 354 was chosen because it has zero wasted spaces in the array, and a roughly even distribution, and it is the lowest chain length that can be achieved with zero wasted spaces, which is great in terms of storage, but also shows concern for efficiency.

See Also:

Constant Field Values

Constructor Detail

TTT_HC

TTT_HC()

This creates a TTT_HC by instantiating and filling the winners array of HashNodes which should hold all of the winning Strings at their proper hash code index. If there is already a HashNode at that index, the constructor uses chaining as the method of solving collisions by adding the HashNode at that index, and setting the next HashNode to the current HashNode located there.

Method Detail

tttHashCode

public int tttHashCode(java.lang.String str)

Returns a hash code for each winner to be stored. This hash code method will cause collisions because this method is focusing on being efficient with space, and should have no wasted spaces in the main array.

Parameters:

str - the String to create a hash code for

Returns:

an integer hash code for str

analyzeAndPrint

public static void analyzeAndPrint(int arraySize,
                                   java.util.ArrayList<java.lang.Integer> chainLengths,
                                   java.util.ArrayList<HashNode> entrySpots,
                                   java.util.ArrayList<HashNode> collisionSpots,
                                   int emptySpaces)

Analyzes and prints the required information surrounding the winners method which is: size of the array, load factor, the number of chains, the maximum chain length, the average chain length, the number of entries per quarter and the number of collisions per tenth.

Parameters:

arraySize - the size of the array to be analyzed

chainLengths - an ArrayList of all of the chainLengths (greater than 1) found in the array being analyzed

entrySpots - an ArrayList of the HashNodes that are directly located in winners

collisionSpots - an ArrayList of the HashNodes where collisions occurred

emptySpaces - the number of empty spots in the winners array

main

public static void main(java.lang.String[] args)