Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 13 of 13

Thread: Map implementation.

  1. #1
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default 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?


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: 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.
    Last edited by helloworld922; June 3rd, 2012 at 07:12 PM.

  3. #3
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Map implementation.

    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.

  4. #4
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Map implementation.

    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".
    Last edited by javapenguin; June 3rd, 2012 at 11:03 PM.

  5. #5
    Super Moderator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,104
    Thanks
    169
    Thanked 780 Times in 726 Posts
    Blog Entries
    5

    Default Re: Map implementation.

    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.

  6. #6
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Map implementation.

    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.

  7. #7
    Member
    Join Date
    Jan 2012
    Location
    Hellas
    Posts
    284
    Thanks
    11
    Thanked 59 Times in 57 Posts

    Default Re: Map implementation.

    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 View Post
    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 View Post
    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?

  8. The Following User Says Thank You to andreas90 For This Useful Post:

    javapenguin (June 4th, 2012)

  9. #8
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Map implementation.

    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.
    Last edited by javapenguin; June 4th, 2012 at 11:34 AM.

  10. #9
    Super Moderator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,104
    Thanks
    169
    Thanked 780 Times in 726 Posts
    Blog Entries
    5

    Default Re: Map implementation.

    Quote Originally Posted by javapenguin View Post
    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.

  11. #10
    Member
    Join Date
    Jan 2012
    Location
    Hellas
    Posts
    284
    Thanks
    11
    Thanked 59 Times in 57 Posts

    Default Re: Map implementation.

    Quote Originally Posted by javapenguin View Post
    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 View Post

    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
     else if (...) {
     
                MapNode mapNode = new MapNode(key, value);       
                tail = mapNode;          
                size++;                          
                return value;
            }

    Quote Originally Posted by javapenguin View Post
    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.

  12. The Following User Says Thank You to andreas90 For This Useful Post:

    javapenguin (June 4th, 2012)

  13. #11
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Map implementation.

    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.

  14. #12
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Map implementation.

    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.
    Last edited by javapenguin; June 4th, 2012 at 12:59 PM.

  15. #13
    Super Moderator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,104
    Thanks
    169
    Thanked 780 Times in 726 Posts
    Blog Entries
    5

    Default Re: Map implementation.

    Quote Originally Posted by javapenguin View Post
    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)
    Last edited by copeg; June 4th, 2012 at 01:12 PM.

Similar Threads

  1. Vector implementation
    By poolman81 in forum Collections and Generics
    Replies: 11
    Last Post: June 3rd, 2012, 06:45 AM
  2. JAAS Implementation with JSF
    By mhwish in forum JavaServer Pages: JSP & JSTL
    Replies: 0
    Last Post: February 20th, 2010, 01:16 AM
  3. Interface Implementation
    By Samyx in forum Object Oriented Programming
    Replies: 1
    Last Post: December 2nd, 2009, 02:46 AM
  4. Help wih implementation...
    By Frank_nor in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 24th, 2009, 04:43 PM
  5. B+ Tree implementation
    By programmer in forum Java Theory & Questions
    Replies: 2
    Last Post: November 15th, 2009, 04:47 PM