[数据结构与算法]HashMap浅薄详解见解

1、概述

想要API的链接：最新版API JDK11版本中文释义

我们可以看到API中说明了，HashMap是基于哈希表的Map接口的实现。那其实java中对于HashMap的实现是采用对象数组+链表，而且在链表达到一定长度时，链表会转变成二叉树存储。
那么我们首先去学习什么是哈希表。
这里要穿插一个点，我们在提到哈希表时，我们要知道有一个方法是Object.hashCode()。那我为什么提到它呢，请往下看。
好，那我们接着打开API查看这个方法，首先搜索Object,下面有这个方法。

解释一下，这其中所谓的支持此方法，是你所编写的类重写了hasCode()方法,而散列表就是哈希表。

2、数据结构：哈希表

那我们来讲一讲哈希表：

那我觉得我上面的描述已经很完整了，不需要我再进行一步步的分析了。当然为了广大志同道合的好友难呢过狗更清晰的明白这张图的内容，我会再次去描述一下。

首先，上面已经说过，我们也了解一下Object.hashCode()这个方法了。那么我们因为要举例的嘛，所以我创建一个Object对象，别问我为什么创建Object,这还不是因为java万物皆对象。那之后我们搞一个哈希表，我们默认长度为16。那图中也有描述，在存储到哈希表时，会调用我们的hashCode值，然后与哈希表数组长度进行取模运算。那我们想一下，我们不管是多大的数据，取模16，得到的数字一定是0 - 15，对吧。那我们得到的这些0 - 15的数据就是下标。而下标可以确定对象存在哪个位置。

我们图中也举了个例子：一个数据的hash值为17，那我们的这个对象会存储到1下标。那么首先呢，我们要进行对这个1下标的存储数据进行判断，判断是否有数据，只有这个1下标指向的位置为null时，那我们可以直接存储进去。那如果有数据怎么办?哎，我就想存到这个1下标，有数据我也要存。这就好比一个茅坑一只屁股，那你非要和别人一起，那怎么办？放心，有办法，这就体现出我们的M哈希表的好处来了。

我们之前说过哈希表这个数据结构是什么样的?是对象数组+链表的，也就是说，当我们这个下标指向的位置有数据了，那又来了一个下标为1的数据，我们就将其排在这个数据之后，依次排开。

那又有一个情况：那在JDK1.8之后呢，当我们的哈希桶(能放一个链表的这个小框)中的数据数据大于8时，我们的链表会转换为红黑二叉树。(那如果有想要看的，可以去网上找，当然如果想要，可以直接留言，我会关注，指不定就更一个)。好，闲言少叙，废话不说啊，继续正文。
当然要注意一点就是，它不是在减到8的时候又转换成链表的，它是到了6才从红黑二叉树转换成了链表。

面试题

这里可以说个小面试题：就是如图中所言，当HR提问：哎，小火鸡，我问你一个问题啊，如果是有一个哈希桶中的已知数据为7，注意听，那我要往6减，问一定会从红黑树转成链表吗？

别已学过这，就兴致勃勃的回答，哎，是的呢！是个屁啊，首先从逻辑都知道，那人家会问你一个傻瓜问题吗？会，但是也要当成不会，认真回答，仔细思考，沉思半刻，让HR觉得，哎这个小虎吉不错奥。你看他对待问题的态度多认真啊！真好啊，就录取他了。那这时其实你已经成功了一半，另一半就是你要准确全面的回答这个问题，按照您刚刚的描述，我觉得您问的不够准确，您只说了已知数据为7，但是您并没有确定现在的存储方式是链表还是红黑二叉树，那如果是链表的话，就说明次数据就已没有到8，所以不用转换，而如果是红黑二叉树的话，那就在减到6的时候转换成链表结构。其实说到这里，HR就已经在心里对你暗暗点头，要录用你了，如果大家真的遇到这个问题一定要这样回答，录用了也给我报一个喜讯啊！

----------------------------------------------------华丽的分割线-----------------------------------------------------------------

哈希表的实现

好了说到这里，我们就结合API和源码来去看一下java中HashMap对于哈希表的实现。
首先来看我们的API：
我们之前说过了，HashMap有一个初始的容量，以及默认的加载因子(0.75),我们java中的哈希表使用的是对象数组+链表，根据哈希值计算下标，然后确定存在哪一个下标中，当然，我们的对象在存储的过程中会产生冲突，因为他们存储的下标是相同的，也就是这个下标冲突，哈希值冲突有很大概率会发生，那在java中就采用了链表与红黑树的方式来处理这个问题。好之前的内容就复述到这里，接下来我们来看一看，我们这个构造方法中所出现的初始容量和默认加载因子在一个位置构建的。我们来看源码。

我们首先来看一下他的这个构造方法：
这里我就不再赘述了，好吧，图上都要注释。
我们来看一下它的put方法。
通过这个找：

我们来看一下它通过put方法去添加数据的流程。
我们可以看到这个方法是有多么的简单，就是传了一个键一个值，然后就是先计算哈希值。然后呢，把这个哈希值和键和值传给了一个叫putVal的方法去存储。
好，我们点开这个putVal方法。

那我们可以看到，这个方法的实现就很有趣啊，我决定采用在源码上注释的方式为大家简单的说一下这个方法的实现。

/**put 数据获取方法
        我们可以看到，这里用到了很多牛逼的语法，使得代码看起来很简洁，但是也难以阅读，
        那接下来就由我来给大家分析分析部分源码的实现流程是怎样的。
        如果觉得我说的没问题还可以，很不错的话，请给个三连(点赞，收藏，关注我)，谢谢！啊，我又在痴人说梦了，但也许屏幕前的大帅比和大漂亮就给我三连也说不定啊！！！
 */

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)
		/*1、
		比如说这个(tab = table)== null，这个紫色的table是成员属性table赋值给我们的局部变量tab
			也就是相当于把某个成员属性赋值给我们的变量之后，再拿table去判断它是否等于空
			table就是默认长度的桶16赋值变量与null作比较，或者是让n = 哈希表长度与0判断，如果条件满足则进行下面的计算*/
            n = (tab = resize()).length;
		//也就是resize()//扩容算法，然后新扩容的数组赋值到tab,之后求出length,赋值给n
		//到这里，n就是我们数组的长度，而tab就是我们正在存储数据的哈希表
        if ((p = tab[i = (n - 1) & hash]) == null)
		/*3、
		又比如这个tab[i = (n - 1) & hash]，&二进制位与和hash值进行运算，
		其实这个操作就是那哈希值和长度减一进行取模length
		所以这里我给大家提供一个图片，这是从调用添加一路走下来的整个流程，
		这里我们直接说当我们通过哈希算法得到了哈希值后(注意：我们要知道，一对键值对应该存在哪是由键决定的，而不是值决定的)
		那我们具体计算下标是怎么计算的呢
		先计算下标，通过哈希值取模长度，得到下标，然后赋值给i下标,取出下标里的数据赋值给p,
		之后进行判断，如果==null，说明没有数据，那怎么办？
		*/
            tab[i] = newNode(hash, key, value, null);
            /*4、
			直接存就完事了，我们让这个下标直接等于一个new的新结点(链表的新节点)，然后存进去
			方法名称为newNode,方法内部就是这样的，我就不说了(创建结点返回出来)，这还不知道是怎么回事的，你可以不用再看了(开玩笑的，我有求必应，我下贱，直接私信就好)。
		//这里我们返回上图看看流程，每次判断之后都会增加修改次数，然后判断是否到达临界值(75%),当然这个散列因子我们是可以指定的
		这时打开API，那个散列因子会重新散列扩容
		当然我们也要意识到，官方给的这个默认值是作为一般规则，默认加载因子（.75）在时间和空间成本之间提供了良好的折衷。*/
		//5、那如果我们要是
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&//进入到else。计算哈希值
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
			/*6、
			那有数据的p会和我们要存的键值对进行比较，再去判断键是否一样或者两个键进行比较也是相同的，那这时给e赋值为p
			好，我们假定上面的if条件成立，那是不是我们就不用走下面的else if 和else了，所以我们先跳过这部分，直接往下看、
			那这句话的意思其实是说键是重复的，那e才不为null
			这个语句的意思也是：我们这个哈希桶的第一个元素，链表的根元素就是和我们现在要存的是重复的。*/
            else if (p instanceof TreeNode)
            //8、判断链表已经有8个数了，那我们就换成红黑二叉树来存
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
				//如果存储时发生了覆盖，那就返回e告诉下面的if
            else {//存储长度在1 - 8之间
			//不管如何，在这个for循环中一旦发现重复，e就会被赋值
                for (int binCount = 0; ; ++binCount) {//循环遍历1 - 8的数据
				//其实这两个if语句一直在判断当前链表结点是否和我们要存的数据是重复的
                    if ((e = p.next) == null) {//首先判断下一个链表是否为空
					//这是在判断为不重复之后，创建新结点存储
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //这是当我们正好存的是第8个数据
						//也就是要变成二叉树了，这也有二叉树的操作
                            treeifyBin(tab, hash);
                        break;
                    }
					//这是判断为重复后的操作
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
			//7、这里其实就是接上了最上面的刚才的if语句的操作
            if (e != null) { // existing mapping for key
                V oldValue = e.value;//7.1、首先取出旧值，用e.value覆盖旧值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;//7.2、把e.value赋值给新的value
                afterNodeAccess(e);
                return oldValue;//7.3、之后返回旧的值
            }
        }
        //2、这里就是扩容算法resize(),对table进行扩容
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

为了方便大家的理解，我贴心的准备了一张图来系统完整的表达这个步骤。(还不快来点个赞啊！)
那这个对应的步骤我就不再去一一标注了，大家都是成年人了，要学会去对比学习啊，不能再让我这个初学者去一口一口的喂你们了，你们也不怕走偏了？! ! !

那其实说了这么多都是在分析put方法，那剩下的其他像get方法、remove方法、大家都可以根据以上流程去看看它的原理是什么？虽然说懂不懂这些原理都和咱们敲代码去使用这些方法没什么太大的影响，但是，积累知识不是使用处理方法，工具，而是让我们了解见识到这些内容下的原理才是，我们要学会透过事物看本质，敲代码大家多多少少都能敲，但是 明白内里才是一法通，万事成。

注意：
那在这个步骤里面的size临界值产生这个结果的因子：散列因子(0.75)其实我们是可以去改变的。
那我们看到第三个构造方法就可以去指定你的散列因子。

注意：
1、初始容量：我们一定要根据你的需求去创建一个合理的哈希表容量，如果创建的过大，那可能会导致大量的散列。来，我们假设我们往我们的哈希表中调用1万个put方法，但是因为哈希表默认长度为16，所以我们要进行大量的散列，说白了，散列是什么？散列就是在你的数据大于最大容量时，它就会创建一个新的哈希表（重建内部数据结构），大约是之前的两倍容量，然后把你原来的数据迁移到新的哈希表中，那我们这10000个数据是不是要进行大量多次的频繁散列，每次到达临界值就散列，然后重新创建一个哈希表，然后再把数据一个个放进去，周而复始，如此以往，那我们的10000个数据其实就不只是单单存了10000次，它就有可能存了3万、4万乃至更多次，那这就造成了浪费系统性能。所以我们一定要给一个更合理的初始容量，去避免大量散列，重建内部数据结构，避免浪费系统性能。

HashMap的实例有两个影响其性能的参数： 初始容量和负载因子 。 容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。 加载因子是在自动增加容量之前允许哈希表获取的完整程度的度量。 当哈希表中的条目数超过加载因子和当前容量的乘积时，哈希表将被重新哈希（即，重建内部数据结构），以便哈希表具有大约两倍的桶数。

2、散列因子：如果我们设置个0.9，那可能存在大量哈希值碰撞的情况，就是某个桶中存了好几个数据都没有扩容。
又假如我们设置的散列因子为0.5，那我们的哈希桶只能存一半，但是效率高，占用空间大；那我们设置一个0.9、0.99，那我们的哈希桶利用的特别好，空间一点没浪费，但是扩容次数会很少，当然查找数据也会很慢。注意，不要太大 ：如果初始容量大于最大条目数除以加载因子，则不会发生重新加载操作。也就不会散列，不会再扩容了。

散列因子的引用API： 作为一般规则，默认加载因子（.75）在时间和空间成本之间提供了良好的折衷。 较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put ）。 在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以便最小化重新散列操作的数量。 如果初始容量大于最大条目数除以加载因子，则不会发生重新加载操作。

好，最后我们进行一点小小的测试：

/**put 数据获取方法
        我们可以看到，这里用到了很多牛逼的语法，使得代码看起来很简洁，但是也难以阅读，
        那接下来就由我来给大家分析分析部分源码的实现流程是怎样的。
        如果觉得我说的没问题还可以，很不错的话，请给个三连(点赞，收藏，关注我)，谢谢！啊，我又在痴人说梦了，但也许屏幕前的大帅比和大漂亮就给我三连也说不定啊！！！
 */

/**
 * Map:遍历Map集合
 * 通过keySet集合可以获取到键的所有的Set集合,
 * 然后，再通过键获取到所有的值，之后我们可以遍历键和值
 * 如果只需要遍历键，则用keySet把Set集合迭代一下就是所有的键
 * 如果只想遍历值，可以使用Map集合中的values()方法，
 * 把所有的值变成Collection，变成单值存储的集合就可以遍历了，但是用的少
 */
public class Demo9 {
    //Map
    //HashMap/Hashtable/ConcurrentHashMap
    //TreeMap
    //LinkedHashMap
    public static void main(String[] args) {
       	HashMap<String, String> data = new HashMap<>();
        data.put("key1","锄禾日当午");//put存
        data.put("key2","汗滴禾下土");
       /* String value = data.get("key1");
        System.out.println(value);
        value = data.get("key2");
        System.out.println(value);*/
        //遍历
        Set<String> set = data.keySet();
        for (String key:set) {
            System.out.println(key+"->"+data.get(key));
        }
        Collection<String> values = data.values();
        for (String value:values) {
            System.out.println(value);
        }
    }
}

OK，获取+遍历打印

总结

那通过这次的学习也算是对HashMap有了一丁丁的了解，革命尚未成功，同志们仍需努力，大不了转行呗，咱到哪都是最棒的！，对了，别忘了三连啊。