HashMap源码解析——概述

HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

　　值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。
　　

 Map map = Collections.synchronizedMap(new HashMap());

　　HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。

图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

我们看看HashMap中Entry类的代码：

/** Entry是单向链表。 
 * 它是 “HashMap链式存储法”对应的链表。 
 *它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数 
 **/  
    static class Entry implements Map.Entry {    
        final K key;    
        V value;    
        // 指向下一个节点 
        Entry next;    
        final int hash;    

        // 构造函数。 
        // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" 
        Entry(int h, K k, V v, Entry n) {    
            value = v;    
            next = n;    
            key = k;    
            hash = h;    
        }    

        public final K getKey() {    
            return key;    
        }    

        public final V getValue() {    
            return value;    
        }    

        public final V setValue(V newValue) {    
            V oldValue = value;    
            value = newValue;    
            return oldValue;    
        }    

        // 判断两个Entry是否相等 
        // 若两个Entry的“key”和“value”都相等，则返回true。 
        // 否则，返回false 
        public final boolean equals(Object o) {    
            if (!(o instanceof Map.Entry))    
                return false;    
            Map.Entry e = (Map.Entry)o;    
            Object k1 = getKey();    
            Object k2 = e.getKey();    
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {    
                Object v1 = getValue();    
                Object v2 = e.getValue();    
                if (v1 == v2 || (v1 != null && v1.equals(v2)))    
                    return true;    
            }    
            return false;    
        }    

        // 实现hashCode() 
        public final int hashCode() {    
            return (key==null   ? 0 : key.hashCode()) ^    
                   (value==null ? 0 : value.hashCode());    
        }    

        public final String toString() {    
            return getKey() + "=" + getValue();    
        }    

        // 当向HashMap中添加元素时，绘调用recordAccess()。 
        // 这里不做任何处理 
        void recordAccess(HashMap m) {    
        }    

        // 当从HashMap中删除元素时，绘调用recordRemoval()。 
        // 这里不做任何处理 
        void recordRemoval(HashMap m) {    
        }    
    }

HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。