Skip to main content

10. Словари

Каждому элементу множества мы можем сопоставить то или иное значение. Например, каждому элементу множества строк можно сопоставить целое число.

Тогда, зная элемент множества, мы можем, например, перебрав все элементы массива elements, найти индекс совпадающего элемента и вернуть связанное с ним целочисленное значение. Значения можно хранить просто во втором массиве и при увеличении размера массива elements увеличивать размер второго.

Такие структуры называются словарями. Элементы множества называются ключами, а связанные с ними значения - значениями

В Java реализованы словари на основе хэшей HashMap и на основе красно-чёрного дерева TreeMap.

Строго говоря, в Java реализованы словари, а соответствующие множества наследуют их как словари без ключей.

Задание​

Трудоёмкость

Это задание рассчитано на два урока, за него будет выставлено две оценки

Вам требуется на основе класса HashSet написать класс словаря MyHashMap на хэшах со строковыми ключами и целочисленными значениями:

Использовать встроенные коллекции java запрещается. Перед каждой проверкой на равенство строк должна быть проверка хэшей

  1. Поле keys, в нём должны храниться строковые ключи словаря, поле keyCnt, хранящее количество сохранённых элементов, а также поле values - массив значений
  2. Конструктор по умолчанию MyHashMap(), в нём должен инициализироваться целочисленный массив keys десятью нулевыми элементами. Количество элементов elemCnt должно быть равно 00.
  3. String [] getKeys() - возвращает копию массива elements, но копироваться должны только сохранённые элементы (до elemCnt)
  4. int [] getValues() - возвращает копию массива elements, но копироваться должны только сохранённые элементы (до elemCnt)
  5. boolean put(String key, int value), он должен добавлять новый элемент в множество ключей (в конец массива). При добавлении элементов в множество необходимо добавлять новый элемент в позицию с индексом, равным количеству уже добавленных элементов. Если массив уже полностью заполнен, то необходимо создать новый, в два полтора больший, и скопировать в него все элементы исходного массива. После этого необходимо добавить новый элемент. При добавлении Метод должен увеличивать количество добавленных элементов множество на 11. Возвращает true, если был добавлен ключ или изменено значение, false - в остальных случаях.
  6. boolean remove(String v) - удаляет ключ, переданных в аргументах и соответствующее ему значение, возвращает true, если получилось удалить и false, если такого элемента не было
  7. boolean containsKey(String v) - возвращает true, если в множестве есть хотя бы один элемент, равный переданному в аргументах и false, если нет
  8. int get(String v) - возвращает значение, если в словаре присутствует соответствующий ключ. Если такого ключа нет, то следует вернуть Integer.MAX_VALUE
  9. boolean putAll(MyHashMap myHashMap) - добавляет в словарь все пары ключ-значение из словаря, переданного в параметрах. Возвращается true, если был добавлен хотя бы один элемент и false - если нет.

Все поля и методы должны иметь модификатор public

Ссылка на контест