常用集合的原理分析(二) 集合例子

五、ConcurrentHashMap

• 支持线程安全的并发容器 ConcurrentHashMap,原理和HashMap差不多，区别就是采用了CAS + synchronized 来保证并发安全性
• putVal 加了同步锁 synchronized

 final V putVal(K key, V value, boolean onlyIfAbsent) {
 if (key == null || value == null) throw new NullPointerException();
 //根据 key 计算出 hashcode
 int hash = spread(key.hashCode());
 int binCount = 0;
 for (Node<K,V>[] tab = table;;) {
 Node<K,V> f; int n, i, fh;
 // 判断是否需要进行初始化
 if (tab == null || (n = tab.length) == 0)
 tab = initTable();
 //f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功
 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
 if (casTabAt(tab, i, null,
 new Node<K,V>(hash, key, value, null)))
 break; // no lock when adding to empty bin
 }
 else if ((fh = f.hash) == MOVED)
 tab = helpTransfer(tab, f); //如果当前位置的 hashcode == MOVED == -1,则需要进行扩容
 else {
 //如果都不满足，则利用 synchronized 锁写入数据
 V oldVal = null;
 // todo put 数据的时候 加入了锁
 synchronized (f) {
 if (tabAt(tab, i) == f) {
 if (fh >= 0) {
 binCount = 1;
 for (Node<K,V> e = f;; ++binCount) {
 K ek;
 if (e.hash == hash &&
 ((ek = e.key) == key ||
 (ek != null && key.equals(ek)))) {
 oldVal = e.val;
 if (!onlyIfAbsent)
 e.val = value;
 break;
 }
 Node<K,V> pred = e;
 if ((e = e.next) == null) {
 pred.next = new Node<K,V>(hash, key,
 value, null);
 break;
 }
 }
 }
 else if (f instanceof TreeBin) {
 Node<K,V> p;
 binCount = 2;
 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
 value)) != null) {
 oldVal = p.val;
 if (!onlyIfAbsent)
 p.val = value;
 }
 }
 else if (f instanceof ReservationNode)
 throw new IllegalStateException("Recursive update");
 }
 }
 if (binCount != 0) {
 //如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树
 if (binCount >= TREEIFY_THRESHOLD)
 treeifyBin(tab, i);
 if (oldVal != null)
 return oldVal;
 break;
 }
 }
 }
 addCount(1L, binCount);
 return null;
 }

• get方法

 public V get(Object key) {
 Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
 int h = spread(key.hashCode());
 if ((tab = table) != null && (n = tab.length) > 0 &&
 (e = tabAt(tab, (n - 1) & h)) != null) {
 //根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值
 if ((eh = e.hash) == h) {
 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
 return e.val;
 }
 //如果是红黑树那就按照树的方式获取值
 else if (eh < 0)
 return (p = e.find(h, key)) != null ? p.val : null;
 // 就不满足那就按照链表的方式遍历获取值
 while ((e = e.next) != null) {
 if (e.hash == h &&
 ((ek = e.key) == key || (ek != null && key.equals(ek))))
 return e.val;
 }
 }
 return null;
 }

• 基本上的变量都是被volatile关键字修饰

 transient volatile Node<K,V>[] table;
 private transient volatile Node<K,V>[] nextTable;
 private transient volatile long baseCount;
 ...

volatile关键字 Java多线程的三大核心

1、 原子性 :java原子性和数据库事务的原子性差不多，一个操作要么是全部执行成功或者是失败.

• JVM 只保证了基本的原子性，但是类似 i++ 之类的操作，看着好像是原子的操作，其实里面涉及到了三个步骤
• 获取 i 的值
• 自增
• 在赋值给 i
• 这三个步骤 要实现i++ 这样的原子操作就需要用到 synchronized或者是 了lock进行加锁处理。
• 如果是基础类的自增操作可以使用AtomicInteger 这样的原子类来实现(其本质是利用了CPU 级别的 的 CAS 指令来完成的)。AtomicInteger 是线程安全的
• 其中用的最多的方法就是: incrementAndGet() 以原子的方式自增

2、可见性

