HashMap的底层实现

2019-01-02 阅读量

HashMap的底层实现相信是java开发者们面试都会碰到的问题。的确，它方便易用，在java开发中使用频率非常高。它的实现原理包含很多知识点，所以当面试官问到你HashMap的时候可就要当心了，因为如果基本功不够扎实的话，很容易被带到沟里哦，本文主要剖析HashMap的实现原理。首先搞清楚什么是HashMap，实际上从它的名字上就能明白大概。HashMap这个词可以分成两词，Hash和Map。其中Hash指哈希算法，Map则是映射。两个词组合在一起表示的通过哈希算法得到一个散列映射的集合，也就是一个Key对应一个Value的集合，先奉上HashMap的数据结构。

1.HashMap的实现

以下暂时说jdk1.8的HashMap实现，我们都知道在数据结构中，物理存储的数据结构只有两种，即数组和链表，其余的如树，队列，栈等数据结构都是在它们的基础上逻辑抽象而来。它们各有优势，数组存储区域连续，查找快，增删慢，而链表存储区域离散，查找慢，增删快，因此各有各的应用场景。并没有一种既满足查找快也满足增删快的基本数据结构。那能不能把数组和链表组合在一起构成一种新的数据结构呢？HashMap就此诞生了，它的底层就是通过数组加链表组合的方式实现了查找快和增删快的统一。那么怎么样的组合才能使两者达到平衡呢？下面我们来一探究竟，下图是HashMap实现的结构图。

从图中可以看出组成HashMap最基本的单元是Entry。图中红框的Entry构成数组，绿框中的Entry构成链表。当有新的Entry需要加入进来时，通过Entry的Key哈希后得到值和table数组的长度位与运算得到数组的下标。再遍历链表，通过equals方法逐个比较key，如果有相同的Key就覆盖,如果没有就追加到链表头部（HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历[tail traversing]）。数组和链表就是通过这种方式的组合实现了查找和增删效率的平衡。其中Entry对象除了包含本身的Key和Value外还包含它指向的下一个Entry。在jdk源码中Entry的实现类如下

  static class Node<K,V> implements Map.Entry<K,V> {
  	// key的哈希值
      final int hash;
      final K key;
      V value;
      // 下一个Node，没有则为null
      Node<K,V> next;

//省略下面代码
  }

在HashMap类中还定义了几个静态常量，这几个常量是一些很重要的属性，源码如下

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

	 /**
     * HashMap的默认初始容量大小 16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * HashMap的最大容量 2的30次方
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 负载因子，代表了table的填充度有多少，默认是0.75。当数组中的数据大于总长度的0.75倍时
     * HashMap会自动扩容，默认扩容到原长度的两倍。为什么是两倍，而不是1.5倍，或是3倍。这个
     * 2倍很睿智，后面会说到
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 默认阈值，当桶(bucket)上的链表长度大于这个值时会转成红黑树，put方法的代码里有用到
     * 在jdk1.7中链表就是普通的单向链表，很多数据出现哈希碰撞导致这些数据集中在某一个哈希桶上，
     * 因而导致链表很长，会出现效率问题，jdk1.8对此做了优化，默认当链表长度大于8时转化为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;
    
    /**
     * 和上一个的阈值相对的阈值，当桶(bucket)上的链表长度小于这个值时红黑树退化成链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    
    /**
     * 用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap      * 的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
     */
    transient int modCount;
    

}

HashMap有两个有参构造器可以用来设置initialCapacity和loadFactor的值，即HashMap的初始容量和负载因子的值，如果不传参则都使用默认值。

2.HashMap的几个重要方法

（1）put方法

废话不多说，直接上源码，下面所有方法我都加上了注释，以方便阅读理解

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

