#Need help with implementing hashSet

81 messages · Page 1 of 1 (latest)

violet salmon
# 
Option 1 is to avoid arrays and use an ArrayList instead. Then you can declare and create the hash table in the following way:

ArrayList<LinkedList<T>> table = new ArrayList<>();```

And then what I have is a method header for some methods, I need to implement, but where do I use ArrayList?
```java
public class HashSet<T> implements Set<T> {
    private List<T>[] table;
    
    /**
     * Creates a hash table with the given capacity (amount of buckets).
     *
     * @throws IllegalArgumentException if capacity <= 0.
     */
    public HashSet(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException(
                "capacity must be a positive, non-zero value! Provided: " + capacity);
        }
        @SuppressWarnings("unchecked") // for this declaration only
        List<T>[] t = new LinkedList[capacity];
        
        table = t;
    }

    /**
     * Adds the given element to the set.
     * @return true if the set did not contain the element, otherwise false.
     */
    public boolean add(T elem) {
       
        
    }
last juncoBOT
#

⌛ This post has been reserved for your question.

Hey @violet salmon! Please use /close or the Close Post button above when you're finished. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

violet salmon
#

Basically I really need help understanding how to begin

gusty willow
#

read this

copper turtle
#

hashset uses a hashmap internally

violet salmon
# gusty willow read this

I feel like I understand the concept behind it, but it is that I am confused when it comes to the implemenation. I just need help with starting it, as in maybe understand how and why and where I am gonna use arrayList? Isn't it enough with LinkedList?

violet salmon
copper turtle
#

a bucket holder

gusty willow
#

you can hash an object. Do you understand what is hashing?

violet salmon
# 
If you'd rather use arrays, for efficiency-reasons, some more unexpected issues pop up. You can't actually create an array of generic lists in a type-safe fashion in Java. The following, seemingly natural code:

new LinkedList<T>[size];
doesn't work. HashSet.java is a skeleton that shows how you can get around this.```
violet salmon
violet salmon
copper turtle
#

its dynamically resizable out of the hood maybe thats why they say

copper turtle
#

well

violet salmon
#

"table" variable I mean*

copper turtle
#

a hashmap uses linked nodes actually, but ye a linkedlist would work too

#

it uses a Node<K,V>[], which would translate to ArrayList<LinkedList<T>> in your case

violet salmon
#

Or the actual arrayList?

copper turtle
#

or LinkedList<T>[]

violet salmon
#

what type of list should table be?

copper turtle
#

i would be using an array

violet salmon
# copper turtle i would be using an array

I mean like I need to have a LinkedList no matter what to link the objects with hashcode that are congruent. But lets say I pick array as the outside list? Which list should the field "table" be? Now when I think about since they said that I can choose to have an array and an array is not a list. This means that the List "table" has then the roll of a linkedlist right?

copper turtle
#

LinkedList<T>[]?

violet salmon
#

Should I declare the array or the arraylist in the field or where should I have it? I am guessin in the field since I am gonna need to access since I will be implementing multiple methods?

violet salmon
violet salmon
#

anyone that can help?

proper mesa
#

In the code you provided, the table variable is declared as an array of List<T>. This is not what the suggested option 1 says to do, which is to use an ArrayList<LinkedList<T>>.

To implement this change, you need to change the declaration of the table variable to an ArrayList<LinkedList<T>> and initialize it as an empty ArrayList in the constructor:

private ArrayList<LinkedList<T>> table;

