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).

Arpssss
  • 3,850
  • 6
  • 36
  • 80
  • I think OP wants multiple instances of the key in the map – srini.venigalla Jul 31 '12 at 20:39
  • @Recursed, I want key with multiple values. – Arpssss Jul 31 '12 at 20:41
  • @Arpssss Which is what you would have if your key mapped to an ArrayList, or an array – Rob Wagner Jul 31 '12 at 20:42
  • @Recursed, I will just take the values for further processing. – Arpssss Jul 31 '12 at 20:49
  • Take a look at http://stackoverflow.com/questions/1010879/best-way-to-create-a-hashmap-of-arraylist/1011072#1011072 – Steve Kuo Jul 31 '12 at 21:16
  • 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. – Louis Wasserman Jul 31 '12 at 21:25
  • @LouisWasserman, If I built primitive linked list (say http://stackoverflow.com/questions/10042/how-do-i-implement-a-linked-list-in-java) and create an array of that. Will it takes that much ? Because I have not to store keys just only values. – Arpssss Jul 31 '12 at 21:30
  • 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, `ArrayList`s, or magic unicorn lists. – Louis Wasserman Jul 31 '12 at 21:39
  • @LouisWasserman, However, I can provide 16 of memory for my tasks. And I am targeting to store 300 million of values (as I have not to store keys). – Arpssss Jul 31 '12 at 21:43
  • Assuming you mean 16GB...okay, yeah, a tiny linked list node class that contains only an `int` field and a `next` pointer might actually work out. That comes out to 300 million * 16 bytes, plus 2^31 times 4 bytes, equals 12.5GB. ...Was there a question in there? – Louis Wasserman Jul 31 '12 at 21:49
  • @LouisWasserman, what you have calculated I just want same which is not possible in Guava. Now, I am trying to build my custom linked list. To check what happens. – Arpssss Jul 31 '12 at 22:02
  • ...Do you need help, then? You just need your linked list class to have a single `int` value and the `next` pointer. (Also, I hope you don't have too many values per key.) – Louis Wasserman Jul 31 '12 at 22:17
  • @LouisWasserman, And soon I get stuck on this (http://stackoverflow.com/questions/11750583/java-custom-hash-table). – Arpssss Jul 31 '12 at 23:37

5 Answers5

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.

Mike Deck
  • 18,045
  • 16
  • 68
  • 92
  • I want to make it for primitives. Thus it can take less space. – Arpssss Jul 31 '12 at 20:42
  • @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). – Mike Deck Jul 31 '12 at 21:18
  • 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. – Louis Wasserman Jul 31 '12 at 21:23
  • I have used Guava/Trove to do that but I found they take really huge space (http://stackoverflow.com/questions/10064422/java-on-memory-efficient-key-value-store). 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. – Arpssss Jul 31 '12 at 21:27
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/

Andrey Borisov
  • 3,160
  • 18
  • 18
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.

Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268
  • There is no primitive data structure thus I can create array of data structure which solves above issue ? – Arpssss Jul 31 '12 at 20:48
  • 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. – Code-Apprentice Jul 31 '12 at 20:56
  • It is possible to create custom Linked List for primitive types ? Or is there any library solution ? – Arpssss Jul 31 '12 at 21:00
  • 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. – Code-Apprentice Jul 31 '12 at 21:02
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

srini.venigalla
  • 5,137
  • 1
  • 18
  • 29
  • I want to make it for primitives. Thus it can take less space. – Arpssss Jul 31 '12 at 20:39
  • primitives can be autoboxed like Integer, Long, Boolean etc. right, what am I missing? – srini.venigalla Jul 31 '12 at 20:58
  • 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 Jul 31 '12 at 21:02
  • @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? – Steve Kuo Jul 31 '12 at 21:18
  • 250 millions key-value pairs. – Arpssss Jul 31 '12 at 21:21
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.

Grzegorz Rożniecki
  • 27,415
  • 11
  • 90
  • 112