一些与HaspMap有关的数据结构

1. HashMap

HashMap代表一个字典，它的容量会自动调整为2的幂次方，载入因子为0.75。HashMap的数据结构为数组+单链表。其主干是数组实现，如下

HashMapEntry<K, V>[] table;

HashMapEntry代表字典中的一个元素，它是一种单链表结构，定义如下。

static class HashMapEntry<K, V> implements Entry<K, V> {
    final K key;
    V value;
    final int hash;
    HashMapEntry<K, V> next; //单链表
}

a.从HashMap中读取数据的代码如下

public V get(Object key) {
    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; e != null; e = e.next) {
        K eKey = e.key;
        if (eKey == key || (e.hash == hash && key.equals(eKey))) {
            return e.value;
        }
    }
    return null;
}

首先先计算传入key对象的hash值，计算方法是无置位的移位运算，O(1)运算量，可以认为此哈希值决定了元素在数组中的位置，这里可以叫做适当位置。

而后从数组上的适当位置开始遍历链表，并使用传入key对象来匹配链表对象。匹配条件有两个，满足其中一个就可以任务字典上存有该键值的对象

1. key对象的引用相同
2. key对象的 hash 值相同，且equals()方法也相同。

这说明字典中的取值和是否发生覆盖完全是由 key对象决定，与value对象毫无关系。

其中第二个条件值得注意，其意为 key 对象必须完全相等。有时虽然key对象的 hash 值相同但它们却不相等。

b.向HashMap中写入数据与之同理

public V put(K key, V value)

首先计算 K 的哈希值得到元素在数组上的位置，而后遍历链表如果值已经存在就更新它，如果不存在就创建。

2. LinkedHashMap

LinkedHashMap是HashMap的子类。HashMap的实现决定了它的读取是随机的，LinkedHashMap则强调插入顺序，它依然采用数组+链表的结构，但在元素上添加了头尾指针，使之形成双链表的结构，并且整个数据给出了一个总的头指针，其内部的元素定义如下

static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
    LinkedEntry<K, V> nxt;
    LinkedEntry<K, V> prv;
}

3.LruCache

LruCache主要用于缓存，其功能由LinkedHashMap对象代理实现。

特殊之处在于LruCache需要计算键值对象的内存大小，并将存储对象的总大小维持的在指定范围内。如果超出容量，LruCache会调整和删除一些数据，实际上使用什么策略完全可以自己定义。

此外LruCache的读写时线程安全的，而且不支持空值，它还维护了一些缓存用到的统计信息，如命中数等。

public class LruCache<K, V> {
    private final LinkedHashMap<K, V> map;

    private int size;
    private int maxSize;

    private int putCount;
    private int createCount;
    private int evictionCount;
    private int hitCount;
    private int missCount;
}

LruCache使用强引用，加强了对对象的控制。队列大小默认是4M。

4.ArrayMap

HashMap是Java的通用类，HashMap的弱点有很多，如不支持基本类型作为key值，要装箱转换；线程不安全；链表实现影响访问效率等，android.util包定义了很多对具体类型的优化数据结构体代替它。

ArrayMap采用完全的数组实现对HashMap进行了改善，其定义如下

int[] mHashes; //保存key对象的hash值，该值决定元素在数组中的位置
Object[] mArray;//键值对对象
int mSize;

该字典中键值对对象是共存在一个数组中的，采用key-value-key-value的形式，而 key 对象的哈希值依然决定了键值对的数组中的唯一位置，不过计算与 HashMap 不同。

读取对象时，首先计算 key 对象的哈希值，而后在 哈希值数组中查找，如果存在就说明该值已在字典中存储，由哈希值可以得到元素在数组中的位置，继而读取对象。

写入对象与之同理，先计算 key 对象的哈希值，而后进行更新或创建。

5.SparseArray

SparseArray是对HashMap进行了进一步改善，它是一个key值为int类型的字典，这样就不会使用装箱机制，也不再需要一个多余的Entry对象。即SparseArray是一个键类型固定为 int 的定制化字典，受泛型机制限制，HashMap 是不可能实现这一点的。

public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object(); //惰性删除
    private boolean mGarbage = false;//是否要进行垃圾回收
    private int[] mKeys; //key数组
    private Object[] mValues; //值数组
    private int mSize;
}

读取数组的原理是一样的，根据 key 值找元素的位置，将由位置读取值类型。不过这里的 key 值就是 int 类型而已，取消使用 hash 数组，而且搜索位置的算法也变成了二叉搜索。

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

因为是采用二叉搜索提高搜索效率，那么 key 数组就要维持顺序，这使得写入数据时要采用插入操作，如果频繁写入和删除，使用这种数据结构就将失去优势。

为了优化这个问题，SparseArray采用了惰性删除来避免频繁和删除，删除某个值时只进行标记，必须要整理数组时再统一处理。

二分搜索本身比 HashMap 的位运算是慢了很多的，此外SparseArray的数组实现决定了它不适合存储较大规模数据，只适合在数据量较小时(如在几百以内)，差异不明显的情况下使用。

7.一些其它数据结构

7.1 有理数(Rational)

Rational rational = Rational.parseRational("1/2");
rational = Rational.parseRational("1:2");

7.2 宽度/高度(Size/SizeF)

Size size = new Size(100,100);
size = Size.parseSize("100*100");

7.3 两元素元组(Pair)

Pair<String,Integer> apple = new Pair<>("apple",1);
Pair<String,Integer> android = Pair.create("android",2);

7.4 范围(Range)

描述两个值之间的范围，只要值对象实现Comparable接口。支持获取上下限，交集，扩展，claim等操作。

Range<Integer> range = Range.create(1,20);

参考文献

• android.util
• Jenkins hash function