一.哈希表

　　本文首先介绍一下哈希表，因为要解析HashMap，理解其内部结构以及原理，不得不提到哈希表。

　　哈希表是根据关键值key直接进行数据访问的数据结构，其本质是一个数组，数组的每一个元素为一个“桶”，桶中存放键值对。其存储过程是根据每个数据通过哈希函数计算的哈希值决定其存放的桶的下标。若桶中存在键值对，则使用寻址法或链地址法解决冲突。

　　这里提到的哈希函数，也称为散列函数，具有以下几个特点：

• 输入域无限大，输出域有限大。即给定任意长度的输入，通过算法，得到等长的输出。
• 不包含任何随机的东西，输入相同时输出一定相同。
• 不同的输入可能导致相同的输出（称为哈希碰撞，概率极低）。
• 大量的输入出现时，对于输出域中每个点的厚度而言是均匀变厚的（厚度：重复率），体现了哈希函数最重要的性质：

  均匀性。

　　经常使用的MD5算法就是一种哈希函数。

　　在哈希表中，数据的key值通过hash函数得到hash值，hash值mod哈希表的长度（即桶的个数）得到的值就存放的桶的下标，范围为0～桶的个数-1，在HashMap中，使用链地址法解决冲突，所以，桶中存放的就是键值对的链表，下面是网上找的一张图。

　　在哈希表中还有一个重要的概念——负载因子，主要是衡量哈希表的空满程度。

　　负载因子=总的键值对的个数/桶的个数

　　负载因子越大，代表哈希表越满，每个桶中的链表越长，更容易导致冲突，性能越差，此时哈希表将自动扩容。

　　哈希表每次扩容，一般将桶的个数增加至之前的两倍，由于桶的数量增加，则需重新计算所有数据的哈希值，mod新的哈希表的长度，得到新的桶的地址，重新挂链，由此可见，扩容的代价是全量的，但是，扩容后的哈希表的每个桶的链的长度基本是之前的一半，所以说扩容后，很久都不需要扩容（除非有极端情况，数据的key计算出的哈希值都一样，扩容后位置不变），同时在java8的HashMap中，引入了红黑树，使HashMap的性能更高。

二.HashMap源码分析

　　HashMap底层基于哈希表实现，使用链地址法，java8中引入了红黑树优化过长链表，HashMap允许NALL键与NALL值，数据无序，线程不安全，多线程下可能会出现问题。

　　1.Entry与构造方法

　　Entry是Map的一个内部接口，在HashMap中提供了其实现，Entry用于存储键值对以及维护链式结构，其具体实现(部分)如下。

static class Node
     
       implements Map.Entry
      
        {        final int hash;　　//　　key的哈希值        final K key;　　　　        V value;        Node
       
         next;　　//维护链表，指向下一节点        ...    }
       
      
     

　　HashMap的底层就是一个Entry数组

transient Node
     
      [] table;
     

　　HashMap有4个构造方法，最主要的构造方法如下，其他构造方法基于该构造方法实现。

public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        this.loadFactor = loadFactor;        this.threshold = tableSizeFor(initialCapacity);    }

　　可以看出，构造方法主要用于初始化三个变量分别是 HashMap初始容量initialCapacity、负载因子loadFactor以及阈值threshold。

　　初始容量不难理解，就是哈希表的长度，负载因子已经提到过，主要是用来判定哈希表的空满程度，阈值为哈希表所能容纳最多的键值对的个数，键值对个数超过阈值则需扩容，初始阈值由初始容量经过位运算得出。默认情况下初始容量为16，负载因子为0.75，相关代码如下。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final float DEFAULT_LOAD_FACTOR = 0.75f;

　　

　　2.查找

　　HashMap查找步骤同哈希表存储数据的原理一致，首先计算key的哈希值， mod哈希表长度得到桶的下标，然后遍历桶中的链表。get方法如下。

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

　　查找的核心为getNode方法，其实现以及解析如下。

final Node
     
       getNode(int hash, Object key) {        Node
      
       [] tab; Node
       
         first, e; int n; K k; 　　　　 //根据key的哈希值确定桶的下标，得到桶中链表第一个节点的引用first        if ((tab = table) != null && (n = tab.length) > 0 &&            (first = tab[(n - 1) & hash]) != null) {
    　　　　　　　　//判断first是否为查找的节点，如果是则返回            if (first.hash == hash && // always check first node                ((k = first.key) == key || (key != null && key.equals(k))))                return first; 　　　　　　　　//first并非查找的节点，判断是否还有下一个节点，如果没有下一个节点，则查找元素不存在，返回NULL            if ((e = first.next) != null) {
    　　　　　　　　　　//存在下一个节点，判断桶中节点类型 　　　　　　　　　　//1.树形节点，使用红黑树查找方法                if (first instanceof TreeNode)                    return ((TreeNode
        
         )first).getTreeNode(hash, key); 　　　　　　　　　　//2.普通链表，遍历链表                do {                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        return e;                } while ((e = e.next) != null);            }        }        return null;    }
        
       
      
     

　　在源码中，通过(n - 1) & hash得到桶的位置，(n - 1) & hash等价于hash%n，也就是哈希值mod哈希表的长度。

　　

　　3.遍历

　　HashMap是无序的，这种无序体现在，不管键值对以什么样的顺序插入，遍历得到的顺序都是相同的，也就是说遍历的顺序与数据插入顺序无关，我们看一下HashMap中迭代器的源码。

abstract class HashIterator {        Node
     
       next;        // 下一个要返回的节点        Node
      
        current;     // 当前节点        int expectedModCount;  // 快速失败锁        int index;             // 当前桶的下标        HashIterator() {            expectedModCount = modCount;            Node
       
        [] t = table;            current = next = null;            index = 0;            if (t != null && size > 0) { // advance to first entry 　　　　　　　　　　//得到第一个包含键值对的桶                do {} while (index < t.length && (next = t[index++]) == null);            }        }        public final boolean hasNext() {            return next != null;        }        final Node
        
          nextNode() {            Node
         
          [] t;            Node
          
            e = next; 　　　　　　　　//快速失败机制 if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); 　　　　　　　　//判断当前桶中的链表是否已遍历结束 if ((next = (current = e).next) == null && (t = table) != null) { 　　　　　　　　　　//得到下一个包含键值对的桶 do {} while (index < t.length && (next = t[index++]) == null); } return e; } ... }
          
         
        
       
      
     

　　具体流程如下图。

　　

 

　　本文主要介绍了HashMap底层实现哈希表，分析了HashMap构造、查找以及遍历的源码，下一节将对HashMap插入以及扩容部分的源码进行介绍。