2

I want to create my custom Hash Table for key with multiple values. For that, what I want to do is following:

1) Create an array of Linked Lists/ Array-list of the size Integer_MAX.

2) Insert values (int's) to the Linked Lists/ Array-list whose number is key number.

Now, I am facing two issues:

1) How to define array of Linked Lists/ Array-list's.

2) Is there any way to make them primitive ?

Any help or any idea to make it better will be helpful to me.

Thanks.

Edit: I know that Hash Table concept has nothing to do with key with multiple values. But, I want to make it like that.

I want to make a custom hash map and for primitives (not for objects as it takes really huge space like guava).

Improve this question
13
  • I think OP wants multiple instances of the key in the map Commented Jul 31, 2012 at 20:39
  • @Recursed, I want key with multiple values. Commented Jul 31, 2012 at 20:41
  • @Arpssss Which is what you would have if your key mapped to an ArrayList, or an array Commented Jul 31, 2012 at 20:42
  • 1
    Are you sure you want to create an array of size Integer.MAX_VALUE? That will take, at a minimum, 8 gigabytes, without even putting anything in it. Commented Jul 31, 2012 at 21:25
  • 1
    An array of Integer.MAX_VALUE nulls will take 8GB. An array of anything other than nulls will cost more, whether you're using linked lists, ArrayLists, or magic unicorn lists. Commented Jul 31, 2012 at 21:39

5 Answers 5

Reset to default
3

I would highly recommend using a Multimap from the guava project. You can use an ArrayListMultiMap and get exactly the behavior you're looking for.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I want to make it for primitives. Thus it can take less space.
@Arpssss The guava team has spent quite a lot of time making the libraries as efficient as possible. Honestly, unless you have a lot of experience in micro-optimization and a deep understanding of the internals of the JVMs you're targeting it's unlikely you'll be able to write a better implementation than what's available from guava (or Commons Collections).
I mean, using e.g. Trove's specialized primitives collections with Multimaps.new{List,Set}Multimap would do a better job than the basic implementation, but doing much better than those would be extraordinarily difficult.
I have used Guava/Trove to do that but I found they take really huge space (stackoverflow.com/questions/10064422/…). I really care about space. I now I cant make performance better than those but with little performance overhead I want to make it space efficient.
2

1) You define an array of LinkedLists just like any array:

LinkedList[] l = new LinkedList[10];

Although, you should probably do an array of Lists instead:

List[] l = new List[10];

2) Arrays are not primitives. Neither are LinkedLists. Also, LinkedLists can only hold references, not primitive types. If you must store primitives in your custom hashmap class, you will need to use arrays only, not LinkedList or ArrayList.

Improve this answer

4 Comments

There is no primitive data structure thus I can create array of data structure which solves above issue ?
All Collection classes from the Java API are designed for object references, not primitive types. This is why there are wrapper classes such as Integer, Double, etc. In order to do what you are asking, you will need to use only arrays.
It is possible to create custom Linked List for primitive types ? Or is there any library solution ?
Sure, you can create your own LinkedList that holds primitive types. You would have to create one for each type (e.g. IntLinkedList, CharLinkedList, DoubleLinkedList, etc.) because generics do not support primitives. There might be a library available for this, but I am not aware of any.
2

use guava multimap http://tomjefferys.blogspot.com/2011/09/multimaps-google-guava.html and http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Multimaps.html

for primitives use this http://labs.carrotsearch.com/hppc.html or http://fastutil.di.unimi.it/

Improve this answer

1 Comment

I want to make it for primitives. Thus it can take less space.
1

If what you need is a multi-value map, use the Collections

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/MultiValueMap.html

Improve this answer

5 Comments

I want to make it for primitives. Thus it can take less space.
primitives can be autoboxed like Integer, Long, Boolean etc. right, what am I missing?
Actually, what solution you have provided makes Objests as key and values. Now, I want to make it for int (not INTEGER) because object will take more space than int.
@Arpssss collections only accepts objects. Thus for primitives, you need to convert them (boxing) to their object equivalent (ie, int becomes Integer). Don't worry about storage. How many values do you need to store?
250 millions key-value pairs.
1

Did you really check Guava + Trove Multimap implementation? Like this one:

final int listCapacity = 10; // Intege.MAX_VALUE isn't an option
final ListMultimap<Integer, Integer> multimap =
    Multimaps.newListMultimap(
        TDecorators.wrap(
            new TIntObjectHashMap<Collection<Integer>>()), //Map<int, Collection>
        new Supplier<List<Integer>>() {
          @Override
          public List<Integer> get() {
            return TDecorators.wrap(new TIntArrayList(listCapacity)); //List<int>
          }
        });

You'll get fully-blown ListMultimap<Integer, Integer>, so you can do:

multimap.putAll(1, Ints.asList(1, 11, 111, 1, 1111));
multimap.putAll(2, Ints.asList(2, 22, 222, 2, 2222));
multimap.put(3, 333);

System.out.println("multimap: " + multimap);
System.out.println("get(2): " + multimap.get(2));
System.out.println("get(3): " + multimap.get(3));
System.out.println("get(4): " + multimap.get(4));

which outputs:

multimap: {3=[333], 2=[2, 22, 222, 2, 2222], 1=[1, 11, 111, 1, 1111]}
get(2): [2, 22, 222, 2, 2222]
get(3): [333]
get(4): []

and each list is instance of TIntArrayList, each map is TIntObjectHashMap, which are very memory efficient and optimized (you should experiment with Map's parameters btw). I don't think you can build more optimized implementation that'll be usable at the same time.

Only downside is autoboxing cost, but it doesn't consume that much memory, more likely time.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.