• 现在的计算机，由于 cpu 直接从 主内存中读取数据的效率不高。所以都会对应的 cpu高速缓存，先将主内存中的数据读取到缓存中，线程修改数据之后首先更新到缓存中，之后才会更新到主内存。如果此时还没有将数据更新到主内存其他的线程此时读取就是修改之前的数据
• volatile关键字就是用于保存内存的可见性，当线程A更新了volatite的修饰的变量的话，他会立即刷新到主线程，并且将其余缓存中该变量的值清空，导致其余线程只能去主内存读取最新的值

*synchronized 和加锁也能保证可见性，实现原理就是在释放锁之前其余线程是访问不到这个共享变量的。但是和volatile 相比较起来开销比较大 ！

• 但是volatile不能够替换synchronized因为volatile 不能够保证原子性 (要么执行成功或者失败，没有中间的状态)

3、顺序性

int a = 100 ; //1
int b = 200 ; //2
int c = a + b ; //3

• 正常的代码的执行顺序应该是1》》2》》3。但是有时候 JVM为了提高整体的效率会进行指令重排导致执行顺序可能是 2》》1》》3。但是JVM 也不能是 什么都进行重排，是在保证最终结果和代码顺序执行结果是一致的情况下才可能会进行重排
• 重排在单线程中不会出现问题，但是在多线程中就会出现顺序不一致的问题
• java中可以使用 volatile 关键字来保证顺序性，synchronized和lock 也可以来保证有序性，和保证 原子性的方式一样，通过同一段时间只能一个线程访问来实现的
• 除了 volatile 关键字显式的保证顺序之外，jvm HIA通过 happen-before 原则来隐式来保证顺序性。
• volitle的应用，主要是在单利，个人感觉这是常用的在移动端的开发!当然可以使用内部类或者是单利去实现，更多的设计模式
• 1、volatile 实现一个双重检查锁的单例模式

 public class Singleton {
 private static volatile Singleton singleton;
 private Singleton() {
 }
 public static Singleton getInstance() {
 if (singleton == null) {
 synchronized (Singleton.class) {
 if (singleton == null) {
 singleton = new Singleton();
 }
 }
 }
 return singleton;
 }
}

• 这里的 volatile 关键字主要是为了防止指令重排。 如果不用volatile，singleton = new Singleton();，这段代码其实是分为三步：
• 分配内存空间。(1)
• 初始化对象。(2)
• 将 singleton 对象指向分配的内存地址。(3)
• 加上volatile 是为了让以上的三步操作顺序执行，反之有可能第三步在第二步之前被执行就有可能导致某个线程拿到的单例对象还没有初始化，以致于使用报错。
• 2、控制停止线程的标记

 private volatile boolean flag ;
 private void run(){
 new Thread(new Runnable() {
 @Override
 public void run() {
 doSomeThing();
 }
 });
 }
 private void stop(){
 flag = false ;
 }

• 如果没有用volatile 来修饰flag，就有可能其中一个线程调用了 stop()方法修改了flag的值并不会立即刷新到主内存中，导致这个循环并不会立即停止.这里主要利用的是 volatile 的内存可见性 .

六、HashSet

• HashSet 是一个不允许存储重复元素的集合。
• HashSet的源码只有三百多行，原理非常简单，主要底层还是HashMap。
• map 和 PERSENT:

 // map ：用于存放最终数据的。
 private transient HashMap<E,Object> map;
 // Dummy value to associate with an Object in the backing Map
 // PRESENT ：是所有写入 map 的 value 值。
 private static final Object PRESENT = new Object();

• 构造方法:底层一个hashMap

 public HashSet() {
 map = new HashMap<>();
 }

• 关键的就是这个 add()方法。 可以看出它是将存放的对象当做了 HashMap的健，value 都是相同的 RESENT。由于 HashMap 的 key 是不能重复的，所以每当有重复的值写入到 HashSet时，value会被覆盖，但 key不会受到影响，这样就保证了HashSet中只能存放不重复的元素。

 public boolean add(E e) {
 return map.put(e, PRESENT)==null;
 }

七、LinkedHashMap

• HashMap 是一个无序的 Map，每次根据 key 的 hashcode 映射到 Entry 数组上，所以遍历出来的顺序并不是写入的顺序。 因此 JDK 推出一个基于HashMap但具有顺序的LinkedHashMap来解决有排序需求的场景。它的底层是继承于HashMap实现的，由一个双向链表所构成。
• LinkedHashMap 的排序方式有两种：
• 根据写入顺序排序。
• 根据访问顺序排序(LRU底层的原理)。 其中根据访问顺序排序时，每次get都会将访问的值移动到链表末尾，这样重复操作就能得到一个按照访问顺序排序的链表。
• LinkedHashMap中的 Entry:利用了头节点和其余的各个节点之间通过 Entry中的 after和 before指针进行关联