public HashSet(int capacity) {
    if (capacity <= 0) {
        throw new IllegalArgumentException(
            "capacity must be a positive, non-zero value! Provided: " + capacity);
    }

    table = new ArrayList<LinkedList<T>>();
    for (int i = 0; i < capacity; i++) {
        table.add(new LinkedList<T>());
    }
}```
Then in the add method, you can use the ArrayList to access and manipulate the linked lists.
violet salmon
proper mesa
#

yeah

violet salmon
#

so using hashcode I will generate the integer representation of the object right? I can't add an extra method that is not given. So then how do I do the module what ever this "%" is called to find it's index in the arrayList?

proper mesa
#

Yes, you can use the hashCode method to generate the integer representation of an object. You can then use the modulo operator (%) to reduce the value of the hash code to an index within the size of the ArrayList.

#

example:

public boolean add(T elem) {
    int hash = elem.hashCode();
    int index = hash % table.size();

    LinkedList<T> list = table.get(index);
    if (!list.contains(elem)) {
        list.add(elem);
        return true;
    }
    return false;
}
#

The index variable holds the position in the ArrayList where the element should be inserted or checked for existence. The list variable holds the reference to the linked list at that position in the ArrayList. By checking if the linked list at the index position contains the element, you can determine if the element already exists in the set. If the element does not exist, you can add it to the linked list.

worthy pilot
#

Keep in mind - when you hash an object, if two objects are considered equal, they should have the same hash.

#

(As defined in your equals method)

violet salmon
worthy pilot
#

If two objects are not equal, they probably do not have the same hash, but they might. If two objects are equal, they must have the same hash.

violet salmon
proper mesa
violet salmon
violet salmon
worthy pilot
#

Multiplying by 31 is just a way to try to get things that are not equal to have different hashes. That’s generally good to avoid collisions

violet salmon
#

I understand we only care about this index but like in general?

worthy pilot
#

There are other numbers besides 31, idk exactly the best numbers. But that’s generally why people do it

violet salmon
worthy pilot
#

The same thing happens with different hashes with collisions

violet salmon
worthy pilot
#

The data structures stuff is mostly for the theory, not the code.

#

The theory is the same in pretty much every language.

#

Implementation is just different

violet salmon
#

Alright I will check that out and thank you guys for the help

violet salmon
gusty willow
violet salmon
gusty willow
#

make sure you have sufficient initial capacity, so it won't resize automatically as you will be adding values, and it won't mess up with buckets 😉

#

oh nevermind, it shouldn't

violet salmon
gusty willow
#

better show the code

violet salmon
#

repost it?

gusty willow
#

you mean the one in the very first message?

#

there is array of lists

#

not arraylist of lists

violet salmon
# gusty willow you mean the one in the very first message? 
public class HashSet<T> implements Set<T> {
    private List<T>[] table;
    
    /**
     * Creates a hash table with the given capacity (amount of buckets).
     *
     * @throws IllegalArgumentException if capacity <= 0.
     */
    public HashSet(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException(
                "capacity must be a positive, non-zero value! Provided: " + capacity);
        }
        @SuppressWarnings("unchecked") // for this declaration only
        List<T>[] t = new LinkedList[capacity];
        
        table = t;
    }

    /**
     * Adds the given element to the set.
     * @return true if the set did not contain the element, otherwise false.
     */
    public boolean add(T elem) {
 int hashCode = elem.hashCode();
        int index = hashCode % table.size();
        LinkedList<T> indexList = table.get(index);
    
        if(!indexList.contains(elem)){
            indexList.add(elem);
            return true;
        }
        else{
            return false;
      
    }```
gusty willow
#

if you want to use option 2 (as it is in your code - you use array of lists) I would recommend you to cast raw type to List<T> like this:```java
List<T>[] t = (List<T>[])new LinkedList[capacity];

#

besides, why don't you assign it directly?

table = (List<T>[])new LinkedList[capacity];
violet salmon
gusty willow
#

instead of array or instead of LinkedList?

proper mesa
# violet salmon I tried implementing my method the way you said to, but the problem I am facing ...

Ah, I see what the issue is now. In the HashSet class, the table variable is declared as an array of List objects, but it is initialized as an array of LinkedList objects:

private List<T>[] table;

public HashSet(int capacity) {
    if (capacity <= 0) {
        throw new IllegalArgumentException(
            "capacity must be a positive, non-zero value! Provided: " + capacity);
    }

    @SuppressWarnings("unchecked") // for this declaration only
    List<T>[] t = new LinkedList[capacity];
    
    table = t;
}```
To use an ArrayList instead of a linked list array, you would need to change the declaration of the table variable and the initialization of t:
```java
private ArrayList<LinkedList<T>> table;

public HashSet(int capacity) {
    if (capacity <= 0) {
        throw new IllegalArgumentException(
            "capacity must be a positive, non-zero value! Provided: " + capacity);
    }

    table = new ArrayList<>(capacity);
    for (int i = 0; i < capacity; i++) {
        table.add(new LinkedList<T>());
    }
}```
And in the add method, you would retrieve the linked list at the specified index in the ArrayList as follows:
```java
public boolean add(T elem) {
    int hash = elem.hashCode();
    int index = hash % table.size();

    LinkedList<T> list = table.get(index);
    if (!list.contains(elem)) {
        list.add(elem);
        return true;
    }
    return false;
}
violet salmon
#

But if I use an array, do I still need to alter the HashSet method? The thing is I'm not sure if I'm allowed (usually not allowed) to alter anything else except the method header in teh interface. But if there is not other way of doing it(looks like there is no other way since you can't magically make two different type equal), I guess I'd need to alter it.

violet salmon
violet salmon
#

anyone?

proper mesa
#

If you're not allowed to change the declaration of the table variable or the constructor of the HashSet class, then you would need to use an array of linked lists instead of an ArrayList.

Here's an implementation of the add method using an array of linked lists:

public boolean add(T elem) {
    int hash = elem.hashCode();
    int index = hash % table.length;

    LinkedList<T> list = table[index];
    if (!list.contains(elem)) {
        list.add(elem);
        return true;
    }
    return false;
}

This implementation works the same way as the one using an ArrayList, but instead of using the get method to retrieve the linked list at the specified index, it uses the array indexing operator [] to access the linked list at that index in the table array.

proper mesa
# violet salmon Also why don't I need @SuppressWarnings("unchecked) anymore?

The @SuppressWarnings("unchecked") annotation was used in the original implementation to suppress the compiler warning that arises when using an array of a non-reifiable type, such as List<T>[]. In this new implementation, you are using an array of a concrete type, LinkedList<T>[], which is a reifiable type, so there's no need to use the @SuppressWarnings("unchecked") annotation anymore.