Map class made easy for beginners to understand

Question

I want to explain to beginners what a Map is in Java, with the assumption that beginners do not understand what a hashcode is.

As I developed games (Tarot, Belote, President, Pokemon), I know Java pretty well and I do not understand why overriding hashcode considering that I developed a Map class that looks like the standard HashMap class.

Besides, order of entries is not random unlike the standard HashMap class. The order of entries in my custom Map class is the order of inserting them. Besides, I think that my Map objects are lighter than objects of the standard HashMap class.

I hope that beginners will understand better collections with my customized class.

package util;

import java.io.Serializable;

public final class EntryCust<K, V> implements Serializable {

    private static final String SEPARATOR = " ";

    private K key;

    private V value;

    public EntryCust(K _k, V _v) {
        key = _k;
        value = _v;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V _v) {
        value = _v;
    }

    @Override
    public boolean equals(Object _obj) {
        if (!(_obj instanceof EntryCust)) {
            return false;
        }
        //EntryCust is a final class, so testing "_obj instanceof EntryCust" is sufficient.
        EntryCust<?,?> pair_ = (EntryCust<?,?>) _obj;
        if (key == null) {
            if (value == null) {
                if (pair_.value != null) {
                    return false;
                }
                return pair_.key == null;
            }
            if (!value.equals(pair_.value)) {
                return false;
            }
            return pair_.key == null;
        }
        if (value == null) {
            if (!key.equals(pair_.key)) {
                return false;
            }
            return pair_.value == null;
        }
        if (!key.equals(pair_.key)) {
            return false;
        }
        if (!value.equals(pair_.value)) {
            return false;
        }
        return true;
    }

    @Override
    public String toString() {
        return key+SEPARATOR+value;
    }
}

Keys of my maps are compared ONLY with "equals" method in order to make much easier to understand functionment of maps. I want to serialize my maps with the Serializable interface.

package util;

import java.io.Serializable;
import java.util.ArrayList;

/**Serializable interface is used for serializing this map*/
public class Map<K, V> implements Serializable {

    /**list cannot be null, even by reflection.
    New entries are appended to the list
    in order to code better tests about order of entries*/
    private final ArrayList<EntryCust<K, V>> list = new ArrayList<EntryCust<K, V>>();

    //Default constructor
    public Map() {
    }

    //Copy the map object but not the entries
    public Map(Map<? extends K, ? extends V> _arg0) {
        putAllMap(_arg0);
    }

    //Return the entries
    public ArrayList<EntryCust<K,V>> entryList() {
        return list;
    }

    //Only equals method is used if the parameter _key is not null.
    //hashcode is too much hard for using by beginners
    public V get(K _key) {
        if (_key == null) {
            for (EntryCust<K, V> e:entryList()) {
                if (e.getKey() == null) {
                    return e.getValue();
                }
            }
            return null;
        }
        for (EntryCust<K, V> e:entryList()) {
            if (_key.equals(e.getKey())) {
                return e.getValue();
            }
        }
        return null;
    }
    //The contains method uses only equals on the parameter _key
    public boolean contains(K _key) {
        return getKeys().contains(_key);
    }
    //The contains method uses only equals on the parameter _key
    public boolean has(V _value) {
        return values().contains(_value);
    }
    public ArrayList<V> values() {
        ArrayList<V> s_ = new ArrayList<V>();
        for (EntryCust<K, V> e: list) {
            s_.add(e.getValue());
        }
        return s_;
    }

    //Only equals method is used if the parameter _key is not null.
    public void put(K _key, V _v) {
        if (_key == null) {
            int i_ = 0;
            for (EntryCust<K, V> e: list) {
                if (e.getKey() == null) {
                    list.get(i_).setValue(_v);
                    return;
                }
                i_++;
            }
            list.add(new EntryCust<K, V>(_key, _v));
            return;
        }
        int i_ = 0;
        for (EntryCust<K, V> e: list) {
            K key_ = e.getKey();
            if (_key.equals(key_)) {
                list.get(i_).setValue(_v);
                return;
            }
            i_++;
        }
        list.add(new EntryCust<K, V>(_key, _v));
        return;
    }

    //Only equals method is used if the parameter _key is not null.
    public void remove(K _key) {
        if (_key == null) {
            int i_ = 0;
            for (EntryCust<K, V> e:entryList()) {
                if (e.getKey() == null) {
                    entryList().remove(i_);
                    return;
                }
                i_++;
            }
            return;
        }
        int i_ = 0;
        for (EntryCust<K, V> e:entryList()) {
            K key_ = e.getKey();
            if (_key.equals(key_)) {
                entryList().remove(i_);
                return;
            }
            i_++;
        }
    }