• 变量

• 
  
• 构造方法，LRUchace最近最少使用的缓存底层就是这个构造函数。

 public LinkedHashMap(int initialCapacity,
 float loadFactor,
 boolean accessOrder) {
 super(initialCapacity, loadFactor);
 this.accessOrder = accessOrder;
 }

• 侧重关注 put，会走父类HashMap中的put方法，具体请看HashMap put 方法的解释
• 1、 在 LinkedHashMap 重写了,newNode的方法。 使用了LinkedHashMap.Entry里面多了两个结点 Entry<K,V> before, after;

 Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
 LinkedHashMap.Entry<K,V> p =
 new LinkedHashMap.Entry<K,V>(hash, key, value, e);
 //秘密就在于 new的是自己的Entry类，然后调用了linkedNodeLast
 linkNodeLast(p);
 return p;
}

• 2、实现了afterNodeAccess()方法， void afterNodeAccess(Node<K,V> p) { }！此函数执行的效果就是将最近使用的Node，放在链表的最末尾。特别说明一下，这里是显示链表的修改后指针的情况，实际上在桶里面的位置是不变的，只是前后的指针指向的对象变了！

// 此函数执行的效果就是将最近使用的Node，放在链表的最末尾
void afterNodeAccess(Node<K,V> e) { // move node to last
 LinkedHashMap.Entry<K,V> last;
 //仅当按照LRU原则且e不在最末尾，才执行修改链表，将e移到链表最末尾的操作
 if (accessOrder && (last = tail) != e) {
 //将e赋值临时节点p， b是e的前一个节点， a是e的后一个节点
 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
 //设置p的后一个节点为null，因为执行后p在链表末尾，after肯定为null
 p.after = null;
 //p前一个节点不存在，情况一
 if (b == null)
 head = a;
 else
 b.after = a;
 if (a != null)
 a.before = b;
 //p的后一个节点不存在，情况二
 else
 last = b;
 if (last == null)
 head = p;
 else { //正常情况，将p设置为尾节点的准备工作，p的前一个节点为原先的last，last的after为p
 p.before = last;
 last.after = p;
 }
 //将p设置为将p设置为尾节点
 tail = p;
 ++modCount; // 修改计数器+1
 }
}

• 3、 put方法 执行的第二个步骤 ，这个方法没什么用尽可能删除最老的 插入后把最老的Entry删除，不过removeEldestEntry总是返回false，所以不会删除，估计又是一个方法给子类用的

void afterNodeInsertion(boolean evict) { // possibly remove eldest
 LinkedHashMap.Entry<K,V> first;
 if (evict && (first = head) != null && removeEldestEntry(first)) {
 K key = first.key;
 // todo hashmap中移除 Node结点
 removeNode(hash(key), key, null, false, true);
 }
}
 // 如果映射表示缓存，这是有用的：它允许通过删除过时条目来减少内存消耗的映射。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
 return false;
}

• 4 、afterNodeRemoval()移除结点也会重写，因为结点都不一样

 void afterNodeRemoval(Node<K,V> e) { // unlink
 //与afterNodeAccess一样，记录e的前后节点b，a
 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
 //p已删除，前后指针都设置为null，便于GC回收
 p.before = p.after = null;
 //与afterNodeAccess一样类似，一顿判断，然后b，a互为前后节点
 if (b == null)
 head = a;
 else
 b.after = a;
 if (a == null)
 tail = b;
 else
 a.before = b;
}

• get()方法详情,然后调用父类HashMap 的getNode()去找结点

public V get(Object key) {
 Node<K,V> e;
 //调用HashMap的getNode的方法，
 if ((e = getNode(hash(key), key)) == null)
 return null;
 if (accessOrder)
 afterNodeAccess(e);
 return e.value;
 }

• HashMap中的getNode() 方法

