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适用于数据量很小的场景。