Explain how ArrayMap works

ArrayMap uses 2 arrays. The instance variables used internally are Object[ ] mArray to store the objects and the int[] mHashes to store hashCodes. When a key/value is inserted :

• Key/Value is autoboxed.
• The key object is inserted in the mArray where on the index in which it needs to pushed is searched using the binary search.
• A value object is also inserted in the position next to key’s position in mArray[ ].
• The hashCode of the key is calculated and placed in mHashes[ ] at the next available position.

For searching a key :

• Key’s hashCode is calculated
• Binary search is done for this hashCode in the mHashes array. This implies time complexity increases to O(logN).
• Once we get the index of hash, we know that key is at 2*index position in mArray and value is at 2*index+1 position.
• Here the time complexity increases from O(1) to O(logN), but it is memory efficient. Whenever we play on a dataset of around 100,
• there will no problem of time complexity, it will be non-noticeable. As we have the advantage of memory efficient application.