专栏首页Java大联盟通过一个实际案例,彻底搞懂 HashMap

通过一个实际案例,彻底搞懂 HashMap

作者|邵磊

前言

我知道大家都很熟悉hashmap,并且有事没事都会new一个,但是hashmap的一些特性大家都是看了忘,忘了再记,今天这个例子可以帮助大家很好的记住。

场景

用户提交一张试卷答案到服务端,post报文可精简为

[{"question_id":"100001","answer":"A"},
{"question_id":"100002","answer":"A"},
{"question_id":"100003","answer":"A"},
{"question_id":"100004","answer":"A"}]

提交地址采用restful风格

http://localhost:8080/exam/{试卷id}/answer

那么如何比对客户端传过来的题目就是这张试卷里的呢,假设用户伪造了试卷怎么办?

正常解决思路

1、得到试卷所有题目id的list

2、2层for循环比对题号和答案

3、判定分数

大概代码如下

//读取post题目
for (MexamTestpaperQuestion mexamTestpaperQuestion : mexamTestpaperQuestions) {
    //通过考试试卷读取题目选项对象
    MexamQuestionOption questionOption = mexamQuestionDao.findById(mexamTestpaperQuestion.getQuestionId());
          map1.put("questionid", mexamTestpaperQuestion.getQuestionId());
          map1.put("answer", mexamQuestionDao.findById(mexamTestpaperQuestion.getQuestionId()).getAnswer());
          questionAnswerList.add(map1);
          //将每题分add到一个List
}

//遍历试卷内所有题目
for (Map<String, Object> stringObjectMap : list) {
    //生成每题结果对象
    mexamAnswerInfo = new MexamAnswerInfo();
    mexamAnswerInfo.setAnswerId(answerId);
    mexamAnswerInfo.setId(id);
    mexamAnswerInfo.setQuestionId(questionid);
    mexamAnswerInfo.setResult(anwser);
    for (Map<String, Object> objectMap : questionAnswerList) {
        if (objectMap.get("questionid").equals(questionid)) {
            //比较答案
            if (anwser.equals(objectMap.get("answer"))) {
                totalScore += questionOption.getScore();
                mexamAnswerInfo.setIsfalse(true);
            } else {
                mexamAnswerInfo.setIsfalse(false);
            }
        }
    }
    mexamAnswerInfoDao.addEntity(mexamAnswerInfo);
}

使用普通的2层for循环解决了这个问题,一层是数据库里的题目,一层是用户提交的题目,这时候bug就会暴露出来,假设用户伪造了1万道题目或更多,服务端运算量将增大很多。

利用hashmap来解决

首先,看看它的定义

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

主要看HashMap k-v均支持空值,我们何不将用户提交了答案add到一个HashMap里,其中题目id作为key,答案作为value,而且HashMap的key支持以字母开头。

我们只需要for循环试卷所有题目,然后通过这个map.put("题目id")就能得到答案,然后比较答案即可,因为HashMap的key是基于hashcode的形式存储的,所以在程序中该方案效率很高。

思路:

1、将提交答案以questionid为key,answer为value加入一个hashmap

2、for循环实体列表,直接比对答案

3、判分

代码如下:

//拿到用户提交的数据
Map<String, String> resultMap = new HashMap<>();

JSONArray questions = JSON.parseArray(params.get("questions").toString());
for (int size = questions.size(); size > 0; size--) {
    JSONObject question = (JSONObject) questions.get(size - 1);
    resultMap.put(question.getString("questionid"), question.getString("answer"));
}
//拿到试卷下的所有试题
List<MexamTestpaperQuestion> mexamTestpaperQuestions = mexamTestpaperQuestionDao.findBy(map);
int totalScore = 0;
for (MexamTestpaperQuestion mexamTestpaperQuestion : mexamTestpaperQuestions) {
    MexamQuestionOption questionOption = mexamQuestionDao.findById(mexamTestpaperQuestion.getQuestionId());
    MexamAnswerInfo mexamAnswerInfo = new MexamAnswerInfo();
    mexamAnswerInfo.setAnswerId(answerId);
    mexamAnswerInfo.setId(id);
    mexamAnswerInfo.setQuestionId(questionOption.getId());
    mexamAnswerInfo.setResult(resultMap.get(questionOption.getId()));
    //拿到试卷的id作为resultMap的key去查,能查到就有这个题目,然后比对answer,进行存储
    if (questionOption.getAnswer().equals(resultMap.get(questionOption.getId()))) {
        mexamAnswerInfo.setIsfalse(true);
        totalScore += questionOption.getScore();
    } else {
        mexamAnswerInfo.setIsfalse(false);
    }
    mexamAnswerInfoDao.addEntity(mexamAnswerInfo);
}

