SparseArray与HashMap

SparseArray

1. sparseArray

For maps where the keys are of type integer, it's typically more efficient to use the Android SparseArray API.
This is particularly useful when the value types are primitives like ints, where you can use SparseIntArray and avoid auto-boxing the values from int to Integer.
If you need to construct a HashMap because you need to call an API outside of your control which requires a Map, you can suppress this warning using for example the @SuppressLint annotation.

SparseArray的get(int key)方法
调用 public E get(int key, E valueIfKeyNotFound) ，

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];
        }
    }

使用了二分查找方法

// This is Arrays.binarySearch(), but doesn't do any argument validation.
    static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;  //  无符号右移一位，相当于（lo+hi）除以2
            final int midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }

SparseArray与HashMap内部存储结构比较

SparseArray 的内部存储是通过两个数组，采用了压缩式稀疏数组，通过二分查找法进行查找，存储元素是以key值元素从小到大的顺序排列。

HashMap 的内部存储结构是以哈希表带拉链结构（数组<容量为16>＋链表） HashMap中的数据量>容量*装载因子
JDK1.8 以前HashMap的实现是 数组＋链表。
当HashMap中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候HashMap就相当于一个单链表，如果单链表有n个元素，遍历的时间复杂度就是O(n)。优势就没了！
针对这种情况，JDK1.8中引入了红黑树(查找时间复杂度为O(logn))来优化这个问题。

 /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     一个桶的树化阀值
     当桶中元素个数超过 8 时，需要使用红黑树替代链表
     */
    static final int TREEIFY_THRESHOLD = 8 ;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     一个树的链表还原阀值
     当扩容时，桶中元素小于 6 ，就会把树形的桶元素还原（切分）为链表结构
     至少为 6 ，避免频繁转换
     */
    static final int UNTREEIFY_THRESHOLD = 6 ;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     哈希表带最小树形化容量
     当哈希表中的容量大于这个值时，表中的桶才能进行树形化
     否则桶内元素太多时会扩容，而不是树形化
     为了避免进行扩容，树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
     */
    static final int MIN_TREEIFY_CAPACITY = 64 ;

HashMap与HashTable区别
HashMap is unsynchronized and permits null.

相关知识

int之类的基本类型是无法直接加入到collection中的，collection中只能放置对象的引用，所以在把基本类型添加到collection中时需要把基本数据类型包装为对应的包装类。

List list = new ArrayList();
list.add(new Integer(10));

在JDK5中添加了一个新特性叫auto-boxing (自动装箱)。可以直接向collection中添加基本数据类型，看上去好像是collection支持添加基本数据类型了，但事实上是编译器自动帮你将基本数据类型转换为了对应的包装类，如下

List<Integer> list = new ArrayList<Integer>();
list.add(10);

当你需要将数值放到一个collection中或类似必须进行基本类型与对象的转换时才使用auto boxing，而在科学计算或其他性能敏感的系统里一定要谨慎使用。

auto-boxing

Converting a primitive value into an object of the corresponding wrapper class is called autoboxing. For example, converting int to Integer class. The Java compiler applies autoboxing when a primitive value is:

• Passed as a parameter to a method that expects an object of the corresponding wrapper class.
• Assigned to a variable of the corresponding wrapper class.

Unboxing

Converting an object of a wrapper type to its corresponding primitive value is called unboxing. For example conversion of Integer to int. The Java compiler applies unboxing when an object of a wrapper class is:

• Passed as a parameter to a method that expects a value of the corresponding primitive type.
• Assigned to a variable of the corresponding primitive type.

Primitive type	Wrapper Class
boolean	Boolean
byte	Byte
char	Character
float	Float
int	Integer
long	Long
short	Short
double	Double