资讯专栏INFORMATION COLUMN

Android中的容器

roland_reed / 3139人阅读

摘要:包提供了两种比常用很多,原因是查找更容易封装了一个数组数组的初始化封装一个空数组封装一个大小为的数组数组如何实现扩容都需要先进行扩容检查,类似,对象调用方法,要进行对象判空,操作之前要进行,线程检查扩容检查增加的大小与数组比较计算数组扩容的

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;

遍历完成后,计数为数组剩余元素的个 数,将计数之后的元素清空.

算法详细:

     0,3,5,7,3,6 ;
  遍历之后,计数为2,数组为0,7,6,7,3,6;
  清空之后,0,7,6,null,null,null;

trimToSize()

数组扩容后即使删除元素,数组的length也不会该改变,

意味着即使删除了某些元素数组占用的内存大小不会改变;

数组只会不断的增大,且出现大量null的元素.

trimToSize()方法用于改变数组的length,将为null的元素释放掉,等待GC

这也是防止内存浪费的一种方式,当ArrayList经历了多次删除操作之后,使用trimToSize(),避免内存浪费.

trimToSize()使用Array.copyof()来改变数组的length

总结

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

LinkedList

Node的数据结构

Node {
    E element;
    Node prev;
    Node next;
}

基本结构

    Node first, last

Linked是双向链表,first,last指向表头,表尾

总结

LinkedList是一个Deque,双向链表,

增删易,查找难,造成在编码中很少使用

Map

java.util包提供了两种Map:

1.HashMap

2.TreeMap

Android为了性能优化,提供了HashMap的替代品:

1.ArrayMap

2.SparseMap

它俩可以在数据量都在千级以内的情况下,

  如果key的类型为int,使用SparseMap,

  如果key的类型为其它类型,使用ArrayMap

HashMap相比TreeMap更常用

HashMap

数据结构

Node的数据结构:

Node {
    int hash;
    K key;
    V value;
    Node next;
}

基本数据结构:

Node[] table;
float loadFoctor;//默认值0.75f
int threshold;

可以看出HashMap的数据结构是数组+链表

扩容

什么时候扩容

当调用put/putAll时,实际上都是调用putVal方法

  先创建Node,再查看新的Node放入数组,还是链表;

  当++size>threshold,则需要扩容

table如何扩容

它的扩容包含两个步骤:

1. 确定扩容的大小;
2. 如何移动元素,包含数组中的元素与链表中的元素;

  确定扩容的大小:

    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 key;
    V value;
    TreeMapEntry left;
    TreeMapEntry right;
    TreeMapEntry parent;
}

TreeMap的数据结构:

TreeMapEntry root;
Comparator comparator;

TreeMap实际上是红黑二叉树

SparseArray

数据结构

int[] mKeys;
Object[] mValues;

总结

官方推荐去使用SparseArray去替换HashMap,
牺牲了部分效率换来内存

ArrayMap LinkedHashMap

可以看作HashMap+LinkedList,用于保证插入顺序

一般用于作为缓存

Java中的线程安全的容器 同步容器

Vector

HashTable

并发容器

用于读写分离,实现读并发,写同步

并发的不同策略:

  1.Blocking容器

  2.CopyOnWrite容器

  3.Concurrent容器

Blocking容器

并发策略:

  用于解决限制容量的容器的存取问题

  类似生产者-消费者

  容器为空时,阻塞取线程

  容器满时,阻塞存线程

CopyOnWrite容器

并发策略:

  写时赋值,即添加元素时,先复制整个容器,添加到复制的容器中,
  再将容器引用指向复制的容器,达到读的最大并发;
   适用于读多写少的情况;

Concurrent容器

并发策略:

  使用分段锁,首先将容器分成多段,每段使用不同的锁,对不同段达到读写并发,相同段读并发,写同步

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/73644.html

相关文章

  • 非全屏 Weex 页面开发中的 Android 适配

    摘要:代码中的高度和宽度的单位均为,然而,在手机屏幕上显示的高宽却不一定与代码指定的相同。原因是框架在底层做了针对不同屏幕的适配工作,具体计算公式为实际高宽代码高宽屏幕宽度。 weex代码中的高度和宽度的单位均为px,然而,在手机屏幕上显示的高宽却不一定与代码指定的相同。原因是weex框架在底层做了针对不同屏幕的适配工作,具体计算公式为 实际高宽 = 代码高宽 * (屏幕宽度 / 750)。...

    gxyz 评论0 收藏0
  • 六大布局之LinearLayout

    摘要:什么是界面布局为应用程序提供界面架构。线性布局指子控件以水平或垂直方式排列,正如其名字一样,这个布局中的所有控件在线性方向上依次排列。可以把布局看作是一个可以放置很多控件的容器,它可以按照一定的规律调整控件的位置,从而实现精美的界面。 1. 什么是Layout? Layout——界面布局,为应用程序提供界面架构。控制Activity中控件的大小、位置、颜色等属性的方法. Layout...

    Travis 评论0 收藏0

发表评论

0条评论

roland_reed

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<