> For the complete documentation index, see [llms.txt](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/data-structures/hash-table.md).

# Set

Hash set offers a data structure that offers complexity of `O(1)` to insert and obtain element from it. We need to be able to calculate hash or position of element based on its value.

> If you are interesting in sets, have a look at this [chapter in Java Handbook](https://ondrej-kvasnovsky.gitbooks.io/java-handbook/content/chapter1.html).

Here is a naive implementation of hash set.

```
class MyHashSet {

    private Integer[] values = new Integer[1000000];

    public void add(int key) {
        values[hash(key)] = key;
    }

    public void remove(int key) {
        values[hash(key)] = null;
    }

    /** Returns true if this set did not already contain the specified element */
    public boolean contains(int key) {
        return values[hash(key)] != null;
    }

    public int hash(int value) {
        return values.length % value;
    }
}
```

We can perform the following with the hash set we have created.

```
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);         
hashSet.add(2);         
hashSet.contains(1);    // returns true
hashSet.contains(3);    // returns false (not found)
hashSet.add(2);          
hashSet.contains(2);    // returns true
hashSet.remove(2);          
hashSet.contains(2);    // returns false (already removed)
```

## Advanced hashing and re-sizing hash set.

Lets create simple hash set to demonstrate how they are implemented. We can put couple of items into this hash set. If we would like to expand values array when more elements come, we would have to add more check and resizing. But this is omitted from this implementation for easier understanding.

```
import java.util.Arrays;

class HashSet {

    private String[] values;

    public HashSet() {
        values = new String[getMaxCapacity(10)];
    }

    public void put(String value) {
        int sizeMinusOne = values.length - 1;
        int position = sizeMinusOne & (value.hashCode() ^ (value.hashCode() >>> 16));
        values[position] = value;
    }

    public void remove(String value) {
        int sizeMinusOne = values.length - 1;
        int position = sizeMinusOne & (value.hashCode() ^ (value.hashCode() >>> 16));
        values[position] = null;
    }

    private int getMaxCapacity(int capacity) {
        int max = 1 << 30;
        int n = capacity - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= max) ? max : n + 1;
    }

    public int getCapacity() {
        return values.length;
    }

    public String toString() {
        return Arrays.toString(values);
    }
}
```

Now we can try to put and remove some elements.

```
public class HashSetDemo {

    public static void main(String[] args) {
        HashSet set = new HashSet();
        System.out.println(set.getCapacity());

        set.put("Hello");
        System.out.println(set);

        set.put("World");
        System.out.println(set);

        set.remove("World");
        System.out.println(set);

        set.put("123");
        System.out.println(set);

        set.put("1234");
        System.out.println(set);
    }
}
```

Observe how are the values placed in the array.

```
16
[null, null, null, null, Hello, null, null, null, null, null, null, null, null, null, null, null]
[null, null, null, null, Hello, null, null, null, null, null, null, null, World, null, null, null]
[null, null, null, null, Hello, null, null, null, null, null, null, null, null, null, null, null]
[null, null, 123, null, Hello, null, null, null, null, null, null, null, null, null, null, null]
[null, null, 123, null, Hello, 1234, null, null, null, null, null, null, null, null, null, null]
```

## Linked List to handle equals values but the same positions

```
import java.util.Arrays;

class NaiveSetTest {
    public static void main(String[] args) {
        NaiveSet<Integer> set = new NaiveSet();
        set.add(1);
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        set.add(5);
        set.add(6);
        set.add(7);
        set.add(8);
        System.out.println(set);

        set.remove(1);
        System.out.println(set);

        set.remove(5);
        System.out.println(set);

        set.remove(7);
        System.out.println(set);
    }
}

public class NaiveSet<E> {
    Entry<E>[] entries;
    int size = 10;

    NaiveSet() {
        entries = new Entry[size];
    }

    public void add(E value) {
        int position = calcPosition(value);
        if (entries[position] != null) {
            addIntoLinkedList(entries[position], value);
        } else {
            entries[position] = new Entry<>(value);
        }
    }

    private void addIntoLinkedList(Entry<E> entry, E value) {
        Entry<E> current = entry;
        while (current.next != null) {
            if (current.value.equals(value)) {
                return;
            }
            current = current.next;
        }
        if (!current.value.equals(value)) {
            current.next = new Entry<>(value);
        }
    }

    private int calcPosition(E value) {
        int hashCode = value.hashCode();
        if (hashCode == 0) {
            return 0;
        }
        return entries.length % hashCode;
    }

    public void remove(E value) {
        int position = calcPosition(value);
        if (entries[position] != null) {
            removeFromLinkedList(entries[position], value);
        } else {
            entries[position] = null;
        }
    }

    private void removeFromLinkedList(Entry<E> entry, E value) {
        Entry<E> previous = entry;
        Entry<E> current = entry.next;
        if (previous != null && current == null) {
            if (previous.value.equals(value)) {
                int position = calcPosition(value);
                entries[position] = null;
                return;
            }
        }
        if (previous.value.equals(value)) {
            int position = calcPosition(value);
            entries[position] = current;
            return;
        }
        while (current != null) {
            if (current.value.equals(value)) {
                previous.next = current.next;
            }
            previous = current;
            current = current.next;
        }
    }

    public String toString() {
        return Arrays.toString(entries);
    }
}

class Entry<E> {
    E value;
    Entry<E> next;

    Entry(E value) {
        this.value = value;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Entry<E> current = this;
        while (current != null) {
            sb.append(" -> ");
            sb.append(current.value);
            current = current.next;
        }
        return sb.toString();
    }
}
```

Here is the output.

```
[ -> 1 -> 2 -> 5,  -> 3,  -> 4 -> 8,  -> 7,  -> 6, null, null, null, null, null]
[ -> 2 -> 5,  -> 3,  -> 4 -> 8,  -> 7,  -> 6, null, null, null, null, null]
[ -> 2,  -> 3,  -> 4 -> 8,  -> 7,  -> 6, null, null, null, null, null]
[ -> 2,  -> 3,  -> 4 -> 8, null,  -> 6, null, null, null, null, null]
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ondrej-kvasnovsky-2.gitbook.io/algorithms/data-structures/hash-table.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.