Solved

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

Posted on 2001-08-14
16
906 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
  • 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
 
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 100 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
Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

 
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.

708 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now