java - (业余程序员)自定义HashMap大小总是比预期小1？

Question

下午好，

对于我当前的计算机科学类(class)，我们的教授让我们实现一个 HashMap 类，而不使用 Java 内置的 Map 类(除了使用它的接口(interface)之外)。我已经完成了大部分内容，现在处于 Debug模式。我的教授评分服务器告诉我，我总是返回比预期小一个“尺寸”，即。我的类(class)返回的是 48 号，而预期是 49 号。我认为我已经将其范围缩小到 put() 方法中，因为它是大小向上递增的唯一方法，但我不确定。任何有关类(class)的信息将不胜感激。另外，作为一个重要的旁注，我正在利用“链接”碰撞解决技术。

谢谢大家!

  {package adt;
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.HashSet;
  import java.util.Map;
  import java.util.Set;

  @SuppressWarnings("unchecked")


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

//linked list style
private class Entry<K, V> {
    private K key;
    private V value;
    private Entry<K, V> next;

    private Entry( K key, V value){
        this.key = key;
        this.value = value;
        this.next = null;
    }
}


private Entry<K, V>[] table = new Entry[1024]; // Creates a table of Entries. Because of the chaining implementation, each Entry will be treated like a linked list, so each Entry has a .next.
int size = 0;


public HashMap(){
    for(int i =0; i<table.length; i++){
        table[i] = null;
    }
}


@Override
public int size() {
    return size;
}

@Override
public boolean isEmpty() {
return size ==0;
}

@Override
public boolean containsKey(Object key) {
    int location = Hash(key) % table.length;
    Entry<K, V> e = table[location];
    if(table[location] == null){
        return false;
    }else{
        while (e!= null && e.key.equals(key) == false){
            e = e.next;

            if( e.key.equals(key)){
                return true;
            }
        }
    }
    return false;
}

@Override
public boolean containsValue(Object value) {
    for (int i = 0; i<table.length; i++){
        if(table[i] != null){
            Entry<K, V> e = table[i];
            while( e.value.equals(value)==false){
                e = e.next;
                if(e.value.equals(value)){
                    return true;
                }
            }
        }
    }
    return false;
}
@Override
public V get(Object key) {
    V value = null;
    int location = Hash(key)% table.length;
    if (table[location] == null){
        value = null;
    }else{
        Entry<K, V> e = table[location];

        while(e !=null && e.key.equals(key) == false){
            e = e.next;

            if (e == null){
                value = null;
            }
            else{
                value = (V) e.value;
            }
        }
    }
    return value;
}

@Override
public V put(K key, V value) {
    V returnValue = null;
    int location = Hash(key) % table.length;

    if ( table[location]== null){
        table[location] = new Entry< K, V>(key, value);
        size++;

    }
    else{
        Entry<K, V> e = table[location];
        while ( e.next != null && e.key.equals(key) == false){
            e = e.next;

            if( e.key.equals(key)){
                e.value = value;
                returnValue =  e.value;

            }else if(e.next == null){
                e.next = new Entry<K, V>(key, value);
                returnValue = e.value;
                size++;
            }

        }
    }

    return returnValue;

}

@Override
public V remove(Object key) {
    int location = Hash(key) % table.length;
    V value = null;
    Entry<K, V> e = table[location];
    if(table[location] == null){
        value = null;
    }else {
        while(e.next != null && e.key.equals(key) == false){
            e = e.next;
            if(e.key.equals(key)){
                value = e.value;
                e = null;
                size--;
            }else{
                value = null;

            }

        }
    }

    return value;
}

@Override
public void putAll(Map<? extends K, ? extends V> m) {
    // TODO Auto-generated method stub

}

@Override
public void clear() {
    for(int i =0; i<table.length; i++){
        table[i] = null;
    }
    size = 0;
}

@Override
public Set<K> keySet() {
    Set<K> s = new HashSet<K>();
    Entry<K, V> e;
    if(!isEmpty()){
    for(int i = 0; i<table.length; i++){
        e = table[i];
        if(e != null){
            s.add(e.key);
            while(e.next != null){
                s.add(e.key);
                e=e.next;
            }
        }
    }
    }
    return s;
}

@Override
public Collection<V> values() {
    Collection<V> c = new ArrayList<V>();
    Entry<K,V> e;
    if(isEmpty()==false){
        for(int i=0; i<table.length;i++){
            e = table[i];
            if(e != null){
                c.add(e.value);
                while(e.next !=null){
                    c.add(e.value);
                }
            }
        }
    }
    return c;
}

@SuppressWarnings("rawtypes")
@Override
public Set entrySet() {

    Set<Entry> s = new HashSet<Entry>();
    Entry<K,V> e;
    if(isEmpty()==false){
        for(int i = 0; i<table.length; i++){
            e = table[i];
            if( e!=null){
                while(e.next != null){
                    s.add(e);
                }
            }
        }
    }
    return s;
}

public int Hash(Object k){
    String key = k.toString();
    int n = 13;
    for(int i = 0; i<key.length(); i++){
    n += n + key.charAt(i);
    }
    n = n*31;
    return n;
}

public boolean equals(Object o){
    Map<K, V> m2;
    if( o instanceof Map){

    m2 = (Map<K,V>)o;
    if(entrySet().equals(m2.entrySet())){
        return true;
    }
}
    return false;
  }
 }  
}

Answer 1

一般来说，在某些情况下，您甚至无需比较 e.key 即可将 e 值预先递增到 e.next >。

以 put 为例，因为这就是我们正在讨论的内容。

1. 您从表格中获得一个条目
2. 虽然它后面的键不为空并且它的当前键不等于您要放置的键...
3. 移动条目？？？为什么？您还没有检查第一个条目的键是否等于任何内容。

您正在跳过第一个条目的 key 。

您应该将其视为 for 循环。初始化，测试某些条件，然后递增

int location = Hash(key) % table.length;
Entry<K, V> e = table[location];
while ( e.next != null && !e.key.equals(key)) {
    if( e.key.equals(key)) {
        // do some stuff 
    }
    e = e.next;
}

或者，您可以将其重写为这样的 for 循环

int location = Hash(key) % table.length;

for (Entry<K, V> e = table[location]; e.next != null && !e.key.equals(key); e = e.next) {
    if( e.key.equals(key)) {
        // do some stuff
    }
}

代码中的几乎每个方法似乎都执行相同的预增量操作，这导致您跳过第一个 Entry 的键。

<小时/>

您所采用的方法的另一个问题是 while 循环中显示 e.key.equals(key) == false 的部分。

(忽略您可以像上面那样重写的事实)...如果键相等，则将跳过整个 while 循环。

我的建议是简单地从 while 中删除该条件，因为无论如何您都会比较 while 循环内的键。

<小时/>

不过，具体回到put。

您的 if-else 条件不匹配。您要比较的变量不同，因此不存在“else”条件。您需要两个单独的 if 语句来处理不同的条件，如下所示。并且

if(e.next == null){
    e.next = new Entry<K, V>(key, value);
    size++;
    returnValue =  e.value;
}

if(e.key.equals(key)){
    e.value = value;
    returnValue =  e.value;
}