前言我知道hashmap大家都很熟悉，有什么都会新建一个，但是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那么怎么把客户端发来的题目和这张试卷进行比对呢？如果用户伪造试卷怎么办？正常的解决思路是获取试卷中所有问题id的列表。2层for循环比较问题编号和答案以确定分数。大致代码如下//读取题后题for(MexamTestpaperQuestionmexamTestpaperQuestion:mexamTestpaperQuestions){//通过试卷读取题目选项对象MexamQuestionOptionquestionOption=mexamQuestionDao.findById(mexamTestpaperQuestion.getQuestionId());map1.put("questionid",mexamTestpaperQuestion.getQuestionId());map1.put("答案",mexamQuestionDao.findById(mexamTestpaperQuestion.getQuestionId()).getAnswer());questionAnswerList.add(map1);//将每个问题添加到一个List中}//遍历试卷中的所有问题for(MapstringObjectMap:list){//生成每个问题结果对象mexamAnswerInfo=newMexamAnswerInfo();mexamAnswerInfo.setAnswerId(answerId);mexamAnswerInfo.setId(id);mexamAnswerInfo.setQuestionId(questionid);mexamAnswerInfo.setResult(answer);for(MapobjectMap: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就会暴露出来。假设用户伪造10000题或更多，服务器的计算量会增加很多。下面说一下HashMap和TreeMap的内部结构。使用hashmap解决方案首先，看一下Map接口的实现，它定义了一个基于哈希表的接口。此实现提供所有可选的映射操作并允许空值和空键。（HashMap类与Hashtable非常相似，只是它不是同步的并且允许空值。）此类不保证映射的顺序，特别是它不保证顺序不变。最主要的是HashMapk-v支持空值。为什么我们不将用户提交的答案添加到一个HashMap中，以topicid为key，以answer为value，HashMap的key支持以字母开头。我们只需要for循环所有试卷中的问题，然后通过这个map.put("questionid")得到答案，然后比较答案，因为HashMap的key是以hashcode的形式存储的，所以在程序中这个方案效率很高。思路：将提交的答案以questionid为key，answer为value加入一个hashmapforloopentitylist，直接比较答案打分代码如下：//获取用户提交的数据MapresultMap=newHashMap<>();JSONArrayquestions=JSON.parseArray(params.get("questions").toString());for(intsize=questions.size();size>0;size--){JSONObjectquestion=(JSONObject)问题.get(size-1);resultMap.put(question.getString("questionid"),question.getString("answer"));}//获取所有试题ListmexamTestpaperQuestions=mexamTestpaperQuestionDao.findBy(map);inttotalScore=0;for(MexamTestpaperQuestionmexamTestpaperQuestion:mexamTestpaperQuestions){MexamQuestionOptionquestionOption=mexamQuestionDao.findById(mexamTestpaperQuestion.getQuestionId());MexamAnswerInfomexamAnswerInfo=newMexamAnswerInfo();mexamAnswerInfo.setAnswerId(answerId);mexamAnswerInfo.setId(id);mexamAnswerInfo.setQuestionId(问题选项.getId());mexamAnswerInfo.setResult(resultMap.get(questionOption.getId())));//获取试卷的id作为resultMap的key进行校验，如果能找到这道题，则比较答案并存入if(questionOption.getAnswer().equals(resultMap.get(questionOption.getId()))){mexamAnswerInfo.setIsfalse(true);totalScore+=questionOption.getScore();}else{mexamAnswerInfo.setIsfalse(false);}mexamAnswerInfoDao.addEntity(mexamAnswerInfo);}分析HashMap先看文档，大致翻译如下PointimplementsMap,Cloneable,SerializableHashtable-basedMapinterfaceimplementation这种实现提供了所有可选的映射操作，并允许空值和空键。（HashMap类大致等同于Hashtable，只是它是异步的并且允许空值）。此类不保证Map的顺序；特别是它不保证订单会随着时间的推移保持不变。此实现为基本操作（get和put）提供恒定时间性能，假设散列函数正确地将元素分散在这些桶中。集合视图的迭代需要与HashMap实例的“容量”（桶数）及其大小（键值映射数）成正比。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低）是非常重要的。HashMap的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中桶的数量，初始容量只是创建哈希表时的容量。负载因子是哈希表在获得其容量之前被允许自动增加的充分程度的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表被重新哈希化（即重建内部数据结构）使得哈希表具有大约两倍的桶。那么put逻辑是怎样的呢？HashMap的key在放的时候，不需要用equals来一个一个比较，所以时间复杂度是O(n)，也就是说HashMap有多少个循环就有多少个元素。HashMap将密钥转换为哈希码。关于hashcode，同一个字符串确实可能有多个hashcode，但最终HashMap会比bucketIndex一次。bucketIndex是HashMap存放k-v的地方，时间复杂度只有O(1)。图解源代码/***将指定值与此映射中的指定键相关联。*如果映射先前包含键的映射，则替换旧*值。**@paramkeykeywhichthespecifiedvalueistobeassociated*@paramvaluevaluetobeassociatedwiththespecifiedkey*@returnthepreviousvalueassociatedwithkey,or*nullifkeymapping/tt>.*(Anullreturn也可以表示映射*先前关联null与key。)*/publicVput(Kkey,Vvalue){//以键哈希码为键'tchangeexistingvalue*@paramevictiffalse,thetableisincreationmode.*@returnpreviousvalue,ornullifnone*/finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanvict){Node[]tab;Nodep;intn,i;//处理key为null,HashMap允许key和value为nullif((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{Nodee;Kk;if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;elseif(pinstanceofTreeNode)//在树中存储e=((TreeNode)structurep).putTreeVal(this,tab,hash,key,value);else{//存入链表for(intbinCount=0;;++binCount){if((e=p.next)==null){p.next=newNode(hash,key,value,null);if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}//如果key已经存在，修改旧值，返回旧值if(e!=null){//existingmappingforkeyVoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;if(++size>threshold)resize();//如果key不存在，执行插入操作，returnnullafterNodeInsertion(evict);returnnull;}putm方法分为两种情况：bucket是以链表形式存储还是以树结构存储。如果key已经存在，修改旧值并返回旧值。如果key不存在，则执行insert操作，返回null。Put操作，当发生冲突时，如果使用链表处理冲突，则执行尾部插入方法。put操作的大体流程：通过hash值获取bucket的下标。如果为null，说明没有碰撞，那就直接放吧。如果发生碰撞，解决碰撞的实现方法：链表或树。如果能找到key的节点，则执行更新操作。如果没有找到key的节点，则进行插入操作，需要modCount++。执行插入操作后，如果大小超过阈值，需要扩容，执行resize()。
