Java Array of Linked Lists

Question

I am trying to code a custom hashtable which can allows multiple values.

We are doing it in following way:

Create an array of Linked Lists of the size Integer_MAX (custom linked list).
Insert values (int's) to the Linked Lists whose number is key number.

Means structure like:

value1 -> value6
NULL
Null
value3 -> value7
Null
...
...(until Int-Max)

Now, as we will store nearly 500 millions of key value pairs, at-lest 1600 millions link lists are going to be wasted.

Now, as per suggestion fro my working place, I am trying to build hashtable with structure like:

1 -> value1 -> value6
0
0
1 -> value3 -> value7  // here 0/1 bit defines linked lists exits or not
0
...
...(until Int-Max)

Can anybody help me is this possible to build such kind of structure ?

Edit:

Why we are trying to do this can be found here.
Current code (by Louis Wasserman) can be found here.

gkuzmin · Accepted Answer · 2012-08-02 12:34:34Z

1

You can not create an array of generic type because array is reified type. Generics are implemented by erasure.

answered Aug 2, 2012 at 12:34

gkuzmin

2,49418 silver badges24 bronze badges

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

6 Comments

gkuzmin Over a year ago

Try to use ArrayList. It should work with performance close enought to array.

Arpssss Over a year ago

But if I define arraylist(Int-Max) it will affect same like array. Sorry, even more as object.

gkuzmin Over a year ago

It is not very clear to me what exactly do you want to do. Do you want to reduce number of null links in current implementation? Do you want to store link only by some condition?

Arpssss Over a year ago

yah. But, without reducing the size from Int-Max (means O(1) complexity) because of stackoverflow.com/questions/11765517/….

gkuzmin Over a year ago

I can propose to use abstract node class CustomHashMap.AbstractNode with 2 subclasses - CustomHashMap.EmptyNode and CustomHashMap.NotEmptyNode. CustomHashMap.EmptyNode should be singleton with no data inside. So, you will have additional instance check, but reduce memory usage. Correct me if I am wrong or did not understand your problem again, please.

|

Collectives™ on Stack Overflow

Java Array of Linked Lists

1 Answer 1

6 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Linked

Related