final Node<K,V> getNode(int hash, Object key) {
 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
 if (first.hash == hash && // always check first node
 ((k = first.key) == key || (key != null && key.equals(k))))
 return first;
 if ((e = first.next) != null) {
 if (first instanceof TreeNode)
 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
 do {
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 return e;
 } while ((e = e.next) != null);
 }
 }
 return null;
 }

• 关于访问顺序排序的Demo,我只想说明了一下，等于用了的数据，就会放在链表的末尾，这个类也是安卓中LruCache的底层原理

LinkedHashMap<String, Integer> map1 = new LinkedHashMap<String, Integer>(10, (float) 0.75,true);
 map1.put("1",1) ;
 map1.put("2",2) ;
 map1.put("3",3) ;
 map1.put("4",4) ;
 map1.put("5",5) ;
 map1.put("6",6) ;
 map1.put("7",7) ;
 map1.put("8",8) ;
 map1.put("9",9) ;
 map1.put("10",10) ;
 map1.get("6");
 // {1=1, 2=2, 3=3, 4=4, 5=5, 7=7, 8=8, 9=9, 10=10, 6=6}
 System.out.println("map1=="+map1);

八、LruCache

• Android中提供了一种基本的缓存策略，即LRU（least recently used）。基于该种策略，当存储空间用尽时，缓存会清除最近最少使用的对象
• LRU（Least Recently Used）最近最少使用的，看了源码才知道核心是LRUCache类，这个类的核心其实是 LinkedHashMap类.
• Demo 如下

 LruCache<Integer,String> lruCache=new LruCache<>(5);
 lruCache.put(1,"1");
 lruCache.put(2,"2");
 lruCache.put(3,"3");
 lruCache.put(4,"4");
 lruCache.put(5,"5");
 lruCache.get(1);
 lruCache.get(2);
 lruCache.get(3);
 lruCache.get(4);
 Map<Integer, String> snapshot = lruCache.snapshot();
 //lruCache={5=5, 1=1, 2=2, 3=3, 4=4} 5最少使用到
 System.out.println("lruCache="+snapshot.toString());
 //当多添加一个的话，那么5就会被删除，加入6上去
 lruCache.put(6,"6");
 // new lruCache={1=1, 2=2, 3=3, 4=4, 6=6}
 Map<Integer, String> snapshot1 = lruCache.snapshot();
 System.out.println(" new lruCache="+snapshot1.toString());

• 构造方法,可以明显看出，底层使用的是LinkedHashMap.
• public LruCache(int maxSize) {
• if (maxSize <= 0) {
• throw new IllegalArgumentException("maxSize <= 0");
• }
• this.maxSize = maxSize;
• // 初始化这里 就是 new的 true的 所以使用的顺序排序
• this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
• }
• put方法 :重要的就是在添加过缓存对象后，调用trimToSize()方法，来判断缓存是否已满，如果满了就要删除近期最少使用的算法.同时线程也是安全的。

 public final V put(K key, V value) {
 //不可为空，否则抛出异常
 if (key == null || value == null) {
 throw new NullPointerException("key == null || value == null");
 }
 V previous;
 // 多线程 可以使用
 synchronized (this) {
 //插入的缓存对象值加1
 putCount++;
 //增加已有缓存的大小
 size += safeSizeOf(key, value);
 //向map中加入缓存对象
 previous = map.put(key, value);
 if (previous != null) {
 //如果已有缓存对象，则缓存大小恢复到之前
 size -= safeSizeOf(key, previous);
 }
 }
 //entryRemoved()是个空方法，可以自行实现
 if (previous != null) {
 entryRemoved(false, key, previous, value);
 }
 //调整缓存大小(关键方法)
 trimToSize(maxSize);
 return previous;
 }

• 1、safeSizeOf方法,这个sizeof的方法，就是我们自己需要重写的，记得图片加载框架的设计，就会运用到他

 private int safeSizeOf(K key, V value) {
 // 每一个的需要缓存的大小
 int result = sizeOf(key, value);
 if (result < 0) {
 throw new IllegalStateException("Negative size: " + key + "=" + value);
 }
 return result;
 }
 protected int sizeOf(K key, V value) {
 return 1;
 }

• 2、调整缓存大小(关键方法) trimToSize(maxSize); maxSize也就是指定的大小，当if (size <= maxSize) { break; }这个判断不成立的时候，就会往下走，迭代器就会去获取第一个对象，即队尾的元素，近期最少访问的元素。然后把它删除该对象，并更新缓存大小 map.remove(key);

