Implementing a HashSet

[lament palm]

tried implementing Hashset using an array and LinkedList, need suggestions if this right way to do it

[nova pollen]

<@&987246399047479336> please have a look, thanks.

[nova pollen]

While you are waiting for getting help, here are some tips to improve your experience:

Code is much easier to read if posted with syntax highlighting and proper formatting.

If nobody is calling back, that usually means that your question was not well asked and hence nobody feels confident enough answering. Try to use your time to elaborate, provide details, context, more code, examples and maybe some screenshots. With enough info, someone knows the answer for sure.

Don't forget to close your thread using the command </help-thread close:1027500463647621170> when your question has been answered, thanks.

[lament palm]

public class HashTable {
  private final LinkedList<String>[] array;
  private int size = 0;
  private final int DEFAULT_LENGTH = 10;

  public HashTable() {
    array = new LinkedList[DEFAULT_LENGTH];

    for (int i = 0; i < DEFAULT_LENGTH; i++) {
      array[i] = new LinkedList<>();
    }

  }


  public boolean add(String val) {

    if (!contains(val)) {
      int hash = val.hashCode();
      int index = hash % array.length;
      array[index].add(val);
      size++;
      return true;
    }

    return false;
  }
}```

[grand fjord]

Seems pretty good

Note that hashtables switch from linkedlists to trees if the no of elements in that node exceed 9

U can implement that if you wish to

[lament palm]

what if we were to increase the size of array? that should reduce the number of collisions or is it for larger number of inputs?

[flat carbon]

It looks good in terms of functionality, just remember to make DEFAULT_LENGTH static

[flat carbon]

Increasing the size of the array can help reduce the number of collisions and improve the performance actually (because there's more buckets to reduce the collisions)

[lament palm]

right that slipped my mind, thanks

[lament palm]

not familiar with trees implementation yet, so this should come handy 🙂

[flat carbon]

You can look at HashMap as that does, it switches to a balanced binary tree from a linkedlist

it does that because its faster to search through i.e. O(log n) vs O(n) at some overhead cost (which I think is slower insertions and removals?)

[lament palm]

i'll look at HashMap's source code, trees are on my list. For now can't really comment on that😅

[flat carbon]

Yeah that's fine, hopefully you have some things to look into now

[lament palm]

are you good with trees?

[flat carbon]

not really

forgotten most of it since uni lol

[lament palm]

i have mostly struggled with understand trees, i mean i understand the basic concepts like how it's all functioning just still find myself struggling to get comfortable around it

at best i think i may have solved like 3 problems on it

[grand fjord]

yes it would

actually it depends on the class

[flat carbon]

binary tree is pretty straightforward

[grand fjord]

how the hashcodes are scatterred

[flat carbon]

        1
       / \
      2   3
     / \   \
    4  5    6

[grand fjord]

yes that's right, i wasn't sure if it used a binary tree or a trie

[lament palm]

so a better algo for hashing would matter as well

[grand fjord]

yes that too

hash map does this

the xor would scatter the hashes by quite a lot

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
```It then converts an LL to a Binary tree like this

and note that it uses a singly linked list, doubly is not needed here

[lament palm]

what does treeify(tab) does here?

[flat carbon]

transforms any unbalanced subtrees into balanced ones

starting from the head, it does it recursively

[lament palm]

ah