源码中put方法调用了putval方法，OK,接下来我们来看看putval操作的实现吧

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
			   
	//table全局变量,存储链表头节点数组
	Node<K,V>[] tab; Node<K,V> p; int n, i;
	
	//如果table数组是空的，则创建一个头结点数据，默认长度是16
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
		
	//n是table长度,根据数组长度和key的哈希值，定位当前key在table中的下标位置,如果为空则新建一个node。不为空走else
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	else {
		Node<K,V> e; K k;
		// 如果新的key与table中索引处取出的头节点的key相等，且hash值一致，则把新的node替换掉旧的node
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		//如果头节点不是空，且头节点的类型是树节点类型，则把当前节点插入当前头节点所在的树中(红黑树，防止链表过长，1.8的优化)
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		//map的数据结构处理
		else {
			//遍历链表
			for (int binCount = 0; ; ++binCount) {
				如果当前节点的下一个节点为空，则把新节点插入到下一个节点
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					//如果链表长度大于或等于8，则把链表转化为红黑树，重点转化方法(treeifyBin)
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
					//此方法构建红黑树
						treeifyBin(tab, hash);
					break;
				}
				//如果当前节点的key和hash均和待插入的节点相等，则退出循环，(注意此时e的值在前一个if时赋值过，因此当前的e值，就是链表中的当前节点值)
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		//如果老节点不是空，则将老节点的值替换为新值，并返回老的值
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			//此方法实现的逻辑,是把入参的节点放置在链表的尾部，但在HashMap中是空实现，在LinkedHashMap中有具体实现
			afterNodeAccess(e);
			return oldValue;
		}
	}
    //保证并发访问时，若HashMap内部结构发生变化，快速响应失败
	++modCount;
    //当table[]长度大于临界阈值，调用resize方法进行扩容
	if (++size > threshold)
		resize();
	//此方法在HashMap中是空方法，在LinkedHashMap中有实现
	afterNodeInsertion(evict);
	return null;
	}

(2) treeify方法构建红黑树

此方法中比较重要的方法就是treefyBin方法了，此方法以当前节点为头节点，构建一个双向链表(双向链表：链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

final void treeifyBin(Node<K,V>[] tab, int hash) {
	int n, index; Node<K,V> e;
	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
		resize();
	else if ((e = tab[index = (n - 1) & hash]) != null) {
		TreeNode<K,V> hd = null, tl = null;
		do {
			TreeNode<K,V> p = replacementTreeNode(e, null);
			if (tl == null)
				hd = p;
			else {
				p.prev = tl;
				tl.next = p;
			}
			tl = p;
		} while ((e = e.next) != null);
		if ((tab[index] = hd) != null)
		//以当前节点为根节点，构建一颗红黑树
			hd.treeify(tab);
	}
}

然后在这个方法中构建红黑树，jdk1.8对HashMap的优化核心也在于此方法，可以重点看看

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null; // 定义树的根节点
	//这里的this是通过hd.treeify(tab);方法调用的，因此this就是hd，而hd是table数组中某个值，也就是链表的头节点
	// 以下的代码就是从头节点开始遍历链表
    for (TreeNode<K,V> x = this, next; x != null; x = next) { // 遍历链表，x指向当前节点、next指向下一个节点
        next = (TreeNode<K,V>)x.next; // 下一个节点
        x.left = x.right = null; // 设置当前节点的左右节点为空
        if (root == null) { // 如果还没有根节点
            x.parent = null; // 当前节点的父节点设为空
            x.red = false; // 当前节点的红色属性设为false（把当前节点设为黑色）
            root = x; // 根节点指向到当前节点
        }
        else { // 如果已经存在根节点了
            K k = x.key; // 取得当前链表节点的key
            int h = x.hash; // 取得当前链表节点的hash值
            Class<?> kc = null; // 定义key所属的Class
			//遍历红黑树
            for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历，此遍历没有设置边界，只能从内部跳出
                // GOTO1
                int dir, ph; // dir 标识方向（左右）、ph标识当前树节点的hash值
                K pk = p.key; // 当前树节点的key
                if ((ph = p.hash) > h) // 如果当前树节点hash值 大于 当前链表节点的hash值
                    dir = -1; // 标识当前链表节点会放到当前树节点的左侧
                else if (ph < h)
                    dir = 1; // 右侧
 
                /*
                 * 如果两个节点的key的hash值相等，那么还要通过其他方式再进行比较
                 * 如果当前链表节点的key实现了comparable接口，并且当前树节点和链表节点是相同Class的实例，那么通过comparable的方式再比较两者。
                 * 如果还是相等，最后再通过 tieBreakOrder 比较一次
                 */
                else if ((kc == null &&
				//comparableClassFor返回键的类对象，该类必须实现Comparable接口，否则返回null
                            (kc = comparableClassFor(k)) == null) ||
                            (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
 
                TreeNode<K,V> xp = p; // 保存当前树节点
 
                /*
                 * 如果dir 小于等于0 ： 当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子 或者 更深层次的节点。
                 * 如果dir 大于0 ： 当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子 或者 更深层次的节点。
                 * 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩子 为 起始节点  再从GOTO1 处开始 重新寻找自己（当前链表节点）的位置
                 * 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。
                 * 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点进行处理了。
                 */
				 //如果dir等于-1则，插入到左树，如果是1则插入到右树
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp; // 当前链表节点 作为 当前树节点的子节点
                    if (dir <= 0)
                        xp.left = x; // 作为左孩子
                    else
                        xp.right = x; // 作为右孩子
                    root = balanceInsertion(root, x); // 重新平衡
                    break;
                }
            }
        }
    }
 
    // 把所有的链表节点都遍历完之后，最终构造出来的树可能经历多个平衡操作，根节点目前到底是链表的哪一个节点是不确定的
    // 因为我们要基于树来做查找，所以就应该把 tab[N] 得到的对象一定根节点对象，而目前只是链表的第一个节点对象，所以要做相应的处理。
    moveRootToFront(tab, root); 
}