private void trimToSize(int maxSize) {
 while (true) {
 K key;
 V value;
 synchronized (this) {
 if (size < 0 || (map.isEmpty() && size != 0)) {
 throw new IllegalStateException(getClass().getName()
 + ".sizeOf() is reporting inconsistent results!");
 }
 if (size <= maxSize) {
 break;
 }
 //迭代器获取第一个对象，即队尾的元素，近期最少访问的元素
 Map.Entry<K, V> toEvict = null;
 for (Map.Entry<K, V> entry : map.entrySet()) {
 toEvict = entry;
 }
 if (toEvict == null) {
 break;
 }
 key = toEvict.getKey();
 value = toEvict.getValue();
 //删除该对象，并更新缓存大小
 map.remove(key);
 size -= safeSizeOf(key, value);
 evictionCount++;
 }
 // 空实现
 entryRemoved(true, key, value, null);
 }
 }

• 关于 get方法！也是一个同步的方法。

 public final V get(K key) {
 //key为空抛出异常
 if (key == null) {
 throw new NullPointerException("key == null");
 }
 V mapValue;
 synchronized (this) {
 //获取对应的缓存对象
 //get()方法会实现将访问的元素更新到队列头部的功能
 // todo LinkedHashMap 里面已经实现了 如果 添加到头部去
 mapValue = map.get(key);
 if (mapValue != null) {
 hitCount++;
 return mapValue;
 }
 missCount++;
 }
 ...
}

• LruCache使用的Demo,这个 Demo 就看看，没吊用。

 public class ImageCache {
 //定义LruCache，指定其key和保存数据的类型
 private LruCache<String, Bitmap> mImageCache;
 ImageCache() {
 //获取当前进程可以使用的内存大小，单位换算为KB
 final int maxMemory = (int)(Runtime.getRuntime().maxMemory() / 1024);
 //取总内存的1/4作为缓存
 final int cacheSize = maxMemory / 4;
 //初始化LruCache
 mImageCache = new LruCache<String, Bitmap>(cacheSize) {
 //定义每一个存储对象的大小
 @Override
 protected int sizeOf(String key, Bitmap bitmap) {
 return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
 }
 };
 }
 //获取数据
 public Bitmap getBitmap(String url) {
 return mImageCache.get(url);
 }
 //存储数据
 public void putBitmap(String url, Bitmap bitmap) {
 mImageCache.put(url, bitmap);
 }
 }

九、SparseArray

• SparseArray是android里为<Interger,Object> 这样的Hashmap而专门写的类,目的是提高效率，其核心是折半查找函数（binarySearch）。SparseArray仅仅提高内存效率，而不是提高执行效率，所以也决定它只适用于android系统（内存对android项目有多重要）SparseArray不需要开辟内存空间来额外存储外部映射，从而节省内存。
• 变量,核心就是两个数组:mKeys mValues

 //是否可以回收，即清理mValues中标记为DELETED的值的元素
 private boolean mGarbage = false;
 private int[] mKeys; //保存键的数组
 private Object[] mValues; //保存值的数组
 private int mSize; //当前已经保存的数据个数

• 构造方法 ：如果initialCapacity=0那么mKeys,mValuse都初始化为size=0的数组，当initialCapacity>0时，系统生成length=initialCapacity的value数组，同时新建一个同样长度的key数组。

 public SparseArray() {
 this(10);
 }
 public SparseArray(int initialCapacity) {
 if (initialCapacity == 0) {
 mKeys = EmptyArray.INT;
 mValues = EmptyArray.OBJECT;
 } else {
 /* ArrayUtils.newUnpaddedObjectArray 的源码
 public static Object[] newUnpaddedObjectArray(int minLen) {
 return (Object[])VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen);
 }
 */
 mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
 mKeys = new int[mValues.length];
 }
 mSize = 0;
 }

