?
Solved

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

Posted on 2001-08-14
16
Medium Priority
?
933 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
Get real performance insights from real users

Key features:
- Total Pages Views and Load times
- Top Pages Viewed and Load Times
- Real Time Site Page Build Performance
- Users’ Browser and Platform Performance
- Geographic User Breakdown
- And more

 
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

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.

Question has a verified solution.

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

Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
Suggested Courses
Course of the Month10 days, 23 hours left to enroll

770 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