（3）resize方法对HashMap扩容

接下来看看扩容方法

final Node<K,V>[] resize() {
	Node<K,V>[] oldTab = table;
	//oldCap---原hashMap的最大容量,oldThr---原hashMap的负载容量
	int oldCap = (oldTab == null) ? 0 : oldTab.length;
	int oldThr = threshold;
	int newCap, newThr = 0;
	if (oldCap > 0) {
		if (oldCap >= MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return oldTab;
		}
		//左移一位,就是将原来的容量翻倍，翻倍后的值小于2的30次方，大于原来的容量值
		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
				 oldCap >= DEFAULT_INITIAL_CAPACITY)
			//原来的负载容量翻倍	 
			newThr = oldThr << 1; // double threshold
	}
	else if (oldThr > 0) // initial capacity was placed in threshold
		newCap = oldThr;
	else {               // zero initial threshold signifies using defaults
		newCap = DEFAULT_INITIAL_CAPACITY;
		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
	if (newThr == 0) {
		float ft = (float)newCap * loadFactor;
		newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
				  (int)ft : Integer.MAX_VALUE);
	}
	threshold = newThr;
	@SuppressWarnings({"rawtypes","unchecked"})
		Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
	table = newTab;
	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;
					}
				}
			}
		}
	}
	return newTab;
}

以上就是HashMpa中几个重要的方法，get方法相对来说比较简单就不做介绍了，当一个容量稍大的HashMap对象放在jvm中时，它数据的逻辑结构如下图

