3

This QA How does Java implement hash tables? describes that Hashtable is implemented via static array in Java (the underlying static array will be refined according to the total number of items).

Why doesn't Java implement Hashtable via dynamic array, such as ArrayList?

What are the tradeoffs?

Community
  • 1
  • 1
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271

3 Answers3

4

When a hashtable is resized, all of the entries need to be re-positioned.
Using an ArrayList would therefore be slower, since the ArrayList would copy over the now-useless old values before the HashTable re-calculates them all.

SLaks
  • 868,454
  • 176
  • 1,908
  • 1,964
  • So do you mean this: suppose a Hashtable has {1, "a"} (1 is the slot index of the key, not the key, for simplicity). Now the Hashtable needs to expend, so it needs to rehash {1, "a"} to {10, "a"}, so which means the pair need to be copied from index 1 to index 10. ArrayList is not that efficient at copying, at least less efficient than static raw array, so it makes no sense to use ArrayList. Do you mean this? – Jackson Tale Feb 20 '12 at 16:05
  • No. My point is that resizing an ArrayList copies the original data to the new backing array. HashTable doesn't want that. – SLaks Feb 20 '12 at 16:14
  • but ArrayList is a dynamic array, why it needs to be resized? – Jackson Tale Feb 20 '12 at 16:23
  • 1
    ArrayList is implemented using a simple array with a default length (10, or something like that). When you add enough items to the ArrayList, it creates a new array, twice the size of the old one, and copies the old into the new. So it is dynamic, but the memory allocation at any given time is fixed. – Matthew Flynn Feb 20 '12 at 16:41
  • @JacksonTale: There is no such thing as a "dynamic array". See Matthew's explanation. – SLaks Feb 20 '12 at 17:01
  • @MatthewFlynn, roger that, now I understand. – Jackson Tale Feb 20 '12 at 17:18
1

Resizing the underlying array requires rehashing all items in the hashtable, which is a very costly operation and invalidates the position of any item currently in the array - that's why you usually double the array size everytime the number of items exceeds a certain threshold (the load factor). Since resizing is managed internally and existing items have to be moved to a new position anyway a "resizable array" like ArrayList doesn't make sense.

BrokenGlass
  • 158,293
  • 28
  • 286
  • 335
0

Implementation classes are quite opaque. Since an ArrayList is rather uneffcient compared to a real static array there's no need to use it.

You won't have any benefit, at least in this way you save up having a wrapper to the static array that contains the hash map.

Resizing an ArrayList would be like resizing an HashMap, since they both work with a static underlying array but you'll need to rehash all the elements of the map in any case so there's really no need to use it.

Jack
  • 131,802
  • 30
  • 241
  • 343