Map implementation.

While I haven't started yet, per se, I have an idea, kind of, how it might work.

Right now, it would seem I might have to use two parallel LinkedLists, or DoublyLinkedLists, as I have made such a custom LinkedList class already.

However, the problem is that maps don't have indexing per se.

I think an iterator might work, perhaps, but how do I get the elements in this Iterator?

I know I can have the MyMap<S,T> implement the Iterator<S> but how do I go through the either internal DoublyLinkedLists or some other data structure, in order to do this?

I could make it like a LinkedList, I think I'll HAVE to, in order for it to go through the elements at least. I need to have them linked somehow, right?

Any ideas on how to go about that?

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.

Actually, a sort of LinkedList would work. It wouldn't be an internal linked list, only it would involve next and previous links. However, it wouldn't be indexed, hence the possible need for the iterator. Also, I realize now that iterators are for Sets and the like, not maps or linked lists.

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

Why is that?

Code java:

---

 
 
   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.

What I'm baffled about is why my toString is only showing the first element, though my size method returns the right size and my getMethod() works fine.

Hello javapenguin!

I think it's interesting what you are trying to do so I studied your code a little bit.

Quote:

---

Originally Posted by javapenguin

What I'm baffled about is why my toString is only showing the first element

---

If you add some print statements you will see that only the if block of the toString() method is executing. This is because in your put method in the else if block you never change tail. Thus tail always equal head. If you fix that you will get a MyMap with a head and tail. And also it would help in your debbuging if you made a toString() for the MapNode class.

Quote:

---

Originally Posted by javapenguin

though my size method returns the right size and my getMethod() works fine.

---

But the main problem I see in your implementation is that you don't store somewhere the keys or the values of the map. A MyMap has only a head, a tail and size, which is only a counter of how many times the put method is called. To be more specific you cannot retrieve the value of a key if this isn't the head or the tail (the get method doesn't work except from these MapNodes - in your test try to get "Bob" and you will see it won't find it). You need to save (in a Set, ArrayList, or whatever) the keys and the values of your map.

Hope that makes sense.

PS: Just out of curiosity, is there a particular reason for not using the existing Map implementations as helloworld and copeg suggested?

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.

#-o

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.

Quote:

---

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.

Quote:

---

Originally Posted by javapenguin

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.

---

If you have the set of the keys and you know the next of every MapNode then you could probably get the MyMap.

Quote:

---

Originally Posted by javapenguin

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.

---

You should change tail every time in that put is called (i.e in each of the three blocks). In the if block you can do as you described it (tail = head). In the other two you should make tail equal to the new MapNode you create. i.e. for else if

Code :

---

 else if (...) {
 
            MapNode mapNode = new MapNode(key, value);       
            tail = mapNode;          
            size++;                          
            return value;
        }

---

Quote:

---

Originally Posted by javapenguin

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.

---

I'm not sure where this will help you with the above. If you want to check if a key already exists (thus you don't put it in your map) then you don't need to check for the value of it, the key alone is enough for the comparison - since in a map only keys must be unique not values.

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.

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.

Quote:

---

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)