java HashMap 实现原理

在java语言编程中，我们经常会遇到成对出现的数据，比如 姓名和年龄，书籍名称和出版社。这些数据都是key和value的形式组织在一起。
一般我们会使用Map这种数据结构来存储这些数据，你可以看成一个二维的数组。接下来，我会讲讲java中和HashMap相关的几个类和接口，帮助和学习理解HashMap这种结构。

[warning]Map.java[/warning]
Map在java中所有Map实现类的总接口。他定义了所有Map所具备的基本的set put containsKey remove等方法，且存在一个内部的子接口Entry，每一组k-v都是这个Entry的实例，说白了就是put操作，会在Map内部new一个Entry，然后k-v都会塞到这个Entry实例中。

[warning]AbstractMap.java[/warning]
java中还存在了一个Map接口的抽象实现类AbstractMap。

public abstract class AbstractMap<K,V> implements Map<K,V> {...}

如其名是个抽象类，其实现了Map接口中声明的方法，包括containsValue get put等方法，且实现了Map.Entry接口。
AbstractMap类中内部维护了一个set结构用于维护数据，我们都知道set是无序的，所以也导致了大部分map里的数据也是无序的。当然这个set也是抽象的，并没有说明具体的实现。
public abstract Set<Entry<K,V>> entrySet()
举例一下这个AbstractMap的get方法，get方法使用了非常粗暴的迭代循环找到对应的数据，时间复杂度和空闲复杂度都是O(n),如果数据量比较大且查询比较多的情况下，效率比较低下。

public V get(Object key) {
       Iterator> i = entrySet().iterator();
       // map中key可以是null null值用==null判断
       if (key==null) {
           while (i.hasNext()) {
               Entry e = i.next();
               if (e.getKey()==null)
                   return e.getValue();
           }
       } else {
           while (i.hasNext()) {
               Entry e = i.next();
               // 非空的key 用equals判断
               if (key.equals(e.getKey()))
                   return e.getValue();
           }
       }
       return null;
   }

[warning]HashMap.java[/warning]
而现在要说的HashMap类继承于AbstractMap，实现了Map接口。AbstractMap已经帮我们实现了大部分map里的操作。

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
}

既然名字都带了Hash，那么这个实现类肯定和Hash值密切相关，那么一般一个对象的hash值都是通过Object.hashcode()方法获取的，当然你也可以重写，然后还有一个很重要的方法equals方法。一般这2个是成对出现的，否则出现2个对象hashcode一致，equals返回false的情况就尴尬了。这到底是不是同一个对象？
之前提到AbstractMap类中的数据都存放到了Set中，因为set的无序性，导致我们找一个value非常麻烦，必须循环遍历。那么有没有什么办法，提高查找效率、回顾一下java的基础知识，论查找效率最基本的数组肯定是最快的，直接通过下标查找，复杂度都是（1）。那么我们能不能把这个Set替换成数组[].HashMap就是这么干的！

  transient Node<K,V>[] table;

Node类是HashMap的子类，对应Map.Entry接口。数据都存到了一个数组里。这样就会有一个问题，我怎么知道key对应的数组下标？我怎么从数组里拿到我想要的数据？
这个时候hash算法就出场了,hashmap里有一套算法通过对key的hash计算获取这个key对应在数组里的坐标。
那么一个get操作就变成了如下步骤

key->hash(key)->index->get(index)

当然简单的hashcode是无法转换成index的。
Object对hashcode方法的方法定义如下

public native int hashCode();

它返回的是一个int,这个int的值肯定大于数组的长度，那么怎么才能让这个int转换成合法的下标呢？

hashcode(key)%array.length

是不是很简单？循环数组就是这么实现的，直接首尾相连。
HashMap中获取hash的实现如下,我们看到获取的hash值不仅仅调用了hashcode还继续执行了位运算。
这样做的好处是，可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。掺杂的元素多了，那么生成的hash值的随机性会增大。

   static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

但这又出现了一个新的问题，一个数组的长度就这么点，hash值可能会不会重复，转换成下标的时候就很有可能了。
相同下标的k-v怎么存？非常简单，我们回顾下HashMap中定义的k-v容器 Node。

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
    }

我们发现node里不仅存放了 key 和value，还存放了对应的hash值，以及一个Node实例，名字叫next。意思很明白了，如果hash出来的下标重复了，出现了冲突，那么当前索引位置的node就会set一下这个next，这个next就是新put的k-v。
也就是说，出现冲突的时候，新put的键值对和原本就存在的键值对构成一个链表。Node中的next存放了下一个node的引用。

另外如果map中存入了非常多的键值对，那么数组中会存在很多的hash冲突（重复的hash值），所以会出现很多很长的链表，用于存放相同索引位置的键值对。
又又所以，hashmap对此，做了优化。数据量比较小的时候，用链表存放这些冲突的数据，数据量大的时候，优化成了红黑树，提高查找效率。这个阈值由变量TREEIFY_THRESHOLD决定，默认值是8;
红黑树的结构定义为hashmap的子类TreeNode

static final class TreeNode=<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    }

这颗红黑树的查找算法定义如下

final TreeNode find(int h, Object k, Class kc) {
    TreeNode p = this;
    do {
         int ph, dir; K pk;
         TreeNode pl = p.left, pr = p.right, q;
         if ((ph = p.hash) > h)
             p = pl;
         else if (ph < h)
             p = pr;
         else if ((pk = p.key) == k || (k != null && k.equals(pk)))
             return p;
         else if (pl == null)
             p = pr;
         else if (pr == null)
             p = pl;
         else if ((kc != null ||
                   (kc = comparableClassFor(k)) != null) &&
                  (dir = compareComparables(kc, k, pk)) != 0)
             p = (dir < 0) ? pl : pr;
         else if ((q = pr.find(h, k, kc)) != null)
             return q;
         else
             p = pl;
     } while (p != null);
     return null;
 }

未完待续。。。