其中白底的虚线框是数组，也可以说是哈希桶，当不同的数据经过哈希计算后被放到同一个哈希桶时（哈希碰撞）这些数据会以链表的方式组合在一起，也就是图中绿底框。当有相当多的数据出现哈希碰撞时，会导致这个链表很长，在使用get方法时，需要遍历链表，我们知道链表优势是增删快，查找慢，这样get方法效率会很低。因此在jdk1.8中对这里做了优化，当链表长度不小于8时就将链表转化成红黑树，长度小于8时再转化为链表。既然红黑树能有效的提高查询速度（黑红树查找相当于二分查找），那为什么不一开始就把链表转化为红黑树，而是要在链表长度大于8时才做这样的处理呢？这里个人理解，红黑树固然能提高查询速度，但也带来了维护红黑树的成本。我们知道红黑树是一颗自平衡的二叉树，因此在插入数据时，有可能导致红黑树不平衡，这时需要翻转红黑树使它达到平衡状态。而8这个数字就是链表和数字在插入效率和查询效率上的折中处理，就如同HashMap的负载因子是0.75，而不是0.6或是0.8，是一个道理。

3 . HashMap的扩容

通过阅读源码，我们知道HashMap中数组的默认初始长度是16。但当数组中有数据的个数超过总数的0.75时，HashMap就会自动扩容。一旦扩容，就意味着，旧的HashMap中的Entry全部要迁移到新的HashMap中，也就是rehash。想一下如果是你做这件事，你会怎么做呢？我思考过这个问题，首先要把所有的Entry放到一起，然后遍历所有的Entry，出现哈希碰撞时，就把碰撞的数据组成链表。为什么要遍历所有的Entry，因为table[]的长度变成了原来的两倍，所以所有的Entry都需要通过哈希算法重新定位到新的哈希桶。这样做确实很直接，简单粗暴。但如果旧的HashMap中数据量非常大，这样做不但需要一个超大的数组暂存所有的Entry，而且HashMap的扩容将是一个巨大且低效率的 “工程” 。HashMap源码的编写者比我要睿智的多，我们来看看HashMap源码中扩容是怎么做的。其实这个问题的核心点在于哈希算法的设计。也就是Entry的key通过什么样的哈希算法定位到table中的位置。下面是jdk中的哈希算法

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

以及putval方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
       //这里是定位Entry在table[]中的下标，其中n是table[]的长度
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        }
   }

上面两个方法，第一个是hash算法，这个方法的作用是根据key计算哈希值，使结果尽量的离散，这样当数据很多时，数据才会尽可能均匀的分布在哈希桶中。而第二个方法中数组的长度与哈希值的与计算得到下标。然后就是最后一个巧妙的设计了，table[]扩容为原来的两倍。我们先来看以下两种情况，这里HashMap的长度是默认值16

1.key计算后的哈希值小于16

2.key计算后的哈希值大于16

图中的与运算就是源码中Entry确定table下标的代码，也就是上面putval代码的第七行 p = tab[i = (n - 1) & hash] 这行代码的计算。从图中计算的结果可以看出，与运算保留了低位的值，去掉了高位的值。因此在hash值小于16的情况下，旧的Entry在重新定位到扩容后的新HashMap的table下标时，得到的下标值是一样的。而在hash值大于16的情况下，旧的Entry在重新定位到扩容后的新HashMap的table下标时，得到的下标值是不一样的。这说明在第一次HashMap扩容时，hash值大于16的Entry会迁移到新的位置，而小于16的Entry不需要迁移。这就保证了旧table已经散列良好的数据位置重新调换的频率。而每次扩容两倍更是保证了，每次变化的位数只有一位，如下图

这样就可以使之前已经散列好的数组变动最小，这也是为什么扩容2倍的原因。到这里可以给HashMap的原理做个总结：HashMap由数组加链表组成的，数组是HashMap的哈希桶，链表则是为解决哈希碰撞而存在的，如果定位到的数组位置不含链表（即哈希桶中只有一个Entry）,那么对于查找，添加等操作很快，仅需一次寻址即可（数组根据下标寻址，速度很快）；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，也需遍历链表，然后通过key对象的equals方法逐一比较查找。所以，性能考虑，HashMap中的链表出现越少，性能就会越好。（其实也就是key的哈希值越离散，Entry就会尽可能的均匀分布，出现链表的概率也就越低）

4 . 重写equals和hashCode方法

