Skip to main content

08. Хэш-множество

Если в множестве нужно хранить большие объекты, а не целые числа, то полная проверка на равенство обойдётся слишком дорого.

Лучше для каждого объекта сначала считать некоторую сводную величину, которая будет занимать меньше места и при этом будет равна у равных объектов.

Лучше всего для такого сведения подходят хэш-функции. Сам результат сведения называют хэшем объекта. В java хэш-функция всегда возвращает переменную типа int, подробнее о хэшах можно прочитать здесь

Такое множество должно хранить два массива: массив ссылок на объекты и массив хэшей. Сначала для нового объекта высчитывается хэш, потом этот хэш ищется в массиве хэшей, для всех индексов, значения которых совпали с хэшем нового объекта, выполняется проверка самих объектов на равенство. Если ни один хэш не совпал, то и объектов, равных новому точно нет.

В данном блоке требуется разработать множество, хранящее строки.

У строк есть готовые методы сравнения .equals() расчёта хэша .hashCode():

public class Main {
    public static void main(String[] args) {
        String a = "TEST";
        String b = "TEST";
        String c = "TEST2";

        System.out.println(a.equals(b) + " " + b.equals(c));
        System.out.println(a.hashCode() + " " + b.hashCode() + " " + c.hashCode());
    }
}

На консоль будет выведено:

true false
2571410 2571410 79713760

Задание​

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

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

На основе множества MySet из предыдущего задания требуется написать класс хэш-множества строк MyHashSet (массив элементов должен хранить строки):

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

  1. Поле elements, в нём должны храниться элементы множества, а также поле elemCnt, хранящее количество сохранённых элементов.
  2. Конструктор по умолчанию MyHashSet(), в нём должен инициализироваться массив строк elements десятью пустыми строковыми элементами. Количество элементов elemCnt должно быть равно 00.
  3. Конструктор копии MyHashSet(MyHashSet mySet), который на основе множества, переданной в аргументе, инициализирует поля копиями полей полученной из аргументов множества
  4. String [] getData() - возвращает копию массива elements, но копироваться должны только сохранённые элементы (до elemCnt)
  5. int [] getHashes() - возвращает копию массива хэшей, но копироваться должны только сохранённые элементы (до elemCnt)
  6. boolean add(String v), он должен добавлять новый элемент в множество (в конец массива). При добавлении элементов в множество необходимо добавлять новый элемент в позицию с индексом, равным количеству уже добавленных элементов. Если массив уже полностью заполнен, то необходимо создать новый, в два полтора больший, и скопировать в него все элементы исходного массива. После этого необходимо добавить новый элемент. При добавлении Метод должен увеличивать количество добавленных элементов множества на 11. Перед добавлением необходимо проверить, нет ли уже такого элемента в множестве. Если такой элемент уже есть, то возвращает false, иначе true. Первоначальный размер массива элементов должен быть равен двум
  7. boolean remove(String v) - удаляет элемент, равный переданному в аргументах из множества (не только из массива), возвращает true, если такой элемент был и false, если нет
  8. boolean contains(String v) - возвращает true, если в множества есть хотя бы один элемент, равный переданному в аргументах и false, если нет
  9. boolean addAll(MyHashSet mySet) - добавляет в множество все элементы множества, переданной в аргументах по той же логике, что и void add(int v). Возвращает true
  10. boolean containsAll(MyHashSet mySet) - возвращает true, если в множества присутствует каждый из элементов переданной в аргументах множества
  11. boolean removeAll(MyHashSet mySet) - удаляет все элементы, содержащиеся в множестве mySet возвращает true, если был удалён хотя бы один элемент
  12. boolean retainAll(MyHashSet mySet) - оставляет только те элементы, которые есть в mySet возвращает true, если множество было изменено

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

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