Tech or Treat! Write an article about your scariest tech disaster to win gadgets!Learn more

x
?
Solved

How to allow duplicate key in the datastructure like Hashtable or map ???

Posted on 2001-08-14
16
Medium Priority
?
939 Views
Last Modified: 2008-02-01
Hello,

 I want to implement Hashtable or map which should allow
duplicate keys. what is the easiest way or is there
any piece already available in Internet.

any url or anything will be helpful.

Advanced Thanx,
Ramesh//
0
Comment
Question by:rameshaa
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 5
  • 3
  • +1
16 Comments
 
LVL 3

Expert Comment

by:black
ID: 6386461
I believe the JGL libraries do that:
http://www.objectspace.com/products/voyager/libraries.asp
you can download free of charge, you just have to register,
there's a datasheet, check it out and see if it has a class that does what you want
according to them they have:
Maps
HashMap 1-to-1 or 1-to-many mappings, stored using hash
OrderedMap 1-to-1 or 1-to-many mappings, stored in order

I believe you are looking for the 1-to-many mappings
0
 
LVL 92

Expert Comment

by:objects
ID: 6386554
Isn't the point of a Map that you can look up an object by key?

If you can have objects with duplicate keys then how will you perform your lookup.
0
 
LVL 3

Expert Comment

by:black
ID: 6386572
I'm assuming he'll get more than one value and he picks one out of it. I had to do something similar when implementing a simple markov chains program. For one word I had to have multiple values against it and then pick one of them.
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 92

Expert Comment

by:objects
ID: 6386590
The simply use a Map of Collections.
0
 
LVL 3

Expert Comment

by:black
ID: 6386596
That's effectively what the JGL package does, you have the normal put/get methods but you also have an extra:
public synchronized Enumeration values(Object key)
The JGL library will handle that for you rather than you having to explicitly have a Collection or maybe another wrapper object around your multiple values.
0
 
LVL 3

Expert Comment

by:dnoelpp
ID: 6387668
I would create a subclass of HashMap and override put accordingly and add two additional methods: int getValueCount() and Iteration getValues().
0
 
LVL 3

Accepted Solution

by:
dnoelpp earned 300 total points
ID: 6387824
I did it...!

Any comments from the other experts here?

The main() function is to do some testing... Output of the testing should be:

----- 8< ----- 8< ----- 8< ----- 8< ----- 8< -----
key: #0, <no values
key: #1, value1,
key: #2, value1, value2,
key: #3, value1, value2, value3,
key: #4, value1, value2, value3, value4,
----- 8< ----- 8< ----- 8< ----- 8< ----- 8< -----

The class MultiMap.

----- 8< ----- 8< ----- 8< ----- 8< ----- 8< -----
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;

public class MultiMap extends HashMap {

    // suppose if someone puts an ArrayList value to a key?
    // so, use a derived ArrayList to store a multi-value instead.
    private class MultiMapList extends ArrayList {
    }

    public Object put(Object key, Object value) {
        Object existingValue = get(key);

        // no value yet: just put the single value
        if (existingValue == null) {
            super.put(key, value);
        }

        // already several values: add the value to the MultiMapList
        else if (existingValue instanceof MultiMapList) {
            ((List)existingValue).add(value);
            return value;
        }

        // already ONE value: create a MultiMapList and add both the
        // existing and the new value to the list
        else {
            MultiMapList list = new MultiMapList();
            list.add(get(key));
            list.add(value);
            super.put(key, list);
        }
        return value;
    }

    public int getValueCount(Object key) {
        Object value = get(key);

        if (value == null) return 0;
        if (value instanceof MultiMapList) return ((List)value).size();
        return 1;
    }

    public Iterator getValueIterator(Object key) {
        int count = getValueCount(key);

        if (count == 0) return new Iterator() {
            public boolean hasNext() { return false; }
            public Object next() { return null; }
            public void remove() { throw new UnsupportedOperationException(); }
        };

        if (count == 1) {
            final Object value = get(key);
            return new Iterator() {
                private boolean done = false;
                public boolean hasNext() { return !done; }
                public Object next() {
                    if (done) return null;
                    done = true;
                    return value;
                }
                public void remove() { throw new UnsupportedOperationException(); }
            };
        }

        return ((List)get(key)).iterator();
    }

