I am wondering for those dictionary-like data structure (Hashtable, HashMap, LinkedHashMap, TreeMap, ConncurrentHashMap, SortedMap and so on) need to do rehashing operation when its size reaches the threshold ? Since it's really expensive whenever we resize our table, so I am wondering is there anything else that doesn't require rehashing when resizing the table or any way to improve the performance on such operation ?
SortedMap (TreeMap) doesn't need to rehash, it's designed as red-black tree, and thus is self-balanced
closed-hash related structures might need to be rehashed in order to get performance boost, however it's kinda trade-off.
so it can be implemented without rehashing, and that is what load factor parameter introduced for.
To improve the performance estimate approximate initial capacity based on the application and choose the right load factor when allocating memory for the datastructure.
No escape from re-hashing unless you implement your own HashMap.
A few other facts: Rehashing happens only on HashRelated data structures i.e HashMap, HashTable so on. So all non hash datastructures like treemap, sortedmap(is an interface so we can take this out of picture) are not re-hashed on reaching a limit.
Re-sizing always happens on ArrayList when it reaches the threshold. So use Linked list if you have a lot of insertions and deletions in between the datastructure.