(Amateur Programmer) Custom HashMap size is always one less than expected?

Question

Good afternoon,

For my current Computer Science course our professor has us implementing a HashMap class without utilizing Java's built in Map class ( besides using the interface it ). I've finished most of it and am in debugging mode now. My professors grading server is telling me I'm always returning one "size" less than is expected ie. my class is returning size 48 when size 49 is expected. I think i've narrowed it down to being in the put() method, because its the only method where the size is being incremented upwards, but i'm not sure. Any information about the class would be appreciated. Also, as a important side note, i'm utilizing the "chaining" collision resolution technique.

Thanks everyone !

  {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

@cricket_007 spotted where you got it wrong, but I wanted to post my version anyway. I think it is more readable, with a clearer logic.

@Override
public V put(K key, V value) {
    int index = hash(key) % table.length;

    Entry<K, V> prev = null;        
    for (Entry<K, V> entry = table[index]; entry != null; prev = entry, entry = entry.next) {
        if (Objects.equals(entry.key, key)) {
            V res = entry.value;
            entry.value = value;
            return res;
        }
    }

    Entry<K, V> newEntry = new Entry<K, V>(key, value);

    if (prev == null) table[index] = newEntry;
    else              prev.next = newEntry;

    size++;
    return null;
}

This code has two clearly distinct parts : the first part is a search through the existing keys until you exhaust all of them. As soon as you find one matching the key passed as a parameter, you can return.

The second part is what happens when no match was found. In this case, the size is always incremented. This makes it very clear when you need or need not to increment the size and insert and element.

Bonus: Objects.equals handles the case where the existing key is null. If you use it in conjunction with Objects.hashCode or any hash that accepts null, your map can support null keys.

Answer 2

In general, there seems to be several cases where you pre-increment the e value to e.next without even comparing e.key.

Take put, for example, since that is what we are talking about.

1. You get an entry from the table
2. While the key after it is not null and it's current key doesn't equal the key you want to put...
3. Move the entry??? Why? You haven't checked the first entry if it's key equaled anything yet.

You are skipping the first Entry's key.

You should be treating it like a for-loop. Initialize, test some condition, then increment

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;
}

Or, you could just rewrite it as a for-loop like this

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
    }
}

Almost every method in your code seems to do the same pre-increment thing and it is causing you to skip the first Entry's key.

---

Another problem with the approach you have is the section of the while-loop that says e.key.equals(key) == false.

(Ignoring the fact that you can rewrite that as I have above)... if the keys were equal, then the entire while-loop will be skipped.

My suggestion would be to simply remove that condition from the while because you are comparing the keys inside the while loop anyways.

---

Back to put specifically, though.

Your if-else condition doesn't match up. The variables you are comparing are different, so there is no "else" condition. You need two separate if statements that handle your different conditions like so. And

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;
}