分析HashMap

先看看文档

大概翻译为如下几点

1、实现Map ,可克隆,可序列化

2、基于哈希表的Map接口实现。

3、此实现提供所有可选的映射操作,并允许 空值和空键。(HashMap 类大致相当于Hashtable,除非它是不同步的,并且允许null)。这个类不能保证Map的顺序; 特别是不能保证订单在一段时间内保持不变。

4、这个实现为基本操作(get和put)提供了恒定时间的性能,假设散列函数在这些存储桶之间正确分散元素。集合视图的迭代需要与HashMap实例的“容量” (桶数)及其大小(键值映射数)成正比 。因此,如果迭代性能很重要,不要将初始容量设置得太高(或负载因子太低)是非常重要的。

5、HashMap的一个实例有两个影响其性能的参数:初始容量和负载因子。容量是在哈希表中桶的数量,和初始容量是简单地在创建哈希表中的时间的能力。该 负载系数是的哈希表是如何充分允许获得之前它的容量自动增加的措施。当在散列表中的条目的数量超过了负载因数和电流容量的乘积,哈希表被重新散列(即,内部数据结构被重建),使得哈希表具有桶的大约两倍。

那么put逻辑是怎么样的呢?

HashMap的key在put时,并不需要挨个使用equals比较,那样时间复杂度O(n),也就说 HashMap 内有多少元素就需要循环多少次。

而HashMap是将key转为hashcode,关于hashcode的确可能存在多个string相同的hashcode,但是最终HashMap还会比较一次bucketIndex。bucketIndex是HashMap存储k-v的位置,时间复杂度只有O(1)。

图解

源码

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    // 以key的哈希码作为key  
    return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 处理key为null,HashMap允许key和value为null 
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        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;
            }
        }
        //如果是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();
    //如果key不存在,则执行插入操作,返回null。
    afterNodeInsertion(evict);

    return null;
}

}

put方法分两种情况:bucket是以链表形式存储的还是以树形结构存储的。如果是key已存在则修改旧值,并返回旧值。如果key不存在,则执行插入操作,返回null。put操作,当发生碰撞时,如果是使用链表处理冲突,则执行的尾插法。

put操作的大概流程:

1、通过hash值得到所在bucket的下标,如果为null,表示没有发生碰撞,则直接put。

2、如果发生了碰撞,则解决发生碰撞的实现方式:链表还是树。

3、如果能够找到该key的结点,则执行更新操作。

4、如果没有找到该key的结点,则执行插入操作,需要对modCount++。

5、在执行插入操作之后,如果size超过了threshold,这要扩容执行resize()。

