我正在尝试比较链接和双重探测。 我需要向表大小 100 插入 40 个整数, 当我用 nanotime 测量时间时(在 java 中) 我知道双倍更快。 那是因为在Chaining的Insert方法中,我每次都会创建LinkedListEntry, 现在是添加时间。 为什么 Chaining 比 Double 探测更快? (这是我在维基百科上读到的)
谢谢!!
这是链接代码:
public class LastChain
{
int tableSize;
Node[] st;
LastChain(int size) {
tableSize = size;
st = new Node[tableSize];
for (int i = 0; i < tableSize; i++)
st[i] = null;
}
private class Node
{
int key;
Node next;
Node(int key, Node next)
{
this.key = key;
this.next = next;
}
}
public void put(Integer key)
{
int i = hash(key);
Node first=st[i];
for (Node x = st[i]; x != null; x = x.next)
if (key.equals(x.key))
{
return;
}
st[i] = new Node(key, first);
}
private int hash(int key)
{ return key%tableSize;
}
}
}
这是双重探测的相关代码:
public class HashDouble1 {
private Integer[] hashArray;
private int arraySize;
private Integer bufItem; // for deleted items
HashDouble1(int size) {
arraySize = size;
hashArray = new Integer[arraySize];
bufItem = new Integer(-1);
}
public int hashFunc1(int key) {
return key % arraySize;
}
public int hashFunc2(int key) {
return 7 - key % 7;
}
public void insert(Integer key) {
int hashVal = hashFunc1(key); // hash the key
int stepSize = hashFunc2(key); // get step size
// until empty cell or -1
while (hashArray[hashVal] != null && hashArray[hashVal] != -1) {
hashVal += stepSize; // add the step
hashVal %= arraySize; // for wraparound
}
hashArray[hashVal] = key; // insert item
}
}
这样,Double 中的插入比 Chaining 更快。 我该如何修复它?
最佳答案
链接在高负载系数下效果最佳。尝试在 100 个表格中使用 90 个字符串(不是一个很好的整数选择)。
此外,链接更容易实现移除/删除。
注意:在HashMap中,无论链式与非链式,都会创建一个Entry对象,而不是不保存。
关于java - 链式哈希 VS 双重探测,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13838647/