Thread: Map implementation.

The two most common Map implementations use either hashes or binary search trees. You're right, it really doesn't really make sense to use a linked list or iterator, so don't (unless you have a good reason to). A map consists of a set of keys which each reference a value. My recommendation is to implement it like that: create a node class which contains a key and a value, then implement a set using the keys from the nodes.

See:
Associative array - Wikipedia, the free encyclopedia
Set (abstract data type) - Wikipedia, the free encyclopedia

As a side note, why go about re-implementing something you can get for free already, though? There's the HashMap and TreeMap classes in the java API already.

I tried an implementation, but it only seems to be adding the first one, and not any others.

Why is that?

 
 
   public class MyMap<K,V> 
   {
 
      private class MapNode<K,V>
      {
 
         K key;
         V value;
         MapNode<K,V> next;
 
 
         public MapNode(K key, V value)
         {
 
            this.key = key;
 
            setValue(value);
 
 
         }
 
 
         public void setValue(V value)
         {
 
            this.value = value;
         }
 
         public V getValue()
         {
            return value;
         }
 
         public K getKey()
         {
            return key;
 
         }
 
         public void setNext(MapNode<K,V> next)
         {
            this.next = next;
 
 
         }
 
         public MapNode<K,V> getNext()
         {
            return next;
 
         }
 
 
 
 
 
 
 
 
 
      }
 
 
 
      private MapNode<K,V> head;
      private MapNode<K,V> tail;
      private int size;
      public MyMap()
      {
 
 
         head = null;
         tail = null;
 
 
      }
 
      private boolean canAdd(K key, V value)
      {
 
         MapNode<K,V> temp = head;
 
         while (temp !=null)
         {
 
 
            if (temp.getKey().equals(key))
               return false;
 
            temp = temp.next;
 
 
 
         }
 
         return true;
      }
 
 
      public V put(K key, V value)
      {
 
 
         if (!canAdd(key, value))
         {
 
            System.err.println("This key is already here.");
            return value;
 
         }
         MapNode<K,V> temp = head;
 
 
         if (head == null && tail == null)
         {
 
            head = new MapNode(key, value);
 
            tail = head;
 
            size++;
            return value;
 
         }
 
         else if (head != null && head == tail)
         {
 
            temp.setNext(new MapNode(key, value));
 
 
            size++;
            return value;
 
 
 
 
         }
 
         else 
         {
 
 
 
            while (temp.next != tail)
            {
 
 
               temp = temp.next;
 
 
 
 
            }
 
            tail = new MapNode(key, value);
 
            temp.setNext(tail);
 
            size++;
 
 
            return value;
 
 
         }
 
 
 
 
 
 
      }
 
      public V get(K key)
      {
 
         if (head == null)
            return null;
 
         MapNode<K,V> temp = head;
 
         while (temp != null)
         {
 
            if (temp.getKey().equals(key))
               return temp.getValue();
 
            temp = temp.next;
 
         }
 
         return null;
 
 
      }
 
      public String toString()
      {
 
 
         if (head == null)
 
            return "[]";
 
 
 
         MapNode<K,V> temp = head;
 
         String str = "[";
       if (head != null && head == tail)
         {
 
            str = str + temp.getKey().toString() + "=" + temp.getValue().toString() + "]";
            return str;
         }
         while (temp != tail)
         {
 
            str = str + temp.getKey().toString() + "=" + temp.getValue().toString() + ",";
            temp = temp.next;
 
         }
 
         str = str + temp.getKey().toString() + "=" + temp.getValue().toString() + "]";
 
         return str;
 
 
      }
      public int size()
      {
 
         return size;
      }
 
 
 
      public static void main(String[] args)
      {
 
         MyMap<String,String> tester = new MyMap<String,String>();
 
         tester.put("Bob", "Mike");
 
         tester.put("Ben", "John");
 
       tester.put("Ruth", "Joe");
 
         System.out.println(tester.toString());
 
      System.out.println(tester.get("Ruth").toString());
 
      }
 
 
 
 
 
   }

What's mysterious though is that the size is 3, which it should be.

However, the toString() is only doing the first item in there.

Probably something stupid that I'm not noticing because I'm kind of tired.

Also, I added another line for a get() and used the last item I added and it found the corresponding value fine. It returned "Joe".

As helloworld mentioned, why try and reinvent the wheel? There are already Map implementations that should be more than sufficient in most contexts (HashMap, LinkedHashMap, TreeMap....), or rethink your design.

Just wanted to write a Map class for the fun of it.

Also, it works with a linked list. You are right. My get method won't get the middle nodes. Perhaps I should store the keys in a set class. That way I can get them all.

I have a setNext() method that should at least allow it to hop across the Map to find the keys.

I was wondeirng setting tail = head would make it a shallow copy.

I forgot that I would be changing the head value as well. I somehow thought that I could change tail later, but forgot that I'd be altering head too.



I did have an idea. I thought of adding an equals(Object obj) method that would return true if both the keys and the objects of the two objects corresponded.

Originally Posted by javapenguin

Just wanted to write a Map class for the fun of it.

Well for what its worth, that is not how to implement a Map. The advantage of a Map is that it provides constant time performance for its lookup/insert/delete methods - not linear time performance (a LinkedList is linear time). You need to implement a hash function, buckets, and some manner to deal with hash collision if you wish to implement this correctly.

As to that, if it's already there, the method, somewhat based upon the java Map interface, returns a Value. Hence I had to return something.

Found the problem I think

I had

while(temp.next !=tail)

and I should have had

while(temp != tail)

instead.

Originally Posted by javapenguin

Constant time? I thought it was more like logarithmic time. If you used hashing or an AVL tree, then you'd have about logarithmic time. It would probably get a bit closer to linear with hashing, though even with the best hash functions, it's not quite constant time. At least that's what I heard.

Anyway, I thought my approach would work, however inefficient it was.

If implemented correctly and with minimum number of collisions, SOME of a Map's methods are constant (or approximately constant) time. Regardless of 'what you heard', why not prove it to yourself? A Map is far from a tree, and it is far from a linked list.

I am trying to point in the correct direction...if you want to piece together a hacked linked list that ostensibly has key value pairs, please be advised it is not a true hash lookup Map or table (and I would even hesitate to call it a Map). If you want to implement a Map/HashTable correctly, then I recommend reading about what it entails. Wikipedia has a good overview. But, as history has proven, I don't have much confidence you will listen to my advice (which makes me question why I am giving it in the first place)