集是一个集合，它可以快速的查找现有的元素。但是，要查看一个元素，需要有要查找元素的精确副本。这不是一个非常通用的查找方式。通常，我们知道某些键的信息，并想要查找与之对应的元素。映射表（map）就是为此设计的。映射表用来存储键值对。如果提供了键，就可以查找对应的值。例如，有一张关于员工信息的记录表，键为员工ID，值为Employee。
Java类库为映射表提供了两个通用的实现：HashMap和TreeMap，这两个类都实现了Map接口。
散列映射表对键进行散列，树映射表用键的整体顺序对元素进行排序，并将其组织成搜索树。散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。
应该选择散列映射表还是树映射表呢？散列稍微快一些，如果不需要按照排列顺序访问键，就最好选择散列。
本文主要介绍HashMap类的底层实现，并简单介绍TreeMap但不做过多分析，因为TreeMap使用红黑树实现的，比较复杂，等以后再看。
1 Map接口
Map接口提供了一些映射表的基本操作，下面是这些方法的总结：
（1）查询操作
int size(); boolean isEmpty(); boolean containsKey(Object); boolean containsValue(Object); V get(Object);这些方法的含义都很明确。需要注意的是，containsKey方法、containsValue方法和get方法的参数类型都是Object。
（2）修改方法
V put(K,V); V remove(Object); void putAll(Map<? extends K,? extends V>); void clear();put方法用于添加一个键值对，如果键已经存在就更新值并返回旧值。remove方法删除给定键的键值对并返回值。putAll方法将一个Map中的所有键值对添加到映射表中。clear方法删除所有元素。
（3）视图方法
Set<K> keySet(); Collection<V> values(); Set<Map.Entry<K,V>> entrySet();这三个方法返回三个视图：键集、值集合（不是集）和键值对集。对于视图会在后续的文章中作介绍。
在Map接口中还定义了一个子接口：Entry，用来操作键值对。
这个接口主要有一下几个方法：
K getKey(); V getValue(); V setValue(V value); boolean equals(Object o); int hashCode();含义也比较明确。
2 散列映射表：HashMap
散列映射表主要用到散列技术，可以快速对一个元素进行查找。HashMap类中的主要域如下：
transient Node<K,V>[] table; transient int size; int threshold; final float loadFactor;其中使用table来存储元素，size表示映射表中键值对的个数，threshold是一个域值，当元素个数超过这个域值后，就会自动扩展映射表的大小。而loadFactor是一个加载因子，表示threshold与table长度的比值。
可以看到，table是一个数组，数组中存储Node<K,V>类型的值。Node<K,V>表示一个键值对，定义如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey();
public final V getValue();
public final String toString();
public final int hashCode();
public final V setValue(V newValue);
public final boolean equals(Object o);
}是一个静态内部类，这表示一个键值对，可见HashMap将键值对作为一个整体来操作。
在Node中，有存储键的key，存储值的value，存储散列值的hash，还有一个next引用，可见这是一个链表。
既然有散列值hash，那么这个值是如何计算的呢？方法如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}是一个纯粹的数学方式。
有了散列值，HashMap又是如何散列的呢？
HashMap使用hash值确定一个键值对在table中的位置，具体方法是，用hash%table.length，结果就是在table中的下标。如果有多个hash在table中的同一个位置，那么就构成一个链表。存储方式大致是这样的：
在HashMap中，table的默认大小是16，以后每次扩大容量都会是原来的二倍，因此，table的大小一直是2的幂。由于这点，HashMap在计算一个hash的位置的时候，使用了非常巧妙的方法：
int n=table.length; int index=hash&(n-1);这就相当于计算hash%table.length。
了解了键值对的表示方式和HashMap的存储方式之后，就要对键值对进行操作了。常见的操作有查找、插入和删除。接下来就介绍这些操作：
（1）查找
HashMap中，对于查找操作，定义了一个私有方法getNode。这个方法有两个参数：hash和key，根据哈希值和键来找键值对。定义如下：
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;
}首先根据hash定位键值对在table中的位置，找到之后首先检查第一个元素，如果符合就返回，如果不符合就遍历这个链表，知道找到符合的键值对。如果没有找到，说明没有这个键值对，返回null。
这个方法是查找操作的基本方法，HashMap中的查找方法比如containsKey等都是调用这个方法完成操作的。
（2）添加键值对
HashMap中定义了一个基本方法putVal，这个方法将给定的键和值加入映射表中，定义如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果表为空，即里面没有元素，则使用resize方法创建一个表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//找到给定的键值对对应的位置，如果对应位置还没有元素，则创建一个Node作为链表的头
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//对应的位置已经有元素了，即发生了冲突，那么就在后面形成一个链表
else {
Node<K,V> e; K k;
//待插入的键与已有的键相同，则更新值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//在链表中找合适的位置（要么有已存在的键，要么没有）
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//更新值，并返回旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
添加操作和查找操作有点类似，首先定位待插入的键值对在table中的位置，如果里面没有元素，直接插入即可；如果里面已经有元素，即发生了冲突，就将这个元素加入到这个链表中。
put方法就是调用这个方法的。
（3）删除键值对
有加入操作就有删除操作。基本方法是removeNode：
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
首先也是定位到节点的位置，matchValue是是否匹配值，如果为true，就是说只有值也匹配的时候才删除这个键值对。HashMap中的remove方法就是调用这个方法。
（4）容量扩展
当当前元素个数size等于threshold时，即使没有达到table的容量，也需要对table进行扩展。HashMap中的resize方法完成这个操作。
这个方法比较复杂，方法分为两部分，第一个部分就是确定新映射表的大小，考虑的主要问题是数值溢出。因为默认的大小是16，每次扩容都会是原来的2倍，很容易溢出。当发生这种情况时，就将threshold值置为Integer.MAX_VALUE。
第二个部分就是将原来映射表里的内容移到新的映射表中。这只需要两层循环就好。第一层循环是在table数组上，第二层是每个table元素也是一个链表，需要循环一次。然后把每个键值对放在新的映射表中的合适位置即可。
以上就是一些基本的操作，HashMap的修删改查方法都是基于这些方法实现的。
接下来就是HashMap的视图（view）操作。
（1）键集：keySet
方法keySet可以返回一个由键构成的集，注意KeySet既不是HashSet，也不是TreeSet，而是扩展了AbstractSet抽象类的一个内部类：
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}这个类实现了Set接口，也是一个Collection，因此可以与使用任何集合一样使用keySet。
比如，可以枚举映射表中的所有键：
Set<String> keys=map.keySet();
for(String key:keys)
{
do something with key
}（2）值集合：values
values方法返回一个由值构成的集合，注意不是集，因为HashMap仅要求键唯一，不需要值唯一。返回的这个集合是扩展了AbstractCollection类的一个内部类：
final class Values extends AbstractCollection<V>（3）键值对集合：entrySet
这个方法返回由所有键值对构成的集合。这个方法返回的集是扩展了AbstractSet类的内部类：
final class EntrySet extends AbstractSet<Map.Entry<K,V>>这样，就可以同时查看键和值了，以避免对值进行查找：
for(Map.Entry<String,Employee> entry:staff.entrySet())
{
String key=entry.getKey();
Employee value=entry.getValue();
dosomething with key,value
}下面的代码演示了映射表的操作过程。首先将键值对添加到映射表中。然后，从映射表中删除一个键，同时与之对应的值也别删除了。接下来，修改与某一个键对应的值，并调用get方法获得这个值。最后，对元素进行迭代：
import java.util.*;
public class MapTest
{
public static void main(String[] args)
{
Map<String, Employee> staff = new HashMap<>();
staff.put("144-25-5464", new Employee("Amy Lee"));
staff.put("567-24-2546", new Employee("Harry Hacker"));
staff.put("157-62-7935", new Employee("Gary Cooper"));
staff.put("456-62-5527", new Employee("Francesca Cruz"));
// print all entries
System.out.println(staff);
// remove an entry
staff.remove("567-24-2546");
// replace an entry
staff.put("456-62-5527", new Employee("Francesca Miller"));
// look up a value
System.out.println(staff.get("157-62-7935"));
// iterate through all entries
for (Map.Entry<String, Employee> entry : staff.entrySet())
{
String key = entry.getKey();
Employee value = entry.getValue();
System.out.println("key=" + key + ", value=" + value);
}
}
}
结果如下：
当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。
掌握了上面知识之后，我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值；如果程序比较关心空间开销、内存比较紧张，可以适当地增加负载因子；如果程序比较关心时间开销，内存比较宽裕则可以适当的减少负载因子。通常情况下，程序员无需改变负载因子的值。
如果开始就知道 HashMap 会保存多个 key-value 对，可以在创建时就使用较大的初始化容量，如果 HashMap 中 Entry 的数量一直不会超过极限容量（capacity * load factor），HashMap 就无需调用 resize() 方法重新分配 table 数组，从而保证较好的性能。当然，开始就将初始容量设置太高可能会浪费空间（系统需要创建一个长度为 capacity 的 Entry 数组），因此创建 HashMap 时初始化容量设置也需要小心对待。
3 树映射表：TreeMap
TreeMap用键的整体顺序对元素进行排序，底层使用红黑树实现。迭代时，会按照顺序迭代。
下面的代码演示了TreeMap的使用。这里使用的是默认的比较器：
public class MapTest
{
public static void main(String[] args)
{
Map<String, Employee> staff = new TreeMap<>();
staff.put("144-25-5464", new Employee("Amy Lee",9000));
staff.put("567-24-2546", new Employee("Harry Hacker",5000));
staff.put("157-62-7935", new Employee("Gary Cooper",7500));
staff.put("456-62-5527", new Employee("Francesca Cruz",8000));
for(Map.Entry<String,Employee> entry:staff.entrySet()){
String key = entry.getKey();
Employee value = entry.getValue();
System.out.println("key=" + key + ", value=" + value);
}
}
}结果如下：
TreeMap在构造时还可以指定一个比较器，根据比较器对键进行排序：
public class MapTest
{
public static void main(String[] args)
{
Map<String, Employee> staff = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
});
staff.put("144-25-5464", new Employee("Amy Lee",9000));
staff.put("567-24-2546", new Employee("Harry Hacker",5000));
staff.put("157-62-7935", new Employee("Gary Cooper",7500));
staff.put("456-62-5527", new Employee("Francesca Cruz",8000));
for(Map.Entry<String,Employee> entry:staff.entrySet()){
String key = entry.getKey();
Employee value = entry.getValue();
System.out.println("key=" + key + ", value=" + value);
}
}
}
这里构造一个比较器，使得按照键反向排列。结果如下：
注意，TreeMap只能对键进行排序，不能对与键关联的值进行排序。