HashMap的源码与结构分析

1. Map结构

Map是一种维护键-值对的映射表的结构，可以通过键来查找到对应的值。如下的代码就是利用二维数组实现的键-值映射表。

public class SimpleMap<K, V> {
    private Object[][] pairs;
    private int index;

    public SimpleMap(int length) {
        pairs = new Object[length][2];
    }

    public void put(K key, V value) {
        if (index >= pairs.length) {
            throw new ArrayIndexOutOfBoundsException();
        }

        for (int i = 0; i < index; i++) {
            if (key.equals(pairs[index][0])) {
                pairs[index] = new Object[]{key, value};
                return;
            }
        }

        pairs[index++] = new Object[]{key, value};
    }

    public V get(K key) {
        for (int i = 0; i < index; i++) {
            if (key.equals(pairs[index][0])) {
                return (V) pairs[index][0];
            }
        }

        return null;
    }
}

由于没有规律的存储键-值对，导致在查找某个键的值时，需要遍历整个整个映射表来找到对应键的值，效率非常低，而且该映射表的容量是一次性申请的，存在越界的异常。所以HashMap为了解决查找性能的问题，利用散列函数生成散列码来提高查找性能。

2. HashMap的源码分析

2.1 HashMap的相关名词

首先看一下源码中一些变量的定义：

  • size
    表示HashMap中存放的数量(链表及红黑树上结点的总和)

  • bin
    表示桶后面存放的每一个数据node 称为bin

  • DEFAULT_INITIAL_CAPACITY = 1 << 4
    初始容量，最初为16，也被称为桶的数量。每次扩容都会增加一倍。且必须为2的幂。

  • MAXIMUM_CAPACITY = 1 << 30
    扩容的最大容量

  • DEFAULT_LOAD_FACTOR = 0.75f
    装载因子，对应变量loadFactor. 意思是指当size ／ Capcity > 0.75 时，需要执行resize来扩容。

  • TREEIFY_THRESHOLD = 8
    当某一个桶后面的链表的bin的数量超过THEEIFY_THRESHOLD时，就会将链表优化成红黑树。

  • UNTREEIFY_THRESHOLD = 6
    当某一个桶后面的红黑树的bin的数量低于UNTREEIFY_THRESHOLD时，就会将红黑树退化成链表结构。

  • MIN_TREEIFY_CAPACITY = 64
    如果当某个桶链接的结构从链表转换成红黑树时，此时的capacity < MIN_TREEIFY_CAPACITY，说明哈希冲突严重，此时不进行树化，而是采取扩容resize操作。

  • threshold
    阈值，表示当hashMap存的键-值对数量 大于threshold时会执行resize操作。

2.2 HashMap的结构

HashMap内部实现的数据结构是数组+链表＋红黑树实现的。
在hashMap中，实际存储的结点bin也就是如下的node结构，这是典型的链表的node结构，里面有一个索引next，存储着下一个哈希冲突值的node。HashMap在JDK 1.7 中处理哈希冲突的方法是拉链法，但由于冲突过多时，此时查找的时间复杂度又会增加到O(n), 于是在JDK 1.8中，进行了链表到红黑树(自平衡二叉查找树)的优化，查找时间复杂度从O(n) 优化到O(logn)。

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

transient Node<K,V>[] table;

那么数组和链表以及红黑树如何组织工作呢？
某个对象的key 计算出来的hash值，对数组的数量（桶的数量）进行模运算，得到的数据就
是在哪个桶的下标index，如果该index结点，说明发生了哈希冲突，遍历该链表，如果出现hash相同且key值相同，则将结点替换；如果在遍历的过程中，发现bin的数量大于TREEIFY_THRESHOLD时，则进行树化操作，否则挂到链表的最后一个结点上。

接下来具体分析一下源码中的put()，get()，resize 方法。

2.3 put方法

通过源码可知，put()方法最终会走到putVal()方法

