Распределение элементов по корзинам с собственным локом

  • 14
  • Недоступна
В синхронизированных блоках используй нужный лок.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (133)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Сэм Фишер
Уровень 27, Кишинев, Молдова
7 сентября, 15:25
задача хорошая, но это еще одно подтверждение того, что теорию в курсе дают погано. бог с ними с источниками информации, давали бы список тем, с которыми стоило бы ознакомиться подробнее. а то про потокобезопасные коллекции почти ни слова и тут - бац.
Сергей Попов
Уровень 31, Пермь, Россия
7 сентября, 04:24
Это ж примерная реализация HashMap
Дмитрий Б.Г.
Уровень 32, Кременчуг, Украина
24 августа, 18:04
Если вы тоже не сразу доперли как работает равномерное распределение ключей и почему используется оператор %, то советую написать в main следующий цикл и запустить.
for (int i = 0; i < 100; i++) {
    System.out.println(i % 12);
}
Я себе фейспалмом лоб чуть не пробил, осознав как я натупил😅
Андрей
Уровень 29, Киев, Украина
7 августа, 20:22
Я так понял основная задача этой задачи была догадаться что означает "в зависимости от хэша объекта и количества лок объектов" и "в зависимости от индекса элемента и количества лок объектов" и как это описать на языке программирования))
Максим Дудин
Уровень 31, Калининград
2 августа, 14:50
"пять раз" перечитал комментарии и всё равно картинка сложилась не полностью
Алексей
Уровень 30, Phonky Town
28 июля, 10:25
Ничего не понял, скажите что почитать.
Flexo Bending Unit #3370318
8 июля, 20:36
принимается ответ только определённого вида - используйте уже имеющуюся локальную переменную, вместо метода - для вычисления хеша - не используйте константу размера контейнера блоков, а используйте метод самого контейнера для нахождения своего размера ненужные ограничения, не влияющие на работу, но как есть
Татьяна Мацеонжек
Уровень 35, Москва, Россия
28 апреля, 10:20
Не, ну спасибо за очередную технологию, но она вообще не ложится в ряд. Без предисловий и контекста задача вообще бесполезна. Я не требую теории под каждую задачу, но вот так отрывками подавать, тоже не вариант
ЕП
Уровень 29, Санкт-Петербург
7 апреля, 09:42
Поправьте, если не правильно понял. Здесь раскрывается механика работы конкурирующего списка. В частности, создаётся связный список из элементов Node, каждый из которых хранит ссылку на следующий узел и какую-то пару данных (ключ-значение). При этом список разделён на n-ное количество очередей. Начало каждой очереди мы записываем в массив buckets[n] и при добавлении нового элемента в связный список мы определяем его в одну из очередей. То, в какую очередь он попадёт, зависит от хеша ключа нового элемента. С помощью key.hashCode() % buckets.length мы разделяем все возможные хеши ключей на n вариантов. Теперь, если нам нужно выполнить поиск по этому списку, не обязательно листать весь список, достаточно пройти по одной из наших n очередей. По какой именно, определяется хешем ключа искомого элемента. При этом, реализована возможность работы с этим списком из нескольких нитей. Чтобы обезопасить данные, создаётся массив из нескольких объектов (по числу нитей, разрешённых для работы, в нашем случае -12) для выполнения работы в качестве замков. Поскольку число очередей и число замков различные, каждый замок может запирать от нуля до нескольких очередей (зависит от числа очередей). Прописывая "i%NUMBER_LOCKS", мы равномерно распределяем очереди между замками, что позволяет одновременно блокировать не весь список, а только некоторые очереди, среди которых имеется занятая. Это позволит другим нитям, например, параллельно выполнить поиск в списке, если искомый элемент находится в незаблокированной очереди.
Anonymous #1402188
Уровень 39
2 июня, 03:47
Спасибо. Только после твоей росписи понял, как тут всё устроено. Получается, что метод clear() зачищает не весь список, а просто заглавия очередей. Именно этот метод смущал.
ЕП
Уровень 29, Санкт-Петербург
12 июня, 20:26
Остальные элементы списка съедает сборщик мусора, поскольку они теряют удерживающую их связь
Anonymous #1402188
Уровень 39
15 июня, 04:27
ЕП Спасибо
Максим Дудин
Уровень 31, Калининград
2 августа, 14:49
всё равно до конца не понял.... "При этом список разделён на n-ное количество очередей. Начало каждой очереди мы записываем в массив buckets[n] и при добавлении нового элемента в связный список мы определяем его в одну из очередей." это откуда из кода видно... и вот тут "Поскольку число очередей и число замков различные, каждый замок может запирать от нуля до нескольких очередей (зависит от числа очередей)." т.е. до нескольких ли просто он опять делит число очередей на группы по числу замков?
ЕП
Уровень 29, Санкт-Петербург
26 августа, 14:06
Напрямую этого не видно, здесь не реализован метод put, но в конструкторе мы видим создание массива buckets, размер которого задаётся определённым числом, а также создание объектов, выступающих в роли замков - по количеству, заданному в константе: buckets = new Node[numberBuckets]; locks = new Object[NUMBER_LOCKS]; for (int i = 0; i < NUMBER_LOCKS; i++) { locks[i] = new Object(); } Далее, мы видим метод по определению номера очереди для объекта key, который является ключом хранимого объекта в списке: return Math.abs(key.hashCode() % buckets.length); В зависимости от хеш-кода ключа он направляется в одну из очередей от 0 до buckets.length. Логично, что и нода записывается с таким же распределением в одну из очередей. Ну и далее, при считывании объекта из списка, мы определяем очередь в соответствии с его ключом и закрываем замок, соответсвующий этому ключу: int hash = hash(key); synchronized (locks[hash%NUMBER_LOCKS]) { for (Node m = buckets[hash]; m != null; m = m.next) { if (m.key.equals(key)) return m.value; } } В цикле мы проходим по всей очереди, пока не найдём нужный объект по его ключу, это принцип работы связных списков. При этом, тот же замок может относиться и к другим очередям, поскольку количество замков и очередей различное. Но это, по крайней мере, позволяет освободить некоторые очереди для параллельной работы.
Максим Дудин
Уровень 31, Калининград
26 августа, 14:29
да спасибо.... там дальше потом были расклады как и что, разобрался более менее
Mixer-X
Уровень 40, Санкт-Петербург
23 октября, 16:52
Друг, долгих лет кода тебе. Не знаю как бы я ее решал, но разобрался лишь благодаря тебе. После этого полную картину нарисовали короткие намеки остальных.
Даниил Александрович
Уровень 35, Тамбов , Россия
17 марта, 15:26
Странная задача. со странным ТЗ. на 100 или 1000000 объектов если такое количество локов, программа тупа будет в холостую постоянно висеть... плевать, done. и поехали дальше... лочим не объект, переменную. а какую и с каким индексом комменты ниже в помощь.