• 关于put方法,关键是通过二分查找，查找相对应的i角标,如果存在的话，直接赋值新的值，如果不存在的话，取 ~i 位非运算符（~）: 十进制变二进制：原码--反码--加一（补码），相当于 value +1 然后 取反 就可以了.然后就会走到 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);和 mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); 中，这样就完成了赋值的过程。

 public void put(int key, E value) {
 // 二分查找，这个i的值,
 int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 //如果找到了，就把这个值给替换上去 ，或者是赋值上去
 // 这里 也就可以解释出为啥 替换为最新的值
 if (i >= 0) {
 mValues[i] = value;
 } else {
 //这里就是key要插入的位置，上面二分查找方法提到过
 //位非运算符（~）
 i = ~i;
 if (i < mSize && mValues[i] == DELETED) {
 mKeys[i] = key;
 mValues[i] = value;
 return;
 }
 if (mGarbage && mSize >= mKeys.length) {
 gc();
 // Search again because indices may have changed.
 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
 }
 // 一个新的值 ，就会把key 和 value 和 i值插入到两个数组中
 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
 mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
 // todo 然后长度 加上 1 nice
 mSize++;
 }
 }

• get方法:通过二分查找法，在mKeys数组中查询key的位置，然后返回mValues数组中对应位置的值，找不到则返回默认值

 public E get(int key, E valueIfKeyNotFound) {
 // 二分查找 感觉不像啊 卧槽
 int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 if (i < 0 || mValues[i] == DELETED) {
 return valueIfKeyNotFound;
 } else {
 return (E) mValues[i];
 }
 }

• delete其实就是把这个 mValues[i]标记为 DELETED.

public void delete(int key) {
 int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 /*
 i>0表示，找到了key对应的下标，否则应该是负数。同时判断mValues[i] 是不是Object这个对象，如果不是，直接替换为Object（DELETE起到标记删除位置的作用）,并标记 mGarbage=true，注意：这里delete只操作了values数组，并没有去操作key数组;
 */
 if (i >= 0) {
 if (mValues[i] != DELETED) {
 mValues[i] = DELETED;
 mGarbage = true;
 }
 }
 }

• removeReturnOld 其实就是多了一步，把要删除的值返回，其余同delete一样

 public E removeReturnOld(int key) {
 int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 if (i >= 0) {
 if (mValues[i] != DELETED) {
 final E old = (E) mValues[i];
 mValues[i] = DELETED;
 mGarbage = true;
 return old;
 }
 }
 return null;
 }

• clear 这里要留意，clear只是清空了values数组，并没有操作keys数组,这里也是传递的地址值，然后通过for循环，把每个元素清空！

 public void clear() {
 int n = mSize;
 Object[] values = mValues;
 for (int i = 0; i < n; i++) {
 values[i] = null;
 }
 mSize = 0;
 mGarbage = false;
 }

• 其实还有个方法append,添加数据的时候最好去使用它，因为它会判断下mSize != 0 && key <= mKeys[mSize - 1]、如果满足了才会调用 put方法，不满足，直接添加数据，而不是一上来就开始进行二分查找。

 // 要使用这个方法 好点 。
 public void append(int key, E value) {
 // 判断了是否 需要 二分查找，还是直接插入
 if (mSize != 0 && key <= mKeys[mSize - 1]) {
 put(key, value);
 return;
 }
 if (mGarbage && mSize >= mKeys.length) {
 // 通过gc的方法，把DELETED值的 values 清空
 gc();
 }
 // 可以直接都要这里来 ，是最节约能量
 mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
 mValues = GrowingArrayUtils.append(mValues, mSize, value);
 mSize++;
 }

• 关于原型模式中的深拷贝的实现，这里也帮我指明了，一定要记得拷贝类中的容器

 @Override
 @SuppressWarnings("unchecked")
 public SparseArray<E> clone() {
 SparseArray<E> clone = null;
 try {
 clone = (SparseArray<E>) super.clone();
 // 原型模式的深拷贝 两个容器的拷贝的过程----！！！
 clone.mKeys = mKeys.clone();
 clone.mValues = mValues.clone();
 } catch (CloneNotSupportedException cnse) {
 /* ignore */
 }
 return clone;
 }

