предисловие
Я знаю, что все знакомы с хэшмапами, и создадут новый, если будет что-то или ничего, но некоторые возможности хэшмапов забыты и забыты, сегодняшний пример может помочь вам их хорошо запомнить.
Сцены
Пользователь отправляет ответ на тестовую работу на сервер, и почтовое сообщение может быть упрощено как
[{"question_id":"100001","answer":"A"},{"question_id":"100002","answer":"A"},{"question_id":"100003","answer":"A"},{"question_id":"100004","answer":"A"}]Отправить адрес в спокойном стиле
http://localhost:8080/exam/{试卷id}/answerИтак, как сравнить вопросы, отправленные клиентом, в этой контрольной работе, что, если пользователь подделал контрольную работу?
нормальное решение
- Получить список всех идентификаторов вопросов в контрольной работе
- 2-слойный цикл for для сравнения номеров вопросов и ответов
- Оценочная оценка
Примерный код выглядит следующим образом [другие коды]
//读取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);
}Эта проблема решается с помощью общего двухуровневого цикла for. Первый уровень — это вопросы в базе данных, а второй уровень — это вопросы, отправленные пользователем. В это время ошибка будет обнаружена. Предполагая, что пользователь подделал 10 000 вопросов или более, объем вычислений на сервере значительно возрастет.
Используйте hashmap для решения
Во-первых, посмотрите на его определение
Реализация интерфейса карты на основе хеш-таблицы. Эта реализация предоставляет все необязательные операции с картами и допускает нулевые значения и нулевые ключи. (Класс HashMap почти такой же, как Hashtable, за исключением того, что он не синхронизирован и допускается значение null.) Этот класс не гарантирует упорядоченность карты и, в частности, не гарантирует, что порядок сохранится.
В основном это зависит от того, что HashMap kv поддерживает нулевые значения, почему бы нам не добавить ответы, отправленные пользователями, в HashMap, где идентификатор вопроса используется в качестве ключа, ответ используется в качестве значения, а ключ HashMap поддерживает начало с буквы. Нам нужно только зациклить все вопросы в контрольной работе, а затем мы можем получить ответ через этот map.put("id вопроса"), а затем сравнить ответы, потому что ключ HashMap хранится в виде hashcode, поэтому в программе у этой схемы высокая эффективность.
Идеи:
- Добавьте хэш-карту к отправленному ответу с идентификатором вопроса в качестве ключа и ответом в качестве значения.
- для списка объектов цикла непосредственно сравните ответ
- Оценка
код показывает, как показано ниже:
//拿到用户提交的数据
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
Сначала загляните в документацию
Это примерно переводится как
- Реализовать карту, клонируемую, сериализуемую
- Реализация интерфейса Map на основе хеш-таблицы.
- Эта реализация предоставляет все необязательные операции с картами и допускает нулевые значения и нулевые ключи. (Класс HashMap примерно эквивалентен Hashtable, за исключением того, что он не синхронизирован и допускается значение NULL).
Этот класс не дает никаких гарантий относительно порядка Карты; в частности, нет гарантии, что порядок останется неизменным с течением времени. -
Эта реализация обеспечивает постоянную производительность для основных операций (получение и размещение), предполагая, что хеш-функция правильно распределяет элементы по этим корзинам. Итерация представления коллекции должна быть пропорциональна «емкости» (количеству сегментов) экземпляра HashMap и его размеру (количеству карт «ключ-значение»). Поэтому, если важна итеративная производительность, очень важно не устанавливать слишком высокую начальную емкость (или слишком низкий коэффициент загрузки).
-
Экземпляр HashMap имеет два параметра, влияющих на его производительность: начальную емкость и коэффициент загрузки. Емкость — это количество сегментов в хэш-таблице, а начальная емкость — это просто емкость на момент создания хэш-таблицы. Коэффициент загрузки — это мера того, насколько полно хэш-таблица может получить до автоматического увеличения ее емкости. Когда количество записей в хеш-таблице превышает произведение коэффициента загрузки и текущей емкости, хеш-таблица повторно хешируется (т. е. перестраиваются внутренние структуры данных), так что хеш-таблица имеет примерно в два раза больше сегментов.
Итак, какова логика put?
Когда ключи HashMap помещаются, им не нужно использовать сравнение на равенство один за другим, поэтому временная сложность равна O (n), то есть сколько раз элементы в HashMap нужно зацикливать.
HashMap преобразует ключ в хэш-код. Действительно может быть несколько хэш-кодов с одной и той же строкой для хэш-кода, но, в конце концов, 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 разделяется на два случая: хранится ли ведро в виде связанного списка или в виде древовидной структуры.
Если ключ уже существует, измените старое значение и верните старое значение.
Если ключ не существует, выполняется операция вставки и возвращается null.
поставить операцию, когда происходит столкновение, если связанный список используется для обработки конфликта, выполняется метод вставки хвоста.
Примерный процесс работы put:
- Получить индекс ведра по хэш-значению, если он нулевой, значит коллизии нет, то ставить сразу
- Если возникает коллизия, разрешите реализацию коллизии: список цепочек по-прежнему остается деревом.
- Если узел для ключа найден, выполняется операция обновления.
- Если узел ключа не найден, выполняется операция вставки, и требуется modCount++.
- После выполнения операции вставки, если размер превышает пороговое значение, выполняется функция resize() для увеличения емкости.