乐趣区

Android中的容器

List
java.util 包提供了两种
ArrayList
LinkedList
ArrayList 比 LinkedList 常用很多,原因是:ArrayList 查找更容易
ArrayList
ArrayList 封装了一个数组 Object[]

数组的初始化
ArrayList array = new ArrayList();
封装一个空数组, {}
ArrayList array = new ArrayList(10);
封装一个大小为 10 的数组 new Object[10];

数组如何实现扩容
ArrayList.add/addAll 都需要先进行扩容检查,类似,
对象调用方法,要进行对象判空,
UI 操作之前要进行,线程检查

扩容检查: size+ 增加的大小 与 数组.length 比较计算数组扩容的数组长度:

  首先,扩容至原数组大小的一倍,size+ 增加的大 小与其比较:如果大于,扩容至原数组大小的一倍       如果小于,扩容至 size+ 增加的大小;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity – minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity – MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
扩容使用的是: Array.copyof(array, newLen)

removeAll 如何实现
与 remove() 不同,remove 使用 System.copy 完成数组的 部分移动 而 removeAll, 使用的算法:
ArrayList array1 = new ArrayList();
array1.addAll({0,3,5,7,3,6});
int[] array2 = {3,5,4};
array1.removeAll(array2);
首先,遍历 array1 中每个元素,若元素 不在 array2 内,将计数位置的值设置为元素的值并将计 数 +1; 遍历完成后,计数为数组剩余元素的个 数,将计数之后的元素清空. 算法详细:
&#8194;&#8194;0,3,5,7,3,6 ;<br>
&#8194;&#8194; 遍历之后,计数为 2,数组为 0,7,6,7,3,6;<br>
&#8194;&#8194; 清空之后,0,7,6,null,null,null;

trimToSize() 数组扩容后即使删除元素,数组的 length 也不会该改变,意味着即使删除了某些元素数组占用的内存大小不会改变; 数组只会不断的增大, 且出现大量 null 的元素.trimToSize() 方法用于改变数组的 length, 将为 null 的元素释放掉,等待 GC 这也是防止内存浪费的一种方式,当 ArrayList 经历了多次删除操作之后,使用 trimToSize(), 避免内存浪费.trimToSize() 使用 Array.copyof() 来改变数组的 length

总结 ArrayList 本质上维护了一个数组,也就意味者它具有数组的优缺点:增删难,查找易

LinkedList

Node 的数据结构
Node<E> {
E element;
Node<E> prev;
Node<E> next;
}

基本结构
Node<E> first, last
Linked 是双向链表,first,last 指向表头,表尾

总结 LinkedList 是一个 Deque, 双向链表,增删易,查找难,造成在编码中很少使用

Map
java.util 包提供了两种 Map:1.HashMap2.TreeMap
Android 为了性能优化,提供了 HashMap 的替代品:1.ArrayMap2.SparseMap 它俩可以在数据量都在千级以内的情况下,如果 key 的类型为 int,使用 SparseMap,   如果 key 的类型为其它类型,使用 ArrayMap
HashMap 相比 TreeMap 更常用
HashMap

数据结构 Node 的数据结构:
Node<K,V> {
int hash;
K key;
V value;
Node<K,V> next;
}
基本数据结构:
Node<K,V>[] table;
float loadFoctor;// 默认值 0.75f
int threshold;
可以看出 HashMap 的数据结构是数组 + 链表

扩容

什么时候扩容当调用 put/putAll 时, 实际上都是调用 putVal 方法   先创建 Node, 再查看新的 Node 放入数组,还是链表;   当 ++size>threshold,则需要扩容

table 如何扩容它的扩容包含两个步骤:
1. 确定扩容的大小;
2. 如何移动元素,包含数组中的元素与链表中的元素;<br>

  确定扩容的大小:    threshold 默认值 = 16*0.75f=12     每次扩容,先创建一个 threadhold 大小的数组,赋给 tble, 也就是扩容至 threadhold     再,threadhold = threadhold <<1,扩大一倍
  如何移动元素,包含数组中的元素与链表中的元素:    1. 如果元素只在数组里,而没有链表:      新的位置是 e.hash&(newCap-1)    2. 元素在链表上:      根据 (e.hash & oldCap) == 0 决定是在原位置还是在原位置 +oldCap 上      链表可能会分为两部分
TreeMap

数据结构 TreeMapEntry 的数据结构
TreeMapEntry<K, V> {
K key;
V value;
TreeMapEntry<K, V> left;
TreeMapEntry<K, V> right;
TreeMapEntry<K, V> parent;
}
TreeMap 的数据结构:
TreeMapEntry<K, V> root;
Comparator<? super K> comparator;

TreeMap 实际上是红黑二叉树

SparseArray

数据结构
int[] mKeys;
Object[] mValues;

总结 官方推荐去使用 SparseArray<E> 去替换 HashMap<Integer,E>, 牺牲了部分效率换来内存

ArrayMap
LinkedHashMap

可以看作 HashMap+LinkedList,用于保证插入顺序
一般用于作为缓存

Java 中的线程安全的容器
同步容器
Vector HashTable
并发容器
用于读写分离,实现读并发,写同步并发的不同策略:  1.Blocking 容器  2.CopyOnWrite 容器  3.Concurrent 容器
Blocking 容器
并发策略:

  用于解决限制容量的容器的存取问题  类似生产者 - 消费者  容器为空时,阻塞取线程  容器满时,阻塞存线程
CopyOnWrite 容器
并发策略:
  写时赋值,即添加元素时,先复制整个容器,添加到复制的容器中,  再将容器引用指向复制的容器,达到读的最大并发;   适用于读多写少的情况;
Concurrent 容器
并发策略:
  使用分段锁,首先将容器分成多段,每段使用不同的锁,对不同段达到读写并发, 相同段读并发,写同步

退出移动版