Java:如何使这个哈希表函数在更大的范围内工作

Question

我有以下代码，它将获取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个将要使用的数字。

我还想让它在一个程序执行中运行多个这样的字符串数字。例如，哈希表可以容纳1000个数字，因此它将用1个数字运行程序，然后用2，3等……直到它一直运行到1000。每次它这样做时，我希望它输出在特定运行中发生的碰撞的平均次数。只有1个数字就不会发生碰撞，并且随着数字数量的增加，最终会发生碰撞。

通过这样做，我可以绘制一张图，显示碰撞量如何随着数量与可用点的比率的变化而变化。例如，x轴将是平均碰撞，y轴将是输入数量与总可用空间的比率(意味着它的值范围从0到1.00)

提前感谢所有花时间教我的人。我真的很感激。

Answer 1

要让程序为您随机生成数字，您应该创建一个方法，该方法接受一个整数参数，该参数在该大小的数组中循环并插入一个随机数。

int size_of_hash = Integer.parseInt( args[1] );

上面的代码将从命令行中获取一个参数，并使用它来创建一个变量，该变量决定哈希表的大小

你可以调用一个方法

public int[] createRandomArray( int size ) {
Random r = new Random(); //java.util.Random - this class will randomly generate integers for you
int random_array = //instantiate the array
for( int i = 0; i <= size; i++ ) {
//insert logic
}
return random_array;
}

该方法不完整。最好的学习方法是做。这里需要注意的重要一点是，这种方法本质上是接受一个简单的重复任务，并让程序为你做。Javadocs是了解java生态系统中新资源的绝佳资源。只要谷歌一下"javadocrandom"，就会出现这个类。

我建议将main方法更改为类的构造函数，并重写main方法以调用一些可以在程序参数中指定的试验。这将帮助你通过运行大量的试验而不是一次来获得更准确的数据。

Answer 2

使用以下内容：

import java.util.Random; //that's where it is.
...
...//directly to the class
private Random r = new Random();
public String randomString(int limit)
{
int n = r.nextInt(limit);
return n+"";
}
...

这将返回limit内的String形式的随机数(0到极限-1)。如果您想要一个n数字字符串，请执行此

StringBuilder s = new StringBuilder();
for(int i = 0; i < n; i++)
s.append(r.nextInt(10));
return s.toString();