我们在源码中看构造函数，发现并没有给hashMap分配桶的数量，而是在put操作时，发现桶的数量为0时，才进行了第一次的扩容操作。

    if ((p = tab[i = (n - 1) & hash]) == null) {
        tab[i] = newNode(hash, key, value, null);
     }

这段逻辑判断中有一个位运算：(n-1) & hash， 这相当于hash % n 的操作，这样提高了效率，同时也是为什么容量capacity为什么一定要为2的幂的原因。当这个桶的结点为null时，直接将当前的结点赋值给tab[i]，且这个结点的next 为空。

  if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) 
      e = p;

否则的话，如果头结点的哈希值等于当前结点的哈希值，且key值相等时，将头结点替换成当前结点。在这里也可以看出，如果以某个对象作为key值的时候，需要重写equals方法。

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;
           }
       }

如果以上都不符合，则对链表进行遍历，如果遍历的过程中发现某一个结点hash和key都相等的情况，则直接break;
如果遍历到最后都没有发现hash 和 key都相等的情况，则将该结点挂在链表的最后一个结点。

    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();

这段代码第一个if说明在上面的遍历过程中，找到了hash和key值相同的结点，则直接用新的value赋值给旧的结点即可。
另外如果size(插入的总结点树) 超过threshold则进行扩容。

2.4 get 方法

从下面的代码可以看出，get方法是找到key对应的node，然后返回该node的value.

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

那么具体的getNode是如何通过找到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;
    }

首先通过key计算出hash值，将hash值对桶的数量求模，找到该key对应的桶。首先从头结点开始遍历，如果头结点的hash和key都相等，则直接返回头结点。否则进行遍历，如果结点属于树结点，则通过((TreeNode<K,V>)first).getTreeNode(hash, key); 找到结点，否则就遍历链表找到hash和key相等的结点。

2.5 resize方法

当桶的大小不符合期望时，就会出现那大小不符合期望的情况有哪几种呢？

  1. 当 s > threshold: 总bin的数量超过了阈值。
  2. 当 (n = tab.length) < MIN_TREEIFY_CAPACITY：当某个桶的链表数量大于TREEIFY_THRESHOLD时，需要进行链表转红黑树的优化，若此时桶的数量小于最小树化数(MIN_TREEIFY_CAPACITY)， 则说明是由于桶的数量太小导致的哈希冲突太多，此时应该做扩容优化，而非进行链表转红黑树。
  3. 当 if ((tab = table) == null || (n = tab.length) == 0)： 第一次put数据时，桶的数量为0，则进行扩容初始化。

扩容操作除了将容量扩大一倍外，重要的是将原桶的数据移到扩容之后桶上。

if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }

遍历这个map的所有桶

  1. 如果某个桶只有头结点，将这个结点的hash值对扩容后桶的数量求模找到新的下标。

  2. 否则如果这个结点属于红黑树的某个孩子，那么执行树的split

  3. 如果都不属于上述两种情况，就是桶的链表的结点了。代码中的do{}while()模块就是遍历链表的结点操作，在do{}代码块中，又有两个逻辑分支：
    a. if ((e.hash & oldCap) == 0), 该条件说明新的下标不需要动，那么这些结点就挂在指针loHead上，这里注意需要注意是对oldCap进行位与运算，而不是oldCap-1， 如果是oldCap-1, 则等效于e.hash % oldCap 。
    b. 否则的话说明该结点在扩容后的map中的桶的下标发生了变化，就会挂到指针hiTail上。

  4. 通过第三步指针的变换后，就会产生两个链表，头结点分别为loHead、hiHead. 其中loHead指的链表为扩容后的桶的下标值和原有值一致，hiHead指的是链表扩容后桶的下标值和原有值发生了变化，具体变化为oldIndex + oldCap。 这种优化的特性是因为map的容量是2的幂，如果不是2的幂，则无法使用。这里可以用位运算进行模拟，就会发现之前的结点，要不在oldIndex上，要么就会在oldIndex + oldCap上，不会出现第三种情况。

