重新散列put方法中的散列映射

Question

我正在尝试用Java实现一个单独链接的哈希表。在put()-method中，如果加载因子(nr-of-element/size-of-array)变得很大，我想重新散列映射。为此，我编写了另一个方法rehash()，它通过将数组/容量的大小加倍，然后再次添加所有条目来重新散列列表(至少这是我希望它做的事情)。问题是，当我测试它时，我得到了一个"java.lang.OutOfMemoryError: Java heap space“，我猜这是因为我也在rehash()方法中调用了put()方法。问题是我真的不知道如何解决这个问题。我想知道是否有人可以检查我的代码，并给我反馈或给我一个提示如何继续。下面代码中的Entry是散列映射类中的嵌套私有类。

提前感谢！

put()-method：

public V put(K key,V value) {
    int idx = key.hashCode()%capacity;  //Calculate index based on hash code.
    if(idx<0) {    
        idx+=this.capacity;  //if index is less than 0 add the length of the array table
    }
    if(table[idx]==null) {   //If list at idx is empty just add the Entry-node
        table[idx] = new Entry<K,V>(key,value);
        nr_of_keys +=1;
        if(this.load()>=this.load_factor) {  //Check if load-factor is greater than maximum load. If this is the case rehash.
            rehash();
        }
        return null;
    } else {
        Entry<K,V> p = table[idx];  //dummy pointer
        while(p.next!=null) { //while next node isn't null move the pointer forward
            if(p.getKey().equals(key)) {    //if key matches:
                if(!p.getValue().equals(value)) { //if value don't match replace the old value.
                    V oldVal = p.getValue();
                    p.setValue(value);
                    return oldVal; 
                }
            } else {
                p=p.next;
            }
        }
        if(p.getKey().equals(key)) {   //if the key of the last node matches the given key:
            if(!p.getValue().equals(value)) {
                V oldVal = p.getValue();
                p.setValue(value);
                return oldVal;
            } else {
                return null;
            }
        }
        p.next = new Entry<K,V>(key,value); //key doesn't exist so add (key,value) at the end of the list.
        nr_of_keys +=1;
        if(this.load()>=this.load_factor) { //if load is to large rehash()
            rehash();
        }
        return null;
    }
    
}

Rehash()-method：

public void rehash() {
    Entry<K,V>[] tmp = table;  //create temporary table
    int old_capacity = this.capacity;  //store old capacity/length of array.
    this.capacity = 2*capacity; //New capacity is twice as large
    this.nr_of_keys=0; //reset nr. of keys to zero.
    table = (Entry<K, V>[]) new Entry[capacity];  //make this.table twice as large
    for(int i=0; i<old_capacity;i++) { //go through the array
        Entry<K,V> p = tmp[i]; //points to first element of list at position i.
        while(p!=null) {
            put(p.getKey(), p.getValue());
            p=p.next;
        }
    }
}

load()-method：

public double load() {
    return((double) this.size())/((double)this.capacity);
}

其中size()返回map中(key，value)对的数量，capacity是数组表(存储链表的地方)的大小。

Answer 1

一旦你更新了你的地图，所有的东西都不一样了。条目集的存储桶，等等。

• 创建临时表。
• 通常使用当前的get方法获取值。然后，
• 会根据重新散列到新的时段大小创建新的时段，并将新容量添加到表中。(不使用PUT)。
• 然后用刚刚创建的表替换现有的表。确保与新表大小相关的所有值也被更改，例如基于threhholds、capcity等的存储桶选择方法。

最后，使用print语句跟踪新的存储桶以及存储桶之间的项目移动。

Answer 2

您已经添加了rehash()，但仍然缺少load()实现(或内部加载，即size())。

不过，模式看起来很清楚，并允许猜测，等待这些额外的信息。

您告诉我们，当负载因子达到put中的某个点时，您会重新进行散列。这种重新散列会使内部数组加倍，并再次调用put。最后你就没有了记忆。

其中，我打赌会有一些微妙或不那么微妙的递归发生在你放置的地方，它通过加倍内存使用来重新散列，然后重新放置，这以某种方式创建了一个rehashing……

第一种可能性是，有一些跟踪数组状态的内部变量没有正确重置(例如，占用条目的数量，...)。将“旧”数组数据与正在构建的新数组数据混淆可能是罪魁祸首。

另一种可能是您的put实现，但它需要一步一步的调试-我建议您执行。