    public ArrayList<K> getKeys() {
        ArrayList<K> s_ = new ArrayList<K>();
        for (EntryCust<K, V> e: list) {
            s_.add(e.getKey());
        }
        return s_;
    }

    //Clear the map entries
    public void clear() {
        list.clear();
    }

    //Put the entries of an other map using equals on keys
    public void putAllMap(Map<? extends K, ? extends V> _m) {
        for (EntryCust<? extends K,? extends V> e: _m.entryList()) {
            put(e.getKey(), e.getValue());
        }
    }

    //Test is the map is empty or not
    public boolean isEmpty() {
        return list.isEmpty();
    }

    //Return the number of entries
    public int size() {
        return list.size();
    }

    //Return the string representation of the map
    @Override
    public String toString() {
        return list.toString();
    }
}

Answer 1

General best practices

These have already been mentioned by h.j.k:

• The naming conventions: You should not start or end variable names with underscores. From https://docs.oracle.com/javase/tutorial/java/nutsandbolts/variables.html :

  while it's technically legal to begin your variable's name with "_", this practice is discouraged

• Program against an interface. This may refer to the fact that java.util.Map is an interface, but also to your use of existing classes. For example,

  private final ArrayList<EntryCust<K, V>> list = new ArrayList<EntryCust<K, V>>();
  

  should rather be

  private final List<EntryCust<K, V>> list = new ArrayList<EntryCust<K, V>>();
  

  Similarly, the method public ArrayList<K> getKeys() should be public List<K> getKeys().

  While this does not seem so important in this particular case, it is tremendously important at other places: Using something like ArrayList, for example, as a method parameter (instead of List) may severely limit the flexibility of the resuling code

Serialization

When you let a class implement Serializable, then this class should have a "serial version UID". From http://docs.oracle.com/javase/8/docs/api/java/io/Serializable.html:

The serialization runtime associates with each serializable class a version number, called a serialVersionUID, which is used during deserialization to verify that the sender and receiver of a serialized object have loaded classes for that object that are compatible with respect to serialization.

So both of your classes should have a field

/**
 * Serial UID
 */
private static final long serialVersionUID = -6283423393897475782L;

(with different numbers - these just serve as a "version number")

Protect your private parts!

You have this method:

//Return the entries
public ArrayList<EntryCust<K,V>> entryList() {
    return list;
}

This makes me shudder a bit. It might be inspired by the java.util.Map#entrySet method, but note that this method claims very specific and delicate constraints on the returned Set and its relationship to the Map. With the method that you offered, someone could write

someMap.entryList().add(new EntryCrust<K,V>(null, null));
someMap.entryList().add(new EntryCrust<K,V>(null, null));
someMap.entryList().add(new EntryCrust<K,V>(null, null));

which would mess up the internal state of your map in an unrecoverable way. It will then, for example, contain the key null at least 3 times!)

More generally speaking, and more in line with what h.j.k said at the end: From the methods that are currently offered in your class, it is clear (and to some extent, nearly necessary) that it is implemented as a List of entries. While this may be appropriate to get the point across, it's certainly not a "good" solution.

"Memory and Performance"

I'm hesitating a bit to point this out. But for some methods, you used a certain approach for the implementation - for example, in this one:

//The contains method uses only equals on the parameter _key
public boolean contains(K _key) {
    return getKeys().contains(_key);
}

This approach can roughly be described as implementing methods based on existing methods. And in general, this is a good thing. But you should always keep in mind that this may have undesirable side effects. Apart from the fact that this method has O(n) running time (which can hardly be avoided when the implementation is based on a List), this method will create a new list containing all keys each time that the method is called. If you iterated directly over the entries, this would not be necessary.

---

Redundant redundancy is redundant

The different treatment of the case where the key is null and the cases where it is not null cause some redundancy. While one could argue about whether this is a problem, I think that much of this redundancy could be avoided. To some extent, this could already be achieved with the Objects.equals methdo that was already mentioned. But just as a thought: One could introduce two private helper methods

/**
 * A PRIVATE helper method that returns the index of the entry with the 
 * given key, or -1 if there is no such entry
 * 
 * @param key The key
 * @return The index, or -1
 */
private int indexOfEntryForKey(K key)
{
    for (int i=0; i<list.size(); i++)
    {
        EntryCust<K, V> entry = list.get(i);
        if (Objects.equals(entry.getKey(), key))
        {
            return i;
        }
    }
    return -1;
}

