Подскажите что не так

Вопрос по задаче

Обсуждается

Вроде все по требованиям

Добавь и реализуй класс OurHashMapStorageStrategy, используя класс Entry из предыдущей подзадачи. Класс OurHashMapStorageStrategy должен реализовывать интерфейс StorageStrategy.
8.1. Добавь в класс следующие поля:
8.1.1. static final int DEFAULT_INITIAL_CAPACITY = 16;
8.1.2. static final float DEFAULT_LOAD_FACTOR = 0.75f;
8.1.3. Entry[] table = new Entry[DEFAULT_INITIAL_CAPACITY];
8.1.4. int size;
8.1.5. int threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
8.1.6. float loadFactor = DEFAULT_LOAD_FACTOR;
8.2. Реализуй в классе следующие вспомогательные методы:
8.2.1. int hash(Long k)
8.2.2. int indexFor(int hash, int length)
8.2.3. Entry getEntry(Long key)
8.2.4. void resize(int newCapacity)
8.2.5. void transfer(Entry[] newTable)
8.2.6. void addEntry(int hash, Long key, String value, int bucketIndex)
8.2.7. void createEntry(int hash, Long key, String value, int bucketIndex)
8.3. Добавь в класс публичные методы, которые требует интерфейс StorageStrategy.
Какие-либо дополнительные поля класса не использовать. Методы, не описанные в задании, реализовывать не нужно. Если возникнут вопросы как реализовать какой-то метод или что он должен делать, то ты всегда можешь посмотреть, как работает похожий метод в HashMap.
Можешь добавить в метод main класса Solution тестирование новой стратегии. Запусти и сравни время работы двух стратегий на одинаковом количестве элементов.

Требования:

Класс OurHashMapStorageStrategy должен поддерживать интерфейс StorageStrategy.
В классе OurHashMapStorageStrategy должны быть созданы все необходимые поля (согласно условию задачи).
Методы интерфейса StorageStrategy должны быть реализованы в OurHashMapStorageStrategy таким образом, чтобы обеспечивать корректную работу Shortener созданного на его основе.
В классе OurHashMapStorageStrategy должны присутствовать все вспомогательные методы перечисленные в условии задачи.

package com.javarush.task.task33.task3310; import java.math.BigInteger; import java.security.SecureRandom; import java.util.Random; public class Helper { public static String generateRandomString() { Random random = new SecureRandom(); return new BigInteger(130, random).toString(36); } public static void printMessage(String message) { System.out.println(message); } }

Комментарии (10)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Павел Безумный учёный

Expert

3 ноября 2021, 10:53

В методах getKey() и getValue() добавьте проверку текущего элемента table[i] на null перед выполнением действий с этим элементом.

Иван

Уровень 11

3 ноября 2021, 13:51

оказывается неверно был реализован

public int hash(Long k) {
        return k.hashCode();
    }

Жора Нет

Уровень 39

4 мая 2022, 16:56

Павел, здравствуйте! Хочу разобраться в готовом решении от JavaRush. Но, похоже кроме Вас помочь больше некому. В методе put() в цикле, переменной e.value присваивается новое значение value. Вопрос мой в том, как она ложиться в table, если новое значение присваивается переменной e? хотя должно быть что-то типа: table[index].value = value; public void put(Long key, String value) { int hash = hash(key); int index = indexFor(hash, table.length); for (Entry e = table[index]; e != null; e = e.next) { if (key.equals(e.key)) { e.value = value; return; } } addEntry(hash, key, value, index); }

Павел Безумный учёный

Expert

4 мая 2022, 17:29

Здравствуйте! Здесь весь фокус в том, что массив table нужно рассматривать в виде нескольких "корзин" (по англ. buckets), в каждой из которых лежит несколько объектов Entry. Объекты внутри одной "корзины" выстраиваются в "цепочку": первый объект, добавленный к "корзину", имеет в себе ссылку на второй, второй - на третий и т. д. (по принципу связного списка). Сам метод работает следующим образом. По ключу key, переданному в аргументе, вычисляется значение хэша hash, а затем по этому хэшу определяется индекс "корзины", в массиве table, в которую следует добавить запись. Добавляемые записи вполне могут иметь одинаковый хэш, и соответственно, определяться в одну и ту же ячейку массива, отсюда и необходимость хранить в одной "корзине" несколько элементов. После того, как индекс "корзины" определён, из неё берётся первый элемент "цепочки" (ссылка на который, собственно говоря, и находится в ячейке массива table[index]). Затем у элемента Entry проверяется поле key, и если его значение совпадает с ключом, передаваемым в аргументе метода, то полю value присваивается новое значение, и на этом вставка записи завершается. Если же ключ первого элемента "цепочки" не совпадает с аргументом метода, то берётся следующий элемент "цепочки" (ссылка на него хранится в текущем элементе) и снова сравниваются ключи. Наконец, если вся "цепочка" объектов проверена и совпадения ключа не было обнаружено, то просто создаётся новая запись Entry и присоединяется к "хвосту цепочки".

Жора Нет

Уровень 39

4 мая 2022, 18:12

Но ведь Entry e - ссылка, а не сам объект. Ее состояние мы меняем e.value = value; а не самого объекта.

Павел Безумный учёный

Expert

4 мая 2022, 18:22

e - это объект записи типа Entry. Он содержит в себе поля key (ключ), value (значение) и next (ссылка на следующий объект Entry). Цикл перебирает сами объекты Entry, являющиеся "звеньями цепочки". А при обнаружении объекта с подходящим ключом у этого объекта перезаписывается поле value - запись обновляется новым значением.

Жора Нет

Уровень 39

4 мая 2022, 18:33

Кажется понял. Эти необычные для меня циклы for()...🤯 Я так понимаю здесь запись (Entry e = table[index] ... e = e.next) типа цикла for(Entry e : entries) где e - объект, а не ссылка...

Павел Безумный учёный

Expert

4 мая 2022, 19:00

Все операции в Java происходят со ссылками (разумеется, за исключением примитивных типов, но их сейчас не рассматриваем). Непосредственно сами объекты хранятся в отдельной области памяти, а действия, совершаемые с этими объектами на самом деле происходят со ссылками на них (для повышения производительности). Но для простоты можно сказать что переменная e хранит в себе объект, хотя на самом деле в этой переменной хранится только ссылка на объект. Цикл в приведённом Вами примере действительно предназначен для последовательного перебора элементов связного списка. Сначала берётся первый элемент списка, ссылка на который хранится непосредственно в ячейке массива, (то есть элемент e = table[index]). Этот элемент становится "текущим". Затем из этого "текущего" элемента достаётся ссылка из поля e.next, то есть достаётся следующий элемент Entry - это следующая итерация цикла. Так происходит до тех пор, пока не обнаруживается последний элемент цепочки, то есть такой, у которого поле next ссылается на null. Вот как это приблизительно выглядит:

Жора Нет

Уровень 39

4 мая 2022, 19:55

С бакетами и связыванием элементов мне понятно. Спасибо большое за труд и за картинку🤝🤟 Меня цикл в ступор ввел. Сейчас сижу и понимаю, что я задал глупый вопрос😬 Такое бывает иногда, нужно просто отдохнуть.

Павел Безумный учёный

Expert

4 мая 2022, 20:07

Цикл действительно выглядит непривычно, особенно под конец дня 😄. Это верный признак что нужна передышка!