ArrayList与ArrayMap的差异、非线程性能及与HashMap对比问询

Hey there! Let's break down your questions one by one—they cover some key distinctions between these common collection classes, so it's worth getting clear on each point.

First off, these are fundamentally different types of collections, so their purposes don't overlap much:

• Collection Type: ArrayList is a List implementation—it stores an ordered list of single elements, and you access items by their index. ArrayMap is a Map implementation—it holds key-value pairs, where you look up values using their associated keys.
• Underlying Storage: ArrayList uses a single array to store all its elements. ArrayMap uses two separate arrays: one for hash values of keys, and another that alternates between keys and their corresponding values (e.g., index 0 = key1, index 1 = value1, index 2 = key2, etc.). This dual-array setup helps ArrayMap save memory compared to other Map implementations.
• Key Operations: For ArrayList, adding, removing, or accessing elements is all index-based (O(1) for direct index access). For ArrayMap, when you look up a value, it first calculates the key's hash, performs a binary search on the hash array to find the position, then pulls the value from the element array—so lookups are O(log n).

Since ArrayList and ArrayMap serve different purposes, a direct "which is better" comparison doesn't make sense across all cases:

• If you need to store an ordered list of elements and access them by index, ArrayList is far more efficient—its index-based operations are blazingly fast (O(1)) and have minimal overhead.
• If you're working with key-value pairs (the use case for ArrayMap), it depends on data size. For small datasets (dozens of entries or fewer), ArrayMap is more memory-efficient and performs well enough. For larger datasets, HashMap (which we'll talk about next) is faster for lookups, but ArrayMap still has the edge on memory.

No, they are not identical—their underlying implementations and tradeoffs are very different. Here's how they stack up:

• Memory Overhead: ArrayMap is way more memory-efficient, especially for small datasets. HashMap wraps each key-value pair in a separate Entry object, which adds significant object overhead. ArrayMap uses two object arrays (no extra wrapper objects) to store everything, so it avoids that overhead entirely.
• Lookup Speed: HashMap uses a hash table with linked lists/red-black trees for collision resolution, so average-case lookups are O(1). ArrayMap relies on binary search of its hash array, so lookups are O(log n). For large datasets (hundreds of entries or more), HashMap will be noticeably faster for lookups and inserts.
• Resizing Behavior: When they run out of space, HashMap doubles its capacity (e.g., from 16 to 32, 32 to 64) and rehashes all entries, which can be a costly operation. ArrayMap uses a more gradual resizing strategy—its initial capacity is 0, then it expands to 4, then 8, then 16, etc.—and resizing is generally less expensive because it doesn't have to create new Entry objects.
• Use Case Fit: ArrayMap shines in memory-sensitive apps with small to medium key-value datasets. HashMap is the go-to choice when you need fast lookups and inserts for larger datasets, or when you need the full feature set of a standard Map (though ArrayMap covers most basic Map use cases).

内容的提问来源于stack exchange，提问作者ucMax