/**
 * A PRIVATE helper method that returns the entry with the given key, 
 * or <code>null</code> if there is no such entry
 * 
 * @param key The key
 * @return The entry, or <code>null</code>
 */
private EntryCust<K, V> entryForKey(K key)
{
    int index = indexOfEntryForKey(key);
    if (index == -1)
    {
        return null;
    }
    return list.get(index);
}

These could significantly simplify the implementations of the other methods. For example, the get/put/remove method could then just be written as

public V get(K key) 
{
    EntryCust<K, V> entry = entryForKey(key);
    if (entry == null)
    {
        return null;
    }
    return entry.getValue();
}

public void put(K key, V v) {

    EntryCust<K, V> entry = entryForKey(key);
    if (entry != null)
    {
        entry.setValue(v);
        return;
    }
    list.add(new EntryCust<K, V>(key, v));
    return;
}

public void remove(K key) 
{
    int index = indexOfEntryForKey(key);
    if (index != -1)
    {
        list.remove(index);
    }
}

which might be easier for beginners to understand - and this was one key point of your actual question.

Answer 2

The good

Let's start with something (unfortunately) short: Making EntryCust a final class is a good start.

Interfaces over implementations

It's highly recommended to declare variables or method return types based on interfaces over implementations, as users of the variables/methods should not need to know how the object works, but what they can use it for.

Simplifyingif logic

You can use Objects.equals(Object, Object) to simplify the seemingly complex-looking if chains inside EntryCust.equals(Object) to:

public boolean equals(Object other) {
    return other instanceof EntryCust
            && Objects.equals(key, ((EntryCust) other).key)
            && Objects.equals(value, ((EntryCust) other).value);
}

(thanks @Marco13!)

Putting entries and final-izing the key

You do a List.get(int) call inside your iteration over your EntryCust objects when you have identified the entry to update. I think you can simply call your EntryCust.setValue(V) to do so.

On a related note, since you are not expecting to change the key after creating an EntryCust object, you can make the variable final:

public final class EntryCust<K, V> implements Serializable {
    private final K key;
    private V value;
    // ...
}

Type inference and naming conventions

From Java 7, you can replace most of your type usage with just the <> angle brackets, which is known as type inference. For example:

List<V> list = new ArrayList<>();

Your naming convention is bizarre, with the use of underscore either as a suffix or prefix pretty much throughout. Are there any particular reasons why you are doing so to identify external variables (e.g. method parameters) and internal ones (e.g. those declared inside methods)?

Also, it's highly recommended not to give your own class the same name as the commonly used JDK classes, i.e. Map. Your IDE of choice or even yourself may wrongly use either versions when you least expect it.

Predictable iteration on a Map

I hope you know that there are Map implementations with predictable iteration order, such as the LinkedHashMap implementation and the family of SortedMap interface implementations, e.g. TreeMap.

Getting the concept right part 1: Hash codes and Maps:

This is one important point that links the previous section to the next:

The Map interface says nothing about hash codes and how keys and values are stored. That's just how the HashMap implementation works.

For example, a TreeMap compares by keys and inserts/iterates them in that order, it does not rely on hash codes.

Getting the concept right part 2: Is a Map just a List of pairs?

While you may have good intentions at the start, your Map implementation has revealed its false intentions the moment it returns a List for keys. Another way of describing a map is as an associative array, and to borrow its wiki entry:

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

(emphasis mine)

An ordinary List imposes no such restriction, only a Set. If you had gone with a Set-based approach, at least it's still a passable, good-hearted attempt at a 'map' implementation that only relies on equals() comparison, which is ok in itself.

As it stands now, I'll be very cautious using it as a 'map'-like replacement.

Answer 3

I developed a method that remove duplicates of keys like this:

public void removeDuplicatesAndNullEntries() {
    int i = 0;
    while (true) {
        if(i >= size()) {
            break;
        }
        EntryCust<K,V> entryOne = list.get(i);
        if (entryOne == null) {
            //Remove the "null" entry, the size of the list decrease by one
            list.remove(i);
            continue;
        }
        int j = i;
        j++;
        while (true) {
            if (j >= size()) {
                break;
            }
            EntryCust<K,V> entryTwo = list.get(j);
            if (entryTwo == null) {
                //Remove the "null" entry, the size of the list decrease by one
                list.remove(j);
                continue;
            }
            K keyOne = entryOne.getKey();
            K keyTwo = entryTwo.getKey();
            if (Objects.equals(keyOne, keyTwo)) {
                list.remove(j);
            } else {
                j++;
            }
        }
        i++;
    }
}

Can this method be used for removing possible duplicates key and null entries?