4

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

We are doing it in following way:

  1. Create an array of Linked Lists of the size Integer_MAX (custom linked list).
  2. 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:

  1. Why we are trying to do this can be found here.
  2. Current code (by Louis Wasserman) can be found here.
Community
  • 1
  • 1
Arpssss
  • 3,850
  • 6
  • 36
  • 80

1 Answers1

1

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

gkuzmin
  • 2,414
  • 17
  • 24
  • Try to use ArrayList. It should work with performance close enought to array. – gkuzmin Aug 02 '12 at 12:36
  • But if I define arraylist(Int-Max) it will affect same like array. Sorry, even more as object. – Arpssss Aug 02 '12 at 12:37
  • 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? – gkuzmin Aug 02 '12 at 12:43
  • yah. But, without reducing the size from Int-Max (means O(1) complexity) because of http://stackoverflow.com/questions/11765517/java-custom-hash-map-table-some-points. – Arpssss Aug 02 '12 at 12:46
  • 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. – gkuzmin Aug 02 '12 at 12:56
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/14801/discussion-between-gkuzmin-and-arpssss) – gkuzmin Aug 02 '12 at 13:14