ArrayList 内部使用的动态数组来存储元素，LinkedList 内部使用的双向链表来存储元素，这也是 ArrayList 和 LinkedList 最本质的区别。
ArrayList特点：查询快、修改快、增加慢、删除慢。
LinkedList特点：插入和删除节点快，查找耗时。
HashMap是整合了ArrayList和linkedlist的优点，查询和插入都是比较快的。HashMap由数组（键值对entry组成的数组主干）+ 链表（元素太多时为解决哈希冲突数组的一个元素上多个entry组成的链表）+ 红黑树（当链表的元素个数达到8链表存储改为红黑树存储）进行数据的存储。
HashMap采用table数组存储Key-Value的，每一个键值对组成了一个Node节点（JDK1.7为Entry实体，因为jdk1.8加入了红黑树，所以改为Node）。Node节点实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Node节点，以此来解决Hash冲突的问题。
map.put(k,v)实现原理：
1.首先将k,v封装到Node对象当中（节点）。
2.然后它的底层会调用K的hashCode()方法得出hash值。
3.通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
map.get(k)实现原理：
1.先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
2.通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。
HashMap 的实例有两个参数影响其性能：初始容量和加载因子(默认值为0.75)。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
HashMap的缺点：内存浪费。
SparseArray：SparseArray相比于HashMap，采用的是时间换取空间的方式来提高手机App的运行效率。
1.SparseArray采用了int[] mKeys 和 Object[] mValues两个数组来分别存储key和value。
2.对于某个key值，先查找其在mKeys中的索引i，直接mValues[i]获取key对应的value，也就是说key与其对应的value存储下标是一样的。
3.SparseArray对mKeys数组做了正序排列，因此，在进行遍历查找key时，使用的是二分查找法，一切为了效率。
4.SparseArray使用int类型，不同与HashMap使用Integer，省去了自动装箱过程，消耗更少内存。
总的来说，SparseArray内存性能优于HashMap，一般适用于key为整型值，数据量较少的应用场景。也是考虑内存优化时替代HashMap的首选。
ArrayMap：是谷歌推出的在安卓等设备上用于替代HashMap的数据结构，和HashMap相比，具有更高的内存使用率，因此适合在Android等内存较为紧张的移动设备。
特点：
1.实现了Map接口，并使用int[]数来存储key的hash值，数组的索引用作index，而使用Object[]数组来存储key<->value ，这还是比较新颖的 。
2.使用二分查找查找hash值在key数组中的位置，然后根据这个位置得到value数组中对应位置的元素。
3.和SparseArray类似，当数据有几百条时，性能会比HashMap低50%，因此ArrayMap适用于数据量很小的场景。
网友评论