如图所示：


扩容前

其中(0, aa)第一个0 指的是key的hash值. aa指的是这个结点的值。桶的capcity ＝ 16。 扩容之后桶的容量为32,

那么之前的结点如何变化到扩容后的map上呢？

扩容后

可以看到结点(16,bb) 被挂到了(0 + 16)=16的索引上，(17，BB)原来挂在1位置上，现在挂在了(1+16)=17号位上。

2.6 resize()问题

由于hashMap是线程不安全的，所以如果多个线程共享一个hashMap的时候，就有可能出现A线程检测到需要扩容准备扩容，而B线程正在执行扩容操作的问题，对于多线程使用hashMap的情况，我们可以用数据结构CocurrentHashMap来替换hashMap

3. 自定义类作为key

因为hashMap 是利用hashcode()计算出hash值，然后用该hash值对桶的数量求模来进行索引存储的，取数据则是通过判断hash值和key值都相等找到对应的结点，然后返回该结点的value， 而比较key值，正是用的该类的equals方法。所以当用自定义类作为key值时，需要重写hashCode()和equals方法，如果不重写的话，就会调用Object类的hashCode和equals方法，而Object类的hashCode()方法是使用这个对象的内存地址计算哈希码的，而equals方法则只是比较这两个对象的内存地址是否相等。而一个好的hash算法决定了这个hashMap的哈希分布的均匀性。在<Think in JAVA>中，给出了hashCode()方法的基本算法：

  1. 给int 变量result 赋予某个非零值常量，例如17

2）为对象内每个有意义的域f（即每个可以做equals()操作的域）计算出一个int散列码c（见下表）

3）合并计算的到的散列码 result = 37 * result + c

4）返回result

  1. 检查hashCode()最后生成的结果，确保相同的对象有相同的散列码
属性名 说明
boolean c=(f?0:1)
byte,char,short或int c=(int)f
long c=(int)(f^(f>>>32))
float c=Float.floatToIntBits(f)
double long l = Double.doubleToLongBits(f) c = (int)(l^(l>>>32))
Object其equals()调用这个域的equals() c = f.hashCode()
数组 对每个元素应用上述规则

如下就是自定义类作为key的例子。

/**
 * hashcode的生成
 * @Desc: created by taohuahua on 2019-04-05
 */
public class CustomKey {

    private String str;
    private int id = 0;

    public CustomKey(String str, int id) {
        this.str = str;
        this.id = id;
    }

    public String toString() {
        return "string: " + str + " id == " + id + " hashCode(): " + hashCode();
    }

    /**
     * @return
     */
    public int hashCode() {
        int result = 17;
        result = 37 * result + str.hashCode();
        result = 37 * result + id;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof CustomKey && str.equals(((CustomKey)obj).str)
                && id == (((CustomKey)obj).id);
    }
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 好好学习
    听了猫叔的分享，醍醐灌顶，发现自己的学习是场假的学习。怎样才是好好的学习呢，请听我细细道来。 一、利用碎片化时间学...
    夕米可可阅读 1,652评论 0赞 0
  • 别离 五
    高考那几天，接二连三的暴雨像是上帝不甘的泄愤，毫无预兆的暴雨似乎已不是什么奇怪的事，李猜经常坐在窗前，看着窗外的倾...
    叛荼s阅读 2,854评论 2赞 1
  • 熊头老二（二）
    出村的路穿过一片高粱地。秋天了，高粱穗子沉甸甸的饱满起来。 算命先生气哼哼地走来，心里不静更让他走的深一脚浅一脚。...
    夏书江阅读 1,733评论 0赞 0
  • 2017-07-29
    http://www.jianshu.com/p/4a89d02f316f?from=timeline&isapp...
    乡野汇农资技术服务站阅读 1,517评论 0赞 0

友情链接更多精彩内容