У меня есть следующий код, который возьмет 30 строк (числа) и поместит их в хэш-таблицу после их вычисления с помощью "% 29"
import java.util.Arrays;
public class HashFunction {
String[] theArray;
int arraySize;
int itemsInArray = 0;
public static void main(String[] args) {
HashFunction theFunc = new HashFunction(30); // this is where you should be able to control the number of spaces availble in the hash table!!!
// Simplest Hash Function
// String[] elementsToAdd = { "1", "5", "17", "21", "26" };
// theFunc.hashFunction1(elementsToAdd, theFunc.theArray);
// Mod Hash Function
// This contains exactly 30 items to show how collisions
// will work
String[] elementsToAdd2 = { "100", "510", "170", "214", "268", "398",
"235", "802", "900", "723", "699", "1", "16", "999", "890",
"725", "998", "978", "988", "990", "989", "984", "320", "321",
"400", "415", "450", "50", "660", "624" };
theFunc.hashFunction2(elementsToAdd2, theFunc.theArray);
// Locate the value 660 in the Hash Table
//theFunc.findKey("660");
theFunc.displayTheStack();
}
// Simple Hash Function that puts values in the same
// index that matches their value
public void hashFunction1(String[] stringsForArray, String[] theArray) {
for (int n = 0; n < stringsForArray.length; n++) {
String newElementVal = stringsForArray[n];
theArray[Integer.parseInt(newElementVal)] = newElementVal;
}
}
public void hashFunction2(String[] stringsForArray, String[] theArray) {
int sumOfCollisions = 0;
float averageOfCollisions = 0;
int numberOfCollisions = 0;
for (int n = 0; n < stringsForArray.length; n++) {
String newElementVal = stringsForArray[n];
// Create an index to store the value in by taking
// the modulus
int arrayIndex = Integer.parseInt(newElementVal) % 29;
System.out.println("Modulus Index= " + arrayIndex + " for value "
+ newElementVal);
// Cycle through the array until we find an empty space
while (theArray[arrayIndex] != "-1") {
++arrayIndex;
numberOfCollisions++;
//System.out.println("Collision Try " + arrayIndex + " Instead");
//System.out.println("Number of Collisions = " + numberOfCollisions);
// If we get to the end of the array go back to index 0
arrayIndex %= arraySize;
}
if (numberOfCollisions > 0)
{
System.out.println(" Number of Collisions = " + numberOfCollisions);
}
theArray[arrayIndex] = newElementVal;
}
sumOfCollisions += numberOfCollisions;
averageOfCollisions = sumOfCollisions / 30;
System.out.println("Sum of Collisions = " + sumOfCollisions);
System.out.println("Average of Collisions = " + averageOfCollisions);
}
// Returns the value stored in the Hash Table
public String findKey(String key) {
// Find the keys original hash key
int arrayIndexHash = Integer.parseInt(key) % 29;
while (theArray[arrayIndexHash] != "-1") {
if (theArray[arrayIndexHash] == key) {
// Found the key so return it
System.out.println(key + " was found in index "
+ arrayIndexHash);
return theArray[arrayIndexHash];
}
// Look in the next index
++arrayIndexHash;
// If we get to the end of the array go back to index 0
arrayIndexHash %= arraySize;
}
// Couldn't locate the key
return null;
}
HashFunction(int size) {
arraySize = size;
theArray = new String[size];
Arrays.fill(theArray, "-1");
}
public void displayTheStack() {
int increment = 0;
for (int m = 0; m < 3; m++) {
increment += 10;
for (int n = 0; n < 71; n++)
System.out.print("-");
System.out.println();
for (int n = increment - 10; n < increment; n++) {
System.out.format("| %3s " + " ", n);
}
System.out.println("|");
for (int n = 0; n < 71; n++)
System.out.print("-");
System.out.println();
for (int n = increment - 10; n < increment; n++) {
if (theArray[n].equals("-1"))
System.out.print("| ");
else
System.out
.print(String.format("| %3s " + " ", theArray[n]));
}
System.out.println("|");
for (int n = 0; n < 71; n++)
System.out.print("-");
System.out.println();
}
}
}
Для удобства вот вывод:
run:
Modulus Index= 13 for value 100
Modulus Index= 17 for value 510
Modulus Index= 25 for value 170
Modulus Index= 11 for value 214
Modulus Index= 7 for value 268
Modulus Index= 21 for value 398
Modulus Index= 3 for value 235
Modulus Index= 19 for value 802
Modulus Index= 1 for value 900
Modulus Index= 27 for value 723
Modulus Index= 3 for value 699
Number of Collisions = 1
Modulus Index= 1 for value 1
Number of Collisions = 2
Modulus Index= 16 for value 16
Number of Collisions = 2
Modulus Index= 13 for value 999
Number of Collisions = 3
Modulus Index= 20 for value 890
Number of Collisions = 3
Modulus Index= 0 for value 725
Number of Collisions = 3
Modulus Index= 12 for value 998
Number of Collisions = 3
Modulus Index= 21 for value 978
Number of Collisions = 4
Modulus Index= 2 for value 988
Number of Collisions = 7
Modulus Index= 4 for value 990
Number of Collisions = 9
Modulus Index= 3 for value 989
Number of Collisions = 14
Modulus Index= 27 for value 984
Number of Collisions = 15
Modulus Index= 1 for value 320
Number of Collisions = 23
Modulus Index= 2 for value 321
Number of Collisions = 31
Modulus Index= 23 for value 400
Number of Collisions = 31
Modulus Index= 9 for value 415
Number of Collisions = 37
Modulus Index= 15 for value 450
Number of Collisions = 40
Modulus Index= 21 for value 50
Number of Collisions = 43
Modulus Index= 22 for value 660
Number of Collisions = 47
Modulus Index= 15 for value 624
Number of Collisions = 61
Sum of Collisions = 61
Average of Collisions = 2.0
-----------------------------------------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
-----------------------------------------------------------------------
| 725 | 900 | 1 | 235 | 699 | 988 | 990 | 268 | 989 | 320 |
-----------------------------------------------------------------------
-----------------------------------------------------------------------
| 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
-----------------------------------------------------------------------
| 321 | 214 | 998 | 100 | 999 | 415 | 16 | 510 | 450 | 802 |
-----------------------------------------------------------------------
-----------------------------------------------------------------------
| 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
-----------------------------------------------------------------------
| 890 | 398 | 978 | 400 | 50 | 170 | 660 | 723 | 984 | 624 |
-----------------------------------------------------------------------
BUILD SUCCESSFUL (total time: 0 seconds)
Итак, как видите, я настроил его так, чтобы он сообщал мне среднее количество коллизий, произошедших при построении этой конкретной хеш-таблицы. Для них есть 30 номеров и 30 мест. Я попытался изменить параметр количества доступных мест с 30 до 60, но это ничего не изменило, и я хочу выяснить, как это исправить.
Это важно для меня, потому что я хочу поднять этот код на ступеньку выше. Я хотел бы попробовать эту программу для большего набора чисел, возможно, тысячи или более, но я не хочу просто вручную вводить еще тысячу строковых чисел. Как мне написать цикл, который сделает это за меня? Например, если я поставлю 1000 в его параметр, он выдаст тысячу чисел в строковой нотации (как видно из кода), которые будут использоваться.
Я также хочу сделать так, чтобы несколько таких строковых чисел выполнялись при выполнении одной программы. Например, хеш-таблица может содержать 1000 чисел, поэтому она будет запускать программу с 1 числом, затем с 2,3 и т. д., пока не дойдет до 1000. И каждый раз, когда она делает это , я хочу, чтобы он выводил среднее количество столкновений, произошедших в этом конкретном прогоне. Только с 1 числом не будет столкновений, и в конечном итоге столкновения будут происходить по мере увеличения количества чисел.
Сделав это, я мог бы затем построить график, показывающий, как количество столкновений меняется по мере изменения отношения чисел к доступным местам. Например, по оси X будет среднее количество столкновений, а по оси Y будет отношение количества введенных чисел к общему количеству доступных мест (это означает, что оно будет иметь диапазон значений от 0 до 1,00).
Заранее благодарю всех, кто найдет время, чтобы научить меня. Я очень ценю это.
Random
? - person Hungry Blue Dev   schedule 03.03.2014