这个问题相信很多初学java的朋友都碰到过。就是在使用自定义对象作为HashMap的key时，如果重写了equals，也一定要重写hashcode方法。首先来看个小例子，如果在类中重写了equals方法，但是不重写hashCode方法会出现什么样的问题

public class Car {
    private String card;
    private String name;
    private int size;

    public Car(){}

    public Car(String card,String name){
        this.card=card;
        this.name=name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()){
            return false;
        }
        Car person = (Car) o;
        //两辆车，根据车牌判断是否相等
        return this.card.equals(person.card);
    }
    
    //省略set和get方法
    
    
   public static void main(String[] args){
        HashMap<Car,String> map = new HashMap<>();
        Car car1 = new Car("湘B2731","本田");
        map.put(car1,"张三的车");
        Car car2 = new Car("湘B2731","本田");

        System.out.println("结果---"+map.get(car2));
    }
   
}

我定义了一个汽车类，重写了equals方法，通过判断两辆车的车牌号相等来判断是否为同一辆车，预期结果应该输出张三的车，可实际结果却不是这样的，实际输出如下

结果---null

通过上面HashMap的原理，我们大概能明白其中的道理，是因为我们没有重写hashCode方法的原因，因为两个对象的哈希值不一样，导致定位到了HashMap的不同哈希桶中，因此没有get到值。但为什么hashCode会不相等呢。这需要搞清楚hashCode方法的原理。equals方法和hashCode方法都属于java基类Object类的方法，其中equals方法是用于比较两个值是否相等的。hashCode主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable，可以这么理解hashCode方法就是为了集合而生的。或许很多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在成千上万条数据或者更多，如果采用equals方法遍历比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当需要通过集合查找某条数据时，先调用这个对象的hashCode方法，得到对应的hashcode值。这样就把值的范围定位到一小片区域（即哈希桶）中，只要遍历这里面的数据就能找到这条数据了。说了这么多，那么hashCode是怎么计算而来的呢？有些朋友误以为默认情况下，hashCode返回的就是对象的存储地址，这种看法是不全面的，确实有些JVM在实现时是直接返回对象的存储地址，但是大多时候并不是这样，只能说与存储地址有一定关联。下面是HotSpot JVM中生成hash散列值的实现：

static inline intptr_t get_next_hash(Thread * Self, oop obj) {
  intptr_t value = 0 ;
  if (hashCode == 0) {
     // This form uses an unguarded global Park-Miller RNG,
     // so it's possible for two threads to race and generate the same RNG.
     // On MP system we'll have lots of RW access to a global, so the
     // mechanism induces lots of coherency traffic.
     value = os::random() ;
  } else
  if (hashCode == 1) {
     // This variation has the property of being stable (idempotent)
     // between STW operations.  This can be useful in some of the 1-0
     // synchronization schemes.
     intptr_t addrBits = intptr_t(obj) >> 3 ;
     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
  } else
  if (hashCode == 2) {
     value = 1 ;            // for sensitivity testing
  } else
  if (hashCode == 3) {
     value = ++GVars.hcSequence ;
  } else
  if (hashCode == 4) {
     value = intptr_t(obj) ;
  } else {
     // Marsaglia's xor-shift scheme with thread-specific state
     // This is probably the best overall implementation -- we'll
     // likely make this the default in future releases.
     unsigned t = Self->_hashStateX ;
     t ^= (t << 11) ;
     Self->_hashStateX = Self->_hashStateY ;
     Self->_hashStateY = Self->_hashStateZ ;
     Self->_hashStateZ = Self->_hashStateW ;
     unsigned v = Self->_hashStateW ;
     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
     Self->_hashStateW = v ;
     value = v ;
  }
 
  value &= markOopDesc::hash_mask;
  if (value == 0) value = 0xBAD ;
  assert (value != markOopDesc::no_hash, "invariant") ;
  TEVENT (hashCode: GENERATE) ;
  return value;
}

