java跟踪基于数组的哈希表中每个索引的冲突，以及哪些值仅使用开放寻址导致冲突
抱歉这个冗长的标题，但它很好地解释了我的问题
我正在用Java做一个作业，我需要创建自己的哈希表
规范是这样的，我必须使用数组，以及用于冲突处理的开放寻址（使用双哈希和二次哈希实现）
我的实现工作得很好，使用超过200000个随机生成的字符串，我最终只产生了约1400个冲突，这两种类型的冲突处理都提到过（将我的负载因子保持在0.6，当它结束时，将我的数组增加2.1）
这就是我被难倒的地方，然而。。。我的作业需要两个我无法理解的规范
1）有一个选项，当从表中删除一个值时，我必须找到另一个值，而不是使用“AVAILABLE”（将数组中的索引替换为指示其为空的垃圾值），该值之前散列到此索引并导致冲突。例如，如果值A散列到索引2，值B也散列到索引2（后来使用我的冲突处理散列函数将其重新散列到索引5），那么删除值A实际上会将其替换为值B
2）跟踪单个数组索引中的最大冲突数。我目前跟踪所有的碰撞，但我无法跟踪单个细胞的碰撞
我可以使用单独的链接来解决这个问题，方法是让每个数组索引保存一个包含所有已哈希到此索引的值的链表，这样当我调用get（value）方法时，只会检索第一个值，但删除后，我可以轻松地用哈希到此索引的下一个值替换它。这也是一种获取每个索引的最大冲突数的简单方法
但我们被告知不要使用单独的链接。。。我真的在想，这是否可能在不完全破坏哈希表复杂性的情况下实现
任何建议都将不胜感激
编辑：
以下是一些例子，让你了解我的班级结构：
公共课达维哈什{
//Attributes
public String[] dTable;
private double loadFactor, rehashFactor;
private int size = 0;
private String emptyMarkerScheme;
private String collisionHandlingType;
private int collisionsTotal = 0;
private int collisionsCurrent = 0;
//Constructors
public daveHash()
{
dTable = new String[17];
rehashFactor = 2.1;
loadFactor = 0.6;
emptyMarkerScheme = "A";
collisionHandlingType = "D";
}
public daveHash(int size)
{
dTable = new String[size];
rehashFactor = 2.1;
loadFactor = 0.6;
emptyMarkerScheme = "A";
collisionHandlingType = "D";
}
我的哈希函数：
public long getHashCode(String s, int index)
{
if (index > s.length() - 1)
return 0;
if (index == s.length()-1)
return (long)s.charAt(index);
if (s.length() >= 20)
return ((long)s.charAt(index) + 37 * getHashCode(s, index+3));
return ((long)s.charAt(index) + 37 * getHashCode(s, index+1));
}
public int compressHashCode(long hash, int arraySize)
{
int b = nextPrime(arraySize);
int index = ((int)((7*hash) % b) % arraySize);
if (index < 0)
return index*-1;
else
return index;
}
碰撞处理：
private int collisionDoubleHash(int index, long hashCode, String value, String[] table)
{
int newIndex = 0;
int q = previousPrime(table.length);
int secondFunction = (q - (int)hashCode) % q;
if (secondFunction < 0)
secondFunction = secondFunction*-1;
for (int i = 0; i < table.length; i++)
{
newIndex = (index + i*secondFunction) % table.length;
//System.out.println(newIndex);
if (isAvailable(newIndex, table))
{
table[newIndex] = value;
return newIndex;
}
}
return -1;
}
private int collisionQuadraticHash(int index, long hashCode, String value, String[] table)
{
int newIndex = 0;
for (int i = 0; i < table.length; i ++)
{
newIndex = (index + i*i) % table.length;
if (isAvailable(newIndex, table))
{
table[newIndex] = value;
return newIndex;
}
}
return -1;
}
public int collisionHandling(int index, long hashCode, String value, String[] table)
{
collisionsTotal++;
collisionsCurrent++;
if (this.collisionHandlingType.equals("D"))
return collisionDoubleHash(index, hashCode, value, table);
else if (this.collisionHandlingType.equals("Q"))
return collisionQuadraticHash(index, hashCode, value, table);
else
return -1;
}
获取、放置和移除：
private int getIndex(String k)
{
long hashCode = getHashCode(k, 0);
int index = compressHashCode(hashCode, dTable.length);
if (dTable[index] != null && dTable[index].equals(k))
return index;
else
{
if (this.collisionHandlingType.equals("D"))
{
int newIndex = 0;
int q = previousPrime(dTable.length);
int secondFunction = (q - (int)hashCode) % q;
if (secondFunction < 0)
secondFunction = secondFunction*-1;
for (int i = 0; i < dTable.length; i++)
{
newIndex = (index + i*secondFunction) % dTable.length;
if (dTable[index] != null && dTable[newIndex].equals(k))
{
return newIndex;
}
}
}
else if (this.collisionHandlingType.equals("Q"))
{
int newIndex = 0;
for (int i = 0; i < dTable.length; i ++)
{
newIndex = (index + i*i) % dTable.length;
if (dTable[index] != null && dTable[newIndex].equals(k))
{
return newIndex;
}
}
}
return -1;
}
}
public String get(String k)
{
long hashCode = getHashCode(k, 0);
int index = compressHashCode(hashCode, dTable.length);
if (dTable[index] != null && dTable[index].equals(k))
return dTable[index];
else
{
if (this.collisionHandlingType.equals("D"))
{
int newIndex = 0;
int q = previousPrime(dTable.length);
int secondFunction = (q - (int)hashCode) % q;
if (secondFunction < 0)
secondFunction = secondFunction*-1;
for (int i = 0; i < dTable.length; i++)
{
newIndex = (index + i*secondFunction) % dTable.length;
if (dTable[index] != null && dTable[newIndex].equals(k))
{
return dTable[newIndex];
}
}
}
else if (this.collisionHandlingType.equals("Q"))
{
int newIndex = 0;
for (int i = 0; i < dTable.length; i ++)
{
newIndex = (index + i*i) % dTable.length;
if (dTable[index] != null && dTable[newIndex].equals(k))
{
return dTable[newIndex];
}
}
}
return null;
}
}
public void put(String k, String v)
{
double fullFactor = (double)this.size / (double)dTable.length;
if (fullFactor >= loadFactor)
resizeTable();
long hashCode = getHashCode(k, 0);
int index = compressHashCode(hashCode, dTable.length);
if (isAvailable(index, dTable))
{
dTable[index] = v;
size++;
}
else
{
collisionHandling(index, hashCode, v, dTable);
size++;
}
}
public String remove(String k)
{
int index = getIndex(k);
if (dTable[index] == null || dTable[index].equals("AVAILABLE") || dTable[index].charAt(0) == '-')
return null;
else
{
if (this.emptyMarkerScheme.equals("A"))
{
String val = dTable[index];
dTable[index] = "AVAILABLE";
size--;
return val;
}
else if (this.emptyMarkerScheme.equals("N"))
{
String val = dTable[index];
dTable[index] = "-" + val;
size--;
return val;
}
}
return null;
}
希望这能让你了解我的方法。这不包括我上面提到的单独的链接实现。为此，我有以下内部类：
private class hashList
{
private class hashNode
{
private String element;
private hashNode next;
public hashNode(String element, hashNode n)
{
this.element = element;
this.next = n;
}
}
private hashNode head;
private int length = 0;
public hashList()
{
head = null;
}
public void addToStart(String s)
{
head = new hashNode(s, head);
length++;
}
public int getLength()
{
return length;
}
}
我的方法经过了适当的修改，可以访问头部节点中的元素，而不是数组中的元素。然而，我去掉了这个，因为我们不应该使用单独的链接来解决这个问题
谢谢
共 (0) 个答案