1

在我检查负载因子是否指示要调整大小的后备阵列之后，我实际上如何通过二次探测来调整大小？

这是代码。这只是课堂的一部分。另外，你能检查一下我是否正确地实现了 add 方法吗？

import java.util.*;

public class HashMap<K, V> implements HashMapInterface<K, V> {

// Do not make any new instance variables.
private MapEntry<K, V>[] table;
private int size;

/**
 * Create a hash map with no entries.
 */
public HashMap() {
    table = new MapEntry[STARTING_SIZE];
    size = 0;
}

@Override
public V add(K key, V value) {
    if (key == null || value == null) {
        throw new IllegalArgumentException("Passed in null arguments.");
    }
    if (getNextLoadFactor() > MAX_LOAD_FACTOR) {
        resize();
    }
    MapEntry<K, V> entry = new MapEntry<>(key, value);
    V val = null;
    int index = Math.abs(key.hashCode()) % table.length;
    int temp = index;
    int q = 1;
    do {
        if (table[index] == null) {
            table[index] = entry;
        } else if (table[index].getKey().equals(key)) {
            val = table[index].getValue();
            table[index].setValue(value);
        }
        index = index + q*q % table.length;
        q++;
    } while (temp != index);
    size++;
    return val;
}

private double getNextLoadFactor() {
    return (double) size / (double) table.length;
}

private void resize() {
    MapEntry<K, V>[] temp = table;
    table = new MapEntry[table.length * 2 + 1];
    for (int i = 0; i < table.length; i++) {

    }
}
4

1 回答 1

0

遵循wiki的以下内容：

 1. Get the key k
 2. Set counter j = 0
 3. Compute hash function h[k] = k % SIZE
 4. If hashtable[h[k]] is empty
         (4.1) Insert key k at hashtable[h[k]]
         (4.2) Stop
    Else
        (4.3) The key space at hashtable[h[k]] is occupied, so we need to find the next available key space
        (4.4) Increment j
        (4.5) Compute new hash function h[k] = ( k + j * j ) % SIZE
        (4.6) Repeat Step 4 till j is equal to the SIZE of hash table
 5. The hash table is full
 6. Stop

根据以上，在我看来，你的add方法有问题。注意步骤 (4.1) 和 (4.2)：如果table[index] == null，则已找到键的位置，您可以停止。您do将再次执行，因为在插入之后，您会更新索引，因此temp != index将是真的。

您还错误地计算了下一个索引，请更改

index = index + q*q % table.length;

至

index = (Math.abs(key.hashCode()) + q*q) % table.length;

遗嘱因此add变为：

MapEntry<K, V> entry = new MapEntry<>(key, value);
V val = null;
int index = Math.abs(key.hashCode()) % table.length;

int q = 0;

while (table[(index = (Math.abs(key.hashCode()) + q*q++) % table.length)] != null);

table[index] = entry;
size++;
return val;

可以证明，如果第一个位置的桌子大小b是唯一的，那么可以安全地假设如果桌子小于半满，你会发现一个空位置。这取决于您的.b > 3b/2(b/2 - 1)MAX_LOAD_FACTOR

为了调整大小，您需要将每个值重新散列到新表中。这是由于您的哈希函数使用表的大小作为模数。您的哈希函数已基本更改，因此您需要创建 的新数组size + 1，并将每个元素读取到新数组中。

private void resize() {
    MapEntry<K, V>[] temp = table;
    table = new MapEntry[table.length * 2 + 1];
    for (MapEntry<K, V> entry:temp) {
        this.add(entry.getKey(), entry.getValue());
    }
}

注意：我没有对此进行测试，仅使用动态探测和哈希表背后的理论来调试您的代码。希望能帮助到你！

于 2015-04-21T08:58:37.030 回答