1

So I am implementing my own hashtable in java, since the built in hashtable has ridiculous memory overhead per entry. I'm making an open-addressed table with a variant of quadratic hashing, which is backed internally by two arrays, one for keys and one for values. I don't have the ability to resize though. The obvious way to do it is to create larger arrays and then hash all of the (key, value) pairs into the new arrays from the old ones. This falls apart though when my old arrays take up over 50% of my current memory, since I can't fit both the old and new arrays in memory at the same time. Is there any way to resize my hashtable in this situation

Edit: the info I got for current hashtable memory overheads is from here How much memory does a Hashtable use?

Also, for my current application, my values are ints, so rather than store references to Integers, I have an array of ints as my values.

Community
  • 1
  • 1
user548928
  • 46
  • 4
  • 3
    Care to back up the assertion that the builtin HashMap has "ridiculous memory overhead per entry"? On what do you base that assertion? – Jim Garrison Dec 24 '10 at 18:22
  • He mentions open-addressed tables, so I assume he's referring to the overhead of HashMap$Entry. – Brett Kail Dec 24 '10 at 18:25
  • 1
    If you check the HashMap.Entry source code, it has 3 references (to the key, the value and the next entry) and an `int` for the key hash. You might be able to get rid of the reference to the next entry, but I'd day that's it. Unless you dont mind calling key.hashCode() all the time - then you can also get rid of the `int` too. That's what? 12 bytes per entry on a 64-bit JVM? – thkala Dec 24 '10 at 18:37
  • 2
    I guess the better question is why is there a need to minimize memory. Is this going to run on a smartphone or embedded device? If so then it's a valid concern; otherwise it's premature optimization. – Jim Garrison Dec 24 '10 at 20:02
  • 1
    @tkhala: Each HashMap.Entry needs 24 bytes of memory, using the HotSpot VM with small pointers. 8 bytes for the object header, and 16 bytes for the four fields: key, value, hash, next. Omitting the HashMap.Entry in the data structure therefore saves 28 bytes per entry. The last 4 bytes are for the extra pointer to the entry. – Roland Illig Dec 25 '10 at 09:11

3 Answers3

1

The simple answer is "no, there is no way to extend the length of an existing array". That said, you could add extra complexity to your hashtable and use arrays-of-arrays (or specialize and hard-code support for just two arrays).

Brett Kail
  • 33,593
  • 2
  • 85
  • 90
1

You could partition your hash table. e.g. you could have 2-16 partitions based on 1-4 bits in the hashCode. This would allow you to resize a portion of the hash table at a time.

If you have a single hash table which is a large percentage of your memory size, you have a serious design issue IMHO. Are you using a mobile device? What is your memory restriction? Have you looked using Trove4j which doesn't use entry objects either.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
0

Maybe a solution for the problem is: ->Creating a list to store the content of the matrix (setting a list for each row and then free the memory of the array in question if possible, one by one); -> Create the new matrix; ->Fill the matrix with the values stored on the list (removing 1 element from the list right after copying the info from it.

This can be easier if the matrix elements are pointers to the elements themselves. This is a very theorical approach of the problem, but I hope it helps

John
  • 311
  • 4
  • 17