    // test the class Multimap. Inserts four string values
    // to the key "key" and print the contents (to test the iterators)
    public static void main(String[] args) {
        MultiMap map = new MultiMap();

        System.out.println("key: #" + map.getValueCount("key") + ", "
            + valuesToString(map.getValueIterator("key")));

        map.put("key", "value1");

        System.out.println("key: #" + map.getValueCount("key") + ", "
            + valuesToString(map.getValueIterator("key")));

        map.put("key", "value2");

        System.out.println("key: #" + map.getValueCount("key") + ", "
            + valuesToString(map.getValueIterator("key")));

        map.put("key", "value3");

        System.out.println("key: #" + map.getValueCount("key") + ", "
            + valuesToString(map.getValueIterator("key")));

        map.put("key", "value4");

        System.out.println("key: #" + map.getValueCount("key") + ", "
            + valuesToString(map.getValueIterator("key")));
    }

    private static String valuesToString(Iterator iterator) {
        if (!iterator.hasNext()) return "<no values";

        StringBuffer sb = new StringBuffer();
        while (iterator.hasNext()) {
            sb.append(iterator.next().toString()).append(", ");
        }

        return sb.toString();
    }
}
----- 8< ----- 8< ----- 8< ----- 8< ----- 8< -----
0
 
LVL 3

Expert Comment

by:dnoelpp
ID: 6387826
One note, however, I didn't implement the remove feature... :-(
0
 
LVL 7

Expert Comment

by:Igor Bazarny
ID: 6390828
Hi,

One more note. You need to take care about entrySet(), values() and size() methods. Otherwise your users will need to know about MultiMapList. Besides, if you implement iterator which shows all values for all keys, you will know how to implement remove(). And something needs to be done to get() method.

And one more note. Map can contain null value for some key, if I'm not mistaken. Use containsKey() to check whether some elements present for key.

Regards,
Igor Bazarny,
Brainbench MVP for Java 1
www.brainbench.com
0
 
LVL 92

Expert Comment

by:objects
ID: 6390956
You'll also need to take care of the contains() and containsValue() methods, and possibly others.

May be better to instead create a wrapper class which implements Map and uses a Hashtable internally in its implementation.

class MultMapList implements Map
{
   private Hashtable Impl = new Hashtable();

   ...
}
0
 
LVL 3

Expert Comment

by:dnoelpp
ID: 6391582
Yes, the MultiMap is not a silver bullet, but hey, I hacked it in half an hour... If ramesh doesn't want to use a library and is ready to live with a limited version or wants to improve it himself... why not?

Thanks for the comments about the deficiencies.
0
 
LVL 7

Expert Comment

by:Igor Bazarny
ID: 6394198
dnoelpp,

> If ramesh doesn't
> want to use a library and is ready to live with a limited version or wants to improve it himself...
> why not?
Sure, but he should know the limitations. You asked for comments and got some. Everyone is now free to improve your solution taking into account other opinions.

Regards,
Igor
0
 
LVL 3

Expert Comment

by:dnoelpp
ID: 6395863
Yes, that's what I like about EE. It's a pity however that's not easy to split the points. I wrote the MultiMap class just out of pure joy on little things to play with... The concept of the MultiMap fascinated me...

Now, for a serious development of a useful library class a lot more work needs to be done, I agree. I suppose that it's difficult to develop a class like MultiMap because such classes are used in situation you've never dreamt of. And then something is broken in subtle ways you've never thought of.

I think, for example, about the first versions of the Thread class. I was impressed how the developer's at Sun failed with the stop() and suspend() methods. They had to deprecate them because of subtle details which make them essentially unusable. (See the API doc about the thread class and go to stop() and suspend(); in the API doc there are further link on why stop() and suspend() are deprecated.)

Any comments, again?
0
 
LVL 3

Expert Comment

by:black
ID: 6395881
I agree writing library classes is a very hard thing to do because you have to take into account so many different ways it could be used. Personally I always prefer to use an existing packages. For this instance I think it's best to use the JGL, because it's been around for years and has been tested and used. As fun as it is to develop these libraries ourselves:) in a real system it's always quicker and safer to use existing components.
0
 
LVL 3

Expert Comment

by:dnoelpp
ID: 6395912
You agree, it was fun, wasn't it? :-)

Let's have fun, too, not only chase them stupid points! :-)
0
 
LVL 3

Expert Comment

by:black
ID: 6396301
Couldn't agree more! :)
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
Suggested Courses

647 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question