• 其他的 SparseBooleanArray SparseIntArray SparseLongArray 的原理一样
• SparseArray与HashMap无论是怎样进行插入,数据量相同时,前者都要比后者要省下一部分内存,但是效率呢？----在倒序插入的时候,SparseArray的插入时间和HashMap的插入时间远远不是一个数量级.由于SparseArray每次在插入的时候都要使用二分查找判断是否有相同的值被插入.因此这种倒序的情况是SparseArray效率最差的时候.
• 附赠一个二分查找

 /**
 * 二分查找
 * @param ints 需要被查找的数组
 * @param length 数组的长度
 * @param value 查找的值
 */
 private int binarySearch(int[] ints, int length, int value) {
 int i = 0;
 int h = length - 1;
 while (i <= h) {
 /**
 * >>>与>>唯一的不同是它无论原来的最左边是什么数，统统都用0填充。
 * —比如你的例子，byte是8位的，-1表示为byte型是11111111(补码表示法）
 * b>>>4就是无符号右移4位，即00001111，这样结果就是15。
 * 这里相当移动一位，除以二
 */
 //中间的角标
 final int mid = (i + h) >>> 1;// 第一次 2 第二次 mid=3 第三次mid=4
 final int midVal = ints[mid];// 第一次 3 第二次 midVal=4 第三次mid=5
 if (midVal < value) {
 i = mid + 1;// 第一次 3 第二次 i=4
 } else if (value < midVal) {
 h = mid - 1;
 } else if (value == midVal) {
 return mid; //第三次mid=5 返回了
 }
 }
 // 这个取反 ，相当于 value +1 然后 取反 就可以了
 return ~value;
 }

• 附赠System.arraycopy() 的用法

 int[] mKeys={10,5,14,5,46};
 int[] newKeys=new int[5];
 /*
 * @param src 源数组。
 * @param srcPos 表示源数组要复制的起始位置，
 * @param dest 目的地数组。
 * @param destPos 在目标数据中的起始位置。
 * @param length 要复制的数组元素的数目。
 */
 // todo source of type android.util.SparseArray is not an array
 // destPsot +length 不能超过 新的数组的长度
 System.arraycopy(mKeys,0, newKeys, 2, 3);
 for (Integer str : newKeys) {
 System.out.print("newKeys="+str+" ");
 }

最后说明几点

• ArrayList 的主要消耗是数组扩容以及在指定位置添加数据，在日常使用时最好是指定大小，尽量减少扩容。更要减少在指定位置插入数据的操作。
• ArrayList遍历的速度快，插入删除速度慢，随机访问的速度快
• LinkedList 插入，删除都是移动指针效率很高。查找需要进行遍历查询，效率较低。二分查找，如果查找的index的越接近size的一半的话，这样查找的效率很低
• HashMap 是一个线程不安全的容器，发生扩容时会出现环形链表从而导致死循环
• HashMap 是一个无序的 Map，因为每次根据 key的 hashCode映射到Entry 数组上，所以遍历出来的顺序并不是写入的顺序。
• HashMap 遍历的速度慢，底层决定了，插入删除的速度快，随机访问的速度也比较快
• ConcurrentHashMap 并发容器，区别就是采用了CAS + synchronized 来保证并发安全性
• 位与运算符&,把做运算的两个数都转化为二进制的，然后从高位开始比较，如果两个数都是1则为1，否者为0
• 无符号的右移（>>>）:按照二进制把数字右移指定数位，高位直接补零，低位移除！
• a=a|b 等于 a|=b的意思就是把a和b按位或然后赋值给a 按位或的意思就是先把a和b都换成2进制，然后用或操作
• 位异或运算（^）: 运算规则是两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1
• HashSet 底层其实就是 HashMap，只不过是一个value都一样的HashSet.
• LRU（Least Recently Used）最近最少使用的，看了源码才知道核心是LRUCache类，这个类的核心其实是 LinkedHashMap类.
• ~i 位非运算符（~）: 十进制变二进制：原码--反码--加一（补码），相当于 value +1 然后 取反 就可以了
• SparseArray SparseBooleanArray SparseIntArray SparseLongArray 的原理一样
• SparseArray与HashMap无论是怎样进行插入,数据量相同时,前者都要比后者要省下一部分内存,但是效率呢？----在倒序插入的时候,SparseArray的插入时间和HashMap的插入时间远远不是一个数量级.由于SparseArray每次在插入的时候都要使用二分查找判断是否有相同的值被插入.因此这种倒序的情况是SparseArray效率最差的时候.
• 二分查找，是当角标越接近数组长度的一半，效率越低
• 卧槽，刚看了一下总共将近一万字，光写的过程用了16个小时，整理资料大概是10个小时。