Java中的容器类和Android的特有的容器类

发表于

1、ArrayList，Vector，CopyOnWriteArrayList和Collections.SynchronizedList

  • ArrayList是底层是一个动态数组维护的，数组的初始大小是10，每次扩容是oldCapacity + (oldCapacity >> 1)，也即是原来的1.5倍，当添加一个数据之后数组可能越界就会扩容。支持插入空数据。
  • ArrayList中最重要的属性就是elementData数组和size，elementData数组由transient修饰，可以防止自动序列化，因此它实现了readObject和writeObject自定义序列化方法
  • Vector底层也是一个动态数组维护，但是它是线程安全的容器类，它的所有方法都是使用synchronize关键字修饰的，所以它的性能非常之差，所以它是一个同步容器而不是一个并发容器。
  • CopyOnWriteArrayList写入时复制容器，写入时复制的思想：简单来说，就是平时查询的时候，都不需要加锁，随便访问，只有在写入/删除的时候，才会从原来的数据复制一个副本出来，然后修改这个副本，最后把原数据替换成当前的副本。修改操作的同时，读操作不会被阻塞，而是继续读取旧的数据。
  • CopyOnWriteArrayList的缺点就是修改中时读取的是旧数据，假如读写频繁就会读到脏数据，而且频繁的替换对象，会消耗大量内存。
  • Collections.synchronizedList()方法可以将一个ArrayList结构转换成线程安全的数据结构，它实现是利用了synchronize代码块锁住了一个Object对象，所有的操作都使用同步代码块

2、HashMap，HashSet，Hashtable，ConcurrentHashMap，TreeMap

  • HashMap散列表结构，底层实现利用数组加链表实现，java8以后使用数组加链表/红黑树，增加了hash冲突情况下的数据查找效率，初始容量默认为16，如果需要自定义初始容量，必须要是2的幂数，因为根据它的hash规则，如果不是2的幂，数组中的某些位置会被浪费，会大大增加hash冲突的概率。
  • fail-fast机制，HashMap是非线程安全的，当在使用迭代器的时候有其他线程修改Map，就会抛出ConcurrentModificationException，当然，当前线程的修改也会导致这个异常
  • Hashtable实现也是数组，但是它的数组的默认初始容量是11，这个等他的计算索引的方式相关
  • HashMap计算索引的方式是h&(length-1)，而HashTable用的是模运算，效率上是低于HashMap的
  • HashTable每次扩容都是旧容量的2倍加2
  • HashMap的在实现resize()时，新table[]列表采用LIFO方式，即队头插入，这样做的目的是避免尾部遍历。
    尾部遍历是为了避免在新列表插入数据时，遍历队尾的位置。因为直接插入的效率更高
  • HashMap页可以使用Collections.synchronizedMap()这个方法变成线程安全的类，但是效率依然不高

介绍效率比较高，而且线程安全的散列表结构ConcurrentHashMap

  • 基础结构与HashMap一样
  • jdk1.7下
    Segment（分段锁）类，它继承自ReentrantLock。
    ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问
  • 坏处是这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长
  • 好处是写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上）。
  • jdk1.8
    JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。
    Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。
    CAS+Synchronized保证线程安全

至于HashSet

  • 使用过它的都知道，这个容器类可以存唯一的值，重复插入的会被覆盖，其实HashSet底层实现就是一个HashMap，插入的值就是它的key，value值是一个唯一的PRESENT，我们都知道HashMap中是没有重复的key的，原因是不同的值计算出来的hashcode值不同。
  • 也可以使用Collections.synchronizedSet()方法来将它变成一个线程安全的容器类

TreeMap

  • 一种有序的散列表容器，它的实现是利用了红黑树的数据结构，所以它是有序的，它是非线程安全的，我们知道红黑树的查找效率很高(O(lgn))，所以TreeMap继承了这个特性

3、LinkedHashMap，LinkedHashSet

  • LinkedHashMap它的实现是继承于HashMap，由一个双向链表构成
  • 它是有序的，默认顺序为插入顺序，还有一种顺序是根据访问顺序将访问后数据放到链表尾部，想要使用这种排序需要在构造器中传入true，默认为false
  • LinkedHashMap以HashMap结构保存数据结构，一个LinkedList保存数据的插入顺序
  • 利用LinkedHashMap的特性可以实现LRU算法

4、SparseArray，ArrayMap，SparseBooleanArray等

  • 这几个都是Android才有的容器类
  • SparseArray很简单粗暴，利用Int作为key。它保存两个数组，一个是Int类型的key数组，一个是Object类型的value数组，加入数据是先用二分查找去查找是否在key数组已经存在有这个相同的key，没有就新增，有就返回对应value的在数组中下标，然后替换，这个数据类的缺点是增删改查都会使用二分查找，不适用存储大量数据
  • ArrayMap和SparseArray类似，区别是它使用hash值存储在key数组中的，SparseArray是直接存储int在key数组中，缺点也是查找效率没HashMap高，它主要是提高内存效率。