该实现位于hotspot/src/share/vm/runtime/synchronizer.cpp文件下。到这里我们就能明白为什么只重写equals方法不行了，既然hashCode和对象内存地址有关系，那么上面那个例子中，在往HahsMap中set和get时，明显是两个不同的对象，因此肯定会得到不同的哈希值。当我们重写了hashCode方法后，就能得到预期的结果了。

public class Car {
    private String card;
    private String name;
    private int size;

    public Car(){}

    public Car(String card,String name){
        this.card=card;
        this.name=name;
    }

    @Override
    public int hashCode() {

        return Objects.hash(card, name, size);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()){
            return false;
        }
        Car person = (Car) o;
        //两辆车，根据车牌判断是否相等
        return this.card.equals(person.card);
    }

  	// 省略get和set方法
  	
  	public static void main(String[] args){
        HashMap<Car,String> map = new HashMap<>();
        Car car1 = new Car("湘B2731","本田");
        map.put(car1,"张三的车");
        Car car2 = new Car("湘B2731","本田");

        System.out.println("结果---"+map.get(car2));
    }
}

实际输出结果

结果---张三的车

5 . HashMap的并发问题

HashMap是不能在并发场景下使用的，因为在HashMap的源码中，它的所有方法都没有同步处理。实际上只要是在堆中的对象，如果在多线程情况下使用而不做同步处理的话，都有可能导致数据不一致的问题。HashMap独特的数据结构还会带来另一个问题，这个问题在jdk1.8中得到了解决，但在jdk1.7中这个bug是很严重的存在，关于这个问题的解析，网上的博客也有很多，这里我也再回顾一下这个问题，权当复习，下面不做声明的话，默认都是说的jdk1.7的HashMap。

1. jdk1.7中HashMap的并发问题

大家都知道HashMap正常情况下哈希桶中的数据是一个单向链表，而并发情况下哈希桶中的链表有可能会形成一个环形链表。而一旦环形链表出现将会出现一个严重的问题，就是HashMap的get方法。我们知道在使用get时，首先会通过哈希算法定位到哈希桶，然后再通过equals方法遍历链表，获取key对象的值。问题就出现在这里，因为需要遍历链表，如果链表变成环形链表，这个遍历就会变成死循环。这个导致当前线程持续占用cpu资源，得不到释放，甚至会把cpu资源耗尽，是一个极其危险的情况。当另外一个线程get 到这个死循环的key的时候，这个线程也陷入死循环。最后结果是越来越多的线程死循环，最后导致服务器宕机。那么HashMap的环形链表是如何出现的呢？究其原因是因为它的扩容机制，即rehash。当table中的哈希桶超过HashMap默认的0.75时，会自动扩容，这个扩容在单线程下没有任何问题。而在多线程下问题就暴露出来了。那么来看看多线程场景下，环形链表是怎么出现的。下面是jdk1.7中的resize方法，这里省略了部分代码，直接看核心代码

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //省略无关代码
    //创建一个新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //将Old Hash Table上的数据迁移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

在resize方法中调用了transfer方法，transfer方法源码如下

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //  从OldTable里摘一个元素出来，然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next; // ① <--假设线程一执行到这里就被调度挂起了
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

上面代码中，外层的for循环遍历的是HashMap的table[]，即所有哈希桶，而里层的do…while循环遍历的是哈希桶中的链表。现在假设有两个线程在执行put方法时，都出现了HashMap的扩容。两个线程怎么同时出现需要扩容的情况呢，很简单。看addEntry方法源码

void addEntry(int hash, K key, V value, int bucketIndex)
{
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
    if (size++ >= threshold)   // ② <--线程挂起
        resize(2 * table.length);
}

上面两方法的源码中，我分别标注了①和②两个断点。这两个点就是环形链表的形成的原因，为了方便分析，再假设服务器cpu为单核。在②处代码是关于HashMap是否需要扩容的判断，由于此方法没有加synchronized修饰。于是当线程1运行到②处时，线程判断当前的HashMap需要扩容，就在此时线程1被挂起（线程是操作系统调度的最小单元，是否被挂起，什么时候被挂起，什么时候继续运行，都是由操作系统的线程调度说了算）。这时线程2也运行到了②处，这时由于线程1被挂起了，HashMap实际上还没有进行扩容操作。因此线程2也判断当前的HashMap需要扩容。于是两个线程都会执行resize方法。如果此时线程2一鼓作气，将扩容操作全执行完倒也好了，大不了线程1再执行一遍扩容操作，两个线程也会相安无事。可事与愿违，两个线程是交替运行的。在代码①处再出现线程被挂起的情况，就会出现环形链表。下面拿几个数据，举例说明一下，首先来看一下正常情况下的rehash过程。我假设HashMap的table初始长度为2，现在由于要rehash扩容到4。HashMap中有一个长度为3的链表。同样的为了简化分析，这里哈希算法，仅仅只是用key值除以table的长度取余来定位哈希桶的位置，哈希桶0有一个key为2的Entry，哈希桶1有3个key为3,5,7的Entry组成的链表，数据结构如下

正常的rehash过程

1.table[]的第二次循环，遍历哈希桶1，链表的第一次循环，此时e指向Entry<3,b>，next指向Entry<5,c>；

2.table[]的第二次循环，遍历哈希桶1，链表的第二次循环，此时e指向Entry<5,c>，next指向Entry<7,d>；

3.table[]的第二次循环，遍历哈希桶1，链表的第三次循环，此时e指向Entry<7,d>，next指向null；为了便于理解，下图简单的描述了正常的rehash过程

并发的rehash过程

假设线程2已经完成了对hashMap的扩容，那么线程1和线程2的状态分别如下（再强调一下出现环链的前置条件是两个线程同时读到了原HashMap的值，都准备扩容）

这个时刻线程2完成rehash过程，有图不难看出，新的HashMap已经是由两条链表有值了，然后由于操作系统的调度，线程2挂起，线程1继续执行rehash过程。这时线程1拿到的新的HashMap已经是线程1rehash完成之后的HashMap，里面是有值的。我们来看线程1进行rehash的第一步

在链表的第一次循环时，取下原链表的Entry<3,b>值，经过hash算法得到插入新HashMap的第三个下标，由于会采用头节点插入法，因此会得到Entry<3,b> 指向 Entry<7,d>，而此链表中原本就存在Entry<3,b>，且链表结构为Entry<7,d>指向Entry<3,b>。所以就出现了 Entry<3,b> 指向 Entry<7,d> 指向 Entry<3,b>。环形链表就这样出现了，上图实际上应该是这样子的

我们知道正常rehash流程线程拿到是是一个新的全空的HashMap，而在并发情况下，线程1是在线程2进行了全部或者部分rehash基础上，对新的HashMap进行rehash，而且扩容时操作同一个链表导致了环形链表的出现。环形链表一旦出现将导致get方法出现问题，因为get方法时会遍历链表去找到对应的key。假设某个key经过hash需要去遍历3链表，而恰巧3链表中没有这个key，那么get方法就一直在遍历这个链表break不掉了。在jdk1.8中修复了这个问题，使用了两个局部链表进行扩容不会出现哈希环。但jdk1.8中HashMap仍然不可在并发场景下使用，因为HashMap的put方法在并发下会出现丢数据的问题。

总结

对于HashMap的并发问题，有几种解决办法。1. 使用HashTable，这个类是线程安全的。但HashTable源码好像只是在方法上加上了synchronize方法，而synchronize 属于重量级锁，对效率损耗是比较大的。2. 使用jdk1.8中的ConcurrentHashMap，这个类实现了更高级的线程安全，且使用分段锁，在并发下也可有很高的吞吐量，推荐使用。对于HashMap的原理解析就到这吧，如有纰漏，望指正。

打赏一个呗