• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 941
  • Last Modified:

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

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
rameshaa
Asked:
rameshaa
  • 6
  • 5
  • 3
  • +1
1 Solution
 
blackCommented:
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
 
objectsCommented:
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
 
blackCommented:
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
objectsCommented:
The simply use a Map of Collections.
0
 
blackCommented:
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
 
dnoelppCommented:
I would create a subclass of HashMap and override put accordingly and add two additional methods: int getValueCount() and Iteration getValues().
0
 
dnoelppCommented:
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
 
dnoelppCommented:
One note, however, I didn't implement the remove feature... :-(
0
 
Igor BazarnyCommented:
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
 
objectsCommented:
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
 
dnoelppCommented:
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
 
Igor BazarnyCommented:
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
 
dnoelppCommented:
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
 
blackCommented:
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
 
dnoelppCommented:
You agree, it was fun, wasn't it? :-)

Let's have fun, too, not only chase them stupid points! :-)
0
 
blackCommented:
Couldn't agree more! :)
0

Featured Post

[Webinar] Cloud and Mobile-First Strategy

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

  • 6
  • 5
  • 3
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now