1.Map
在之前的两节中，介绍了Android中数据结构框架图，以及Collection接口中List、Set及它们的常用实现类。传送门(→_→)
Android中的数据结构解析（一）ArrayList、LinkedList和Vector
Android中的数据结构解析（二）HashSet、LinkedHashSet、TreeSet
本节要介绍的是Map接口及其实现类HashMap、HashTable和TreeMap。前面提过，Collection可以看做是value的集合，而Map可以看做是(key, value)的集合。Map提供了一组key到value的映射关系，其中key是唯一的，每个key映射到的value也是唯一的，而value是允许重复的。Map接口没什么要说的，直接进入开发中最常见常用好用的Map实现类：HashMap。
2.HashMap
HashMap在数据结构中可以看做是链表+散列，底层使用数组+链表的方式实现。再来复习一下数组和链表的特点：数组的特点是寻址快，插入删除慢；而链表的特点是寻址慢，插入删除快。那么，有没有一种数据结构，能综合两者的优点？当然是有的，HashMap就是这样一种数据结构，我们来看一下它是如何实现的。
当new出一个HashMap对象时，也就会初始化一个数组，看下代码：
/**
* The hash table. If this hash map contains a mapping for null, it is
* not represented this hash table.
*/
transient HashMapEntry<K, V>[] table;
/**
* Constructs a new empty {@code HashMap} instance.
*/
@SuppressWarnings("unchecked")
public HashMap() {
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}
可以看到，HashMap初始化时，同时初始化一个HashMapEntry<K, V>对象的数组，再来看一下HashMapEntry<K, V>：
static class HashMapEntry<K, V> implements Entry<K, V> {
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;
HashMapEntry<K, V>包含了四个变量，key和value不用说，看一下其他两个变量hash和next。
我们已经知道，HashMap使用一个HashMapEntry<K, V>对象的数组来存放元素，那么，当我们向一个HashMap中put元素的时候，HashMap是如何确定这个元素放在数组中的哪个位置呢？这里就用到了hash算法。hash算法根据元素的key值来确定一个hash值，这个hash值就可以确定元素在数组中的位置。
那么问题来了，如果在计算出来的位置上，已经有了其他的元素怎么办呢？举个例子，数组中的index位置处，原本存在着元素A，这时put进来一个元素B，经过hash算法计算，元素B也将存在index这个位置，那岂不是会有覆盖的风险？这时候链表就发挥作用了。元素B将替换元素A，即数组中HashMapEntry<K, V>的key和value将会替换成新元素的，同时生成一个新的HashMapEntry<K, V>对象，而A中的变量next将会指向新的对象。即当hash值不同时，HashMap中的元素以数组的形式存放，而当hash值相同时，相同hash值的元素以链表形式存放。如下图所示：
HashMap.png
put方法源码如下：
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);//key值为null时的处理
}
int hash = secondaryHash(key.hashCode());//通过key值的hashCode()方法计算出hash值
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);//通过hash值计算出数组中的位置
//判断是否有相同的key，若有，则用新value替换旧value
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
//如果数组长度不够了，则扩容
//由于HashMap也是数组实现，一样会遇到扩容问题，关于扩容的原理和优化方法参考第一节ArrayList
//HashMap的扩容略有不同。若有兴趣请阅读源码~
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);//在index位置处插入新元素
return null;
}
注释已经写得很详细了。For more information，请自己阅读源码~~
put方法的原理弄懂之后，get方法也就很简单了~从HashMap中get一个元素时，先通过key的hashCode方法得到hash值，找到该元素在数组中的位置；再通过key的equals方法，在链表中找到对应的元素，也就找到了key对应的value。
通过以上叙述，我们可以得出结论：任何对象都可以作为key存入HashMap中，前提是这个对象合理的重写了hashCode和equals方法。当然，常用的key值对象Integer和String等，早已重写好了这两个方法，用它们作key的时候就不用操心了。
3.Hashtable
Hashtable继承Dictionary类，同样是通过key-value键值对保存数据的数据结构。Hashtable和HashMap最大的不同是Hashtable的方法都是同步的，在多线程中，你可以直接使用Hashtable，而如果要使用HashMap，则必须要自己实现同步来保证线程安全。当然，如果你不需要使用同步的话，HashMap的性能是肯定优于Hashtable的。此外，HashMap是接收null键和null值的，而Hashtable不可以。
4.TreeMap
TreeMap是基于红黑树实现的，它是一个有序的key-value集合，可以根据key的自然顺序进行自动排序，当key是自定义对象时，TreeMap也可以根据自定义的Comparator进行排序。关于自然顺序和自定义Comparator排序，可以参考Android中的数据结构解析（二）HashSet、LinkedHashSet、TreeSet中讲到的TreeSet，TreeSet就是基于TreeMap实现的。这里就不再重复了。另外，TreeMap和HashMap一样，也是非同步的。
5.总结
Map接口中最重要的就是HashMap了。对于HashMap，需要理解它的数组+链表的实现原理；通过key计算元素位置的方法；以及key需要重写的hashCode和equals方法。HashMap的设计非常巧妙，有空仔细阅读HashMap的源码，一定会有收获的~ Hashtable的方法实现了同步，可以在多线程中保证线程安全。TreeMap是有序的key-value集合，可以根据key自动排序。
网友评论