本文分享自微信公众号 - Java大联盟(javaunion)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 通过一个实际案例,彻底搞懂 HashMap!

    我知道大家都很熟悉hashmap,并且有事没事都会new一个,但是hashmap的一些特性大家都是看了忘,忘了再记,今天这个例子可以帮助大家很好的记住。

    Java技术栈
  • 用一个通俗易懂的例子彻底说清楚单例模式

    实现单例模式有多种写法,这里我们只列举其中最常用的三种实现方式,且考虑到网站登录高并发场景下,将重点关注多线程环境下的安全问题。

    智慧zhuhuix
  • Java原来还可以这么学:如何搞定面试中必考的集合类

    本系列文章主要围绕Java程序员必须掌握的核心技能,结合我个人三年多的Java学习和工作经历,总结和沉淀下来的方法论,希望能让Java学习这件事变得更简单,作者...

    黄小斜学Java
  • 一个案例搞懂原码、反码、补码,不懂得请看过来

    根据冯~诺依曼提出的经典计算机体系结构框架。一台计算机由运算器,控制器,存储器,输入和输出设备组成。其中运算器,只有加法运算器,没有减法运算器(据说一开始是有的...

    用户7656790
  • 如何实现一个连接池?一文带你深入浅出,彻底搞懂!

    【2w1h】是技术领域中一种非常有效的思考和学习方式,即What、Why和How;坚持【2w1h】,可以快速提升我们的深度思考能力。

    孙玄@奈学教育
  • 通过一个完整例子彻底学会protobuf序列化原理

    Protobuf是我们在网络传输中经常会用到的协议,优点是版本间兼容性强,对数据序列化时的极致压缩使得Protobuf包体积比xml、json等格式要小很多,节...

    horstxu
  • 「冰河技术」部分精华文章目录汇总

    个人研发的在高并发场景下,提供的简单、稳定、可扩展的延迟消息队列框架,具有精准的定时任务和延迟队列处理功能。自开源半年多以来,已成功为十几家中小型企业提供了精准...

    冰河
  • 一个案例彻底弄懂如何正确使用 mysql inndb 联合索引

    查看当时的监控情况 cpu 使用率是超过了100%,show processlist看到很多类似的查询都是处于create sort index的状态。

    用户7657330
  • 长文慎入!大厂架构演进实战之手写 CAS 单点登录

    单点登录在大型网站里使用得非常频繁,那么什么是单点登录?一句话解释:一处登录,处处登录。

    南风
  • 两个高频设计类面试题:如何设计HashMap和线程池

    我的本意是抛砖引玉,针对每个题目给出我自己的理解和解释型的答案,然后背诵版本需要你们自行去总结和记忆。

    范蠡
  • JDK1.8源码(九)——java.util.LinkedHashMap 类

      前面我们介绍了 Map 集合的一种典型实现  HashMap  ,关于 HashMap 的特性,我们再来复习一遍:

    IT可乐
  • Java中常见数据结构Map之HashMap

    一枝花算不算浪漫
  • Java中常见数据结构Map之HashMap

    彻底搞懂HashMap,HashTableConcurrentHashMap关联:

    一枝花算不算浪漫
  • 每天都在用 Map,这些核心技术你知道吗?

    本篇文章站在多线程并发安全角度,带你了解多线程并发使用 HashMap 将会引发的问题,深入学习 ConcurrentHashMap ,带你彻底掌握这些核心技术...

    andyxh
  • 软件开发之道

    2.对于较难理解的,一定要多看,这个多看不仅仅指一遍遍的阅读技术文档或代码,而且也可以理解为不止某一天看,因为有些知识需要消化,当时看过之后未必能够消化掉,因为...

    小诸葛
  • 彻底讲明白MySQL的乐观锁和悲观锁

    对于MySQL中的乐观锁和悲观锁,可能很多的开发者还不是很熟悉,并不知道其中具体是如何实现的。本文就针对这个问题做一个实际案例演示,让你彻底明白这两种锁的区别。

    A梦多啦A
  • 面试HashMap看这篇就够了

    位运算操作是由处理器支持的底层操作,底层硬件只支持01这样的数字,因此位运算运行速度很快。尽管现代计算机处理器拥有了更长的指令流水线和更优的架构设计,使得加法和...

    sowhat1412
  • 2019 最新 Java 核心技术教程,都在这了!

    以下是Java技术栈微信公众号发布的所有关于 Java 的技术干货,会从以下几个方面汇总,本文会长期更新。

    Java技术栈
  • 从面试连跪到收割offer,回顾我的春招面试历程(研发岗位)

    作者黄小斜,斜杠青年,某985硕士,阿里 Java 研发工程师,于 2018 年秋招拿到 BAT 头条、网易、滴滴等 8 个大厂 offer,目前致力于分享这几...

    黄小斜学Java

扫码关注云+社区

领取腾讯云代金券