I fear downvotes. Anyways, just like an ArrayList would have a contiguous memory allocation, a LinkedList would have a random memory allocation, how does HashMap occupy memory? Does it also take random chunks in the memory? Can I be briefed with a memory diagram of how map's buckets and the LinkedLists inside are located in the memory?
I hope this is not a bs question. Did not find much of information regarding Map's memory allocation diagram.
EDIT: The question I put has nothing to do with debugging/profiling. It's just about how a HashMap fits into the memory. I was unclear about it.
HashMaps use an inner class to store data: the Entry<K, V>. This entry is a simple key-value pair with two extra data: a reference to another Entry so that a HashMap can store entries like singly linked lists. a hash value that represents the hash value of the key.
The Key in Map is stored under given position of array (memory). The position is set by RunTime (not compiler), using algorithm that use transformed hashCode of object and array length. Time needed to retrieve element is O(1), that do not require any iteration.
As Figure 7 shows, when a HashMap is created, the result is a HashMap object and an array of HashMap$Entry objects at its default capacity of 16 entries. This gives a HashMap a size of 128 bytes when it is completely empty.
It's a combination of both.
There is an underlying, contiguous array that backs HashMap
. The elements of this array are actually singly linked lists. Each time you add a key-value pair to the map, the key is hashed and a linked list entry is added to the corresponding slot of the backing array (i.e. the slot corresponding to the key's hash value).
For instance, a map that maps k
to v
might look like this:
0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | | | | | | | | | +-X-+-X-+-↓-+-X-+-X-+-X-+-X-+-X-+ ↓ ↓ +---+ | k | | - | | v | +---+
There is a long "table" that backs the map, and an entry that supports the specific k
-to-v
pairing.
It would probably be best for you to take a look at the HashMap
source for yourself.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With