So much in this task I don't understand

Question about the task

Distributing items into baskets with their own lock

Under discussion

1. What's the Node class? I've tried googling this but the explanations are all very technical and refer to other things I also don't understand. 2. What's up with the for loop? I've never seen the .next in a for loop like this. 3. What is the hash method accomplishing? It seems it would return a semi-random number between 0 and buckets.length, since hashCode doesn't return a predictable value. if so, wouldn't it just be easier to use the built-in Random class? 4. I'm not even really sure what the get method does here. I can't even begin trying to solve this until I understand what the existing code is doing.

In the synchronized blocks, use the right lock.

Requirements:

The Solution class must have a private static final int LOCK_COUNT field.
The Solution class must have a private final Node[] buckets field.
The Solution class must have a private final Object[] locks field.
All of the Solution class's methods must not be synchronized.
In the synchronized block of the Solution class's get() method, use a lock from the locks array, depending on the object hash and the number of lock objects.
In the synchronized block of the Solution class's clear() method, use a lock from the locks array, depending on the element's index and the number of lock objects.

package com.codegym.task.task26.task2609; /* Distributing items into baskets with their own lock */ public class Solution { private static final int LOCK_COUNT = 12; private final Node[] buckets; private final Object[] locks; static class Node { public Node next; public Object key; public Object value; } public Solution(int bucketCount) { buckets = new Node[bucketCount]; locks = new Object[LOCK_COUNT]; for (int i = 0; i < LOCK_COUNT; i++) { locks[i] = new Object(); } } private final int hash(Object key) { return Math.abs(key.hashCode() % buckets.length); } public Object get(Object key) { int hash = hash(key); synchronized (locks[locks.length-1]) { for (Node m = buckets[hash]; m != null; m = m.next) { if (m.key.equals(key)) return m.value; } } return null; } public void clear() { for (int i = 0; i < buckets.length; i++) { synchronized (locks[locks.length - (i + 1)]) { buckets[i] = null; } } } public static void main(String[] args) { } }

Comments (7)

Popular
New
Old

You must be signed in to leave a comment

Lisa

Level 41

9 February 2022, 08:57

To solve this task it is not really necessary to know what's going on here (though very helpful as you'd know what to do right away). So I'll spoiler the solution... you're looking at a data structure here, a hash set. Unfortunately it isn't working as there is no add method implemented. 1. all linked data structures use an inner class holding (at least) one element. That's the node. It holds the value of that element and it points to the next element (that pointer is the Node next reference variable). The easiest to understand of those data structures is the stack. You have that inner Node class and the outer Stack class holds a Node reference. That's the head of the (coming) chain. If you add an element, you create a Node and save the Node in the Stacks Node variable. Adding a next node is nearly the same. You take the current Node reference from the stack, create a new Node with the new value and the current Node as next reference and save that new Node in the Stacks Node reference. So the Stack just contains of the new Node. That new Node has a next reference pointing to former Node. When you add another element, then you do the same, replace the current Node with the new put add the old Node as next Node to the current one. Popping an element is as easy. You look at the current node, take it's next reference and save the next reference in the Stacks Node variable. The head is gone ;) If you're interested in a some implementations... I've written some for a lot of data structures but it might help to see eg. a Stack, Queue or LinkedList. 2. Tough not very common it is legal to use a for loop this way. It initializes variables used inside the loop, has as second part the abort condition and finally you have code that is executed after each iteration. Nothing more is a loop doing. Eg. here from an older task... read strings from the console and add them to a set for (String fileName; !(fileName = console.readLine()).equals("end"); fileNames.add(fileName));

Lisa

Level 41

9 February 2022, 09:11

3. This is a hashSet. So explaining is is the key to the task, the solution. A hash set is a combination of an array, the hash values, and a linked data structure. The arrays key, the index, is the hash value and the value of the arrays elements are references to linked list (similar to the stacks above just with enhanced features). These linked lists store elements with the same hash. Of course it is done that way. Otherwise you'd be able to just save one element of a group with the same hash value. Now the trick... (the same as for ArrayList), even if there are a lot of values you can save inside a hash set and even if their hash values are huge (int), they start of with a small array holding the hash values. Let's say its size is 16. But hash values are ints and huge like 1947529490? How to use that value as index for the hash value array (oh, I forgot to mention, such an element of a hash value array is called a bucket). So how to use that 1947529490 as index? % SIZE ... that's it you do a modulus operation on that int and have a perfectly fitting result. An index from 0 to 15... 1947529490 % 16 So if you want to look up an element in a hash set, you first get it's hash value, then you check the bucket size, do the modulus bucket[hash % SIZE] and you have as result the head Node. Now you go through all the linked nodes till you find the searched element. If you reach the end of the linked list the element has not been found. 4. See above (3.) In the end this is probably a coder joke... to use a frame that is the solution to the task.

Lisa

Level 41

9 February 2022, 09:14

And the Stack... I think it is not that bad for a first try :) I also had a toString method in there. That helps to check the current state of the Stack (the post just will get to long if I include that, too). peek() I've stripped as well... but that should be no problem for you to add.

public class Stack<T> {
    private Node head = null;
    private static int size;

    private class Node {
        private T value;
        private Node last;

        public Node(T value, Node last) {
            this.value = value;
            this.last = last;
        }
    }

    // add an element (make it the new head)
    public void push(T value) {
        head = new Node(value, head);
        size++;
    }

    // get and remove last added element (the head)
    public T pop() {
        if (size == 0) return null;

        T retVal = head.value;
        head = head.last;
        size--;
        return retVal;
    }


    public boolean isEmpty() {
        return head == null;
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < 20; i++)
            s.push(i);

        System.out.println("Size after adding: " + s.size());

        System.out.println("Getting (pop) all elements: ");
        while (!s.isEmpty())
            System.out.println(s.pop());
    }
}

Justin Smith

Level 41 , Greenfield, USA, United States

9 February 2022, 11:49

I'm still really confused about using a hash value as the index. What if one object has a hash value of 29015370 and another object has a hash value of 4578345? If buckets.length is equal to 5, then both of these values % buckets.length would return 0. Wouldn't they point to the same index value then?

Lisa

Level 41

9 February 2022, 12:09

then you have more than one element in a bucket (connected using the linked list as mentioned above). The goal, as you have said, is, not to have to many elements in a bucked (working in that set would take to long. In the worst case all elements are in one bucket -> that's a degenerated hashset). To avoid that you check the number of elements in a bucket when adding a new element to the set. If the size is growing to big, you rehash. Means you create a new, a bigger hash array. Then you go through your old hash array and for each element you create a new hash for the new buckets length and add those rehashed elements to the new buckets. The above set is missing a few methods ;)

Justin Smith

Level 41 , Greenfield, USA, United States

9 February 2022, 12:23

Thank you for trying to explain this to me. I wish I could say I was understanding it more... When you say earlier "this is a hashset" what object in the code is "this" referring to? I think that's a big part of where I'm lost. Buckets and locks are both arrays, right?

Lisa

Level 41

9 February 2022, 12:37

this is referring to the Solution class. You have the bucket array, the key is the hash and its holding Nodes. The Node is an element of a linked data structure. The get method finds an element based on it's hash value. And don't worry. Data structures are not easy to understand and I can not explain that here in a just a few words. You probably need to read a (good) book if you want to know more. CG has some tasks about that later but unfortunately do not explain to much. The clue (why the CG guys added that surrounding code) is probably just the way you add elements to the buckets (the modulus thingie). That's just what they wanted to see. The rest is not important. Just decoration and the joke of course.