how to implement a Map in java correctly?

Question

So I am trying to implement my own Map to understand how it works. I did it by making 2 private lists in my implementation before, but I was told to use and Entry class. so the main question for me now is how can I compare a key of the Entry that is stored in the list? here is my code

   import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Optional;

public class CorrectMapImpl implements Map {
private List<Entry> entries = new ArrayList<>();

@Override
public Object put(Object key, Object value) {
    Entry entry = new Entry(key, value);
    if (entries.contains(entry)) {
        int index = entries.indexOf(entry);
        entries.set(index, (Entry) value);
    }else if(entries.contains()){

    } else  {
        entries.add(entry);
    };
    return entry.getValue();
}

@Override
public Object get(Object key) {
   //return entries.stream().filter(e -> e.getKey().equals(key)).findFirst().orElse(null).getValue();
    /*Optional<Entry> optionalEntry = entries.stream().filter(e -> e.getKey().equals(key)).findFirst();
    optionalEntry.ifPresent(Entry::getValue);
    return optionalEntry;*/
}

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

@Override
public Object remove(Object key) {
    boolean hasKey = false;
    int keyIndex = 0;
    for(Entry entry: entries) {
        if(entry.getKey().equals(key)) {
            hasKey = true;
            break;
        }
        keyIndex++;
    }
    if(hasKey) {
        return entries.remove(keyIndex).getValue();
    }
    return null;
}
//---------------------------------------------------------------------------------------------
class Entry {
    private Object key;
    private Object value;

    public Entry(Object key, Object value) {
        this.key = key;
        this.value = value;
    }

    public Object getKey() {
        return key;
    }

    public void setKey(Object key) {
        this.key = key;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Entry)) return false;
        Entry entry = (Entry) o;
        return Objects.equals(key, entry.key) &&
                Objects.equals(value, entry.value);
    }

    @Override
    public int hashCode() {
        return Objects.hash(key, value);
    }
}

} the "put" is not complitely written. I addet "else if" because without it "put" did't test the entries for the same key/different value, only if the instance of the Entry fully the same, both key and the value. And when I try to entry.put an new instance of entry with the same key, but different value, it doesnt overwrite the previous instance of the entry with the same key, as it has to, but adds a new instance so the size of the list increments. Also "get" implementation doesn't work. the first statement thows a NullPointerException, and the other tipes the class of the object like (CorrectMapImpl$Entry@cd440b02) instead of the value that is set to the key.

Answer 1

Right now you have a list of Entry objects. See the java API which states:

[contains] Returns true if this collection contains the specified element. More formally, returns true if and only if this collection contains at least one element e such that (o==null ? e==null : o.equals(e)).

That means when you wrote:

if (entries.contains(entry)) {

that is effectively equivalent to

for(Entry e : entries) if(e.equals(entry){...}

Your code for the equals() in the Entry class,

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Entry)) return false;
    Entry entry = (Entry) o;
    return Objects.equals(key, entry.key) &&
            Objects.equals(value, entry.value);
}

Means that a.equals(b) will only return true if both the key and the value are the same.

That's why you're code is failing. I don't think the correct solution would be to change the way you currently implement .equals() because the way you implemented it does define the equality of two Entry objects.

My suggestion would be to replace the .contains(entry) code with a manual loop through the list and manually comparing the keys. Something like this

for(int i = 0; i < entries.size(); i++){
  if(entries.get(i).getKey().equals(entry.getKey())) {
    index = i;
    break;
  }
}

Answer 2

Your Entry class should implement the Map.Entry interface.

The put method should look for an existing entry with the given key. You can do that with a for - loop:

    public Object put(Object key, Object value) {
        Entry foundEntry = null;
        for (Entry entry : entries) {
            if (key.equals(entry.getKey())) {
                foundEntry = entry;
            }
        }

When the loop finishes, either you have found an entry that has the same key, or not.

• If you have found an entry, you have to update its value.
• If you haven't found an entry, you have to create a new entry and add it to the map.

Don't forget you have to return the old value of the entry.

        if (foundEntry == null) {
            // Key not in map: create new Entry
            entries.add(new Entry(key, value));
            return null;
        } else {
            // Key already in map: update Entry
            Object oldValue = foundEntry.getValue();
            foundEntry.setValue(value);
            return oldValue;
        }
    }

The get method should look similar to the first part of the put method: First look for an entry that has the right key. If you find such an entry, return its value. Otherwise, return null.

the other tipes the class of the object like [CorrectMapImpl$Entry@cd440b02)

You need to add a toString method to Entry. See How do I print my Java object without getting "SomeType@2f92e0f4"?