HashMap的继承结构
Java中，我们最常用的map类型可能就是HashMap了，这一次介绍的重点也在HashMap上面。但是，在我们详细分析HashMap之前，我们先来看一下HashMap的继承结构：
Java中的Map接口
从上面的继承结构中，可以看出，Java中的HashMap是接口Map的一个实现类，因此，在我们分析HashMap之前，不妨先来看看Map接口。
首先，我们来看一下Map中定义的方法：
可以看到，我们常用的方法，如get、set、size、isEmpty、remove、keySet、entrySet等，在map接口中都有定义，因此我们无论使用map接口的哪个具体实现类，都可以使用这个方法。
同时，注意到Map接口中还有着一个内部类的接口Entry，那么我们再来看看这个内部类的接口中定义了哪些方法吧
从Entry的接口方法中可以看到，我们对于Entry的常用的方法，在这里也都有定义。
AbstractMap类
除了实现了Map的接口外，Java中的Map的具体类多数还继承了一个叫做AbstractMap的抽象类，这个抽象类是Java中为了实现Map所写的一个便利类，其中已经实现了很多Map所需的方法，也就是说如果我们需要其它的一个具体类，只需要完成抽象类AbstractMap中所没有实现的方法即可（当然，也可以重写已实现的方法来实现具体的功能）。
我们先来看一下AbstractMap中实现的方法：
这些方法都是已经有具体实现的方法，这里把其中一些常见的方法的实现贴出来：
public abstract class AbstractMap<K,V> implements Map<K,V> {
transient Set<K> keySet;
transient Collection<V> values;
protected AbstractMap() {
}
public int size() {
return entrySet().size();
}
public boolean isEmpty() {
return size() == 0;
}
以上几个方法的实现都比较简单，需要注意的是，entrySet()方法在这个抽象类中并没有实现。
public boolean containsValue(Object value) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (value==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}
public boolean containsKey(Object key) {
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return true;
}
}
return false;
}
以上两个分别判断是否包含键与值的方法，都是依赖迭代器来实现，实现方法比较安全，但是这种依赖遍历的方式效率是比较低的。
public V get(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}
// 并没有实现
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}
以上三个为get、put、remove方法，get函数与上面的两个判断函数相同，都是依赖通过迭代器来遍历的方式实现的，安全但是效率较低。接下来的put方法并没有进行实现，如果调用到了这个方法（如其具体实现类也没有实现这个方法），会抛出一个异常。最后，remove的实现与get相同，先通过迭代器的遍历找到要删除的键所对应的值，最后依赖迭代器的remove来实现删除，并将刚刚找到的值返回。
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
public void clear() {
entrySet().clear();
}
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new AbstractSet<K>() {
public Iterator<K> iterator() {
return new Iterator<K>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
keySet = ks;
}
return ks;
}
public Collection<V> values() {
Collection<V> vals = values;
if (vals == null) {
vals = new AbstractCollection<V>() {
public Iterator<V> iterator() {
return new Iterator<V>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public V next() {
return i.next().getValue();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object v) {
return AbstractMap.this.containsValue(v);
}
};
values = vals;
}
return vals;
}
public abstract Set<Entry<K,V>> entrySet();
这里，putAll是依赖这个抽象类里并没有实现的put方法来实现，clear是依赖同样没有实现的entrySet方法来实现，接下来的ketSet与values方法都是通过新建一个扩展了抽象类（AbstractSet与AbstractCollection）的类的对象，之后将属性输入到属性，再返回这个对象的方法来实现的。最后一个，entrySet方法，emmmm，前面有很多方法都是依赖这个方法的返回值来进行的，但是这个方法再这个抽象类里是没有被实现的。
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map<?,?> m = (Map<?,?>) o;
if (m.size() != size())
return false;
try {
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(m.get(key)==null && m.containsKey(key)))
return false;
} else {
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}
一个重头戏，equals方法，这个方法在HashMap中也是需要重点关注的方法，这里，我们先看一下AbstractMap中的判断相等的方法是怎样写的吧。
首先，对于输入的对象o，判断其地址与当前对象（this）是否相同，若是，则返回true，否则继续判断，是否为Map接口的实现类的对象，若是则继续，将其类型强制转换为Map类型，然后比较两者的size是否一致。通过以上几个非常快的判断，已经可以以很高的效率，将大部分的不相等的对象返回正确的false的结果了。
在以上判断全都通过的情况下，接下来，和前面的很多方法一样，接下来，会通过引入entrySet来进行判断（嗯，就是通过前面所说的还没有实现的entrySet()方法来得到所需的entrySet），在得到entrySet后，通过entrySet的迭代器来得到每个entry的键和值，先判断o中是否包含这个键，若包含，则通过这个键得到o中所对应的值，判断entry中的值与这个值是否相等，若相等，则继续通过迭代器得到下一个值，继续判断，若不相等，则返回false。若遍历完所有的元素，没有不一样的元素，则返回true，说明两个map完全相同。
public int hashCode() {
int h = 0;
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
}
public String toString() {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (! i.hasNext())
return "{}";
StringBuilder sb = new StringBuilder();
sb.append('{');
for (;;) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
sb.append(key == this ? "(this Map)" : key);
sb.append('=');
sb.append(value == this ? "(this Map)" : value);
if (! i.hasNext())
return sb.append('}').toString();
sb.append(',').append(' ');
}
}
protected Object clone() throws CloneNotSupportedException {
AbstractMap<?,?> result = (AbstractMap<?,?>)super.clone();
result.keySet = null;
result.values = null;
return result;
}
最后，就是我们很多自己写的类也会实现的一些方法了，如’toString()'方法，描述了应该怎样输出这个map，clone则会调用Object中的clone方法，实则需要实现类来实现。而hashCode()方法，则是一次得到每一个entry的hashcode`，再将其全部加起来作为自己的hashcode。
总结
至此，我们便将HashMap所实现的Map接口，与所继承的AbstractMap抽象类都详细地看过了，以这些为基础，接下来，我们就可以来看我们所需重点关注的HashMap类了。
