Implement a Set Data Structure with a Resizable Array, Then Improve It with Hashing

Problem Statement

Implement an integer set data structure, CustomHashSet, from scratch without using any built-in hash-based containers (such as Python's set or dict, Java's HashSet or HashMap, or C++'s std::unordered_set).

Your implementation should back its storage with an array and handle collisions using either separate chaining (e.g., linked list buckets) or open addressing (e.g., linear probing). Additionally, to maintain O(1) average time complexity, your set must dynamically resize (rehash) when the load factor exceeds a defined threshold.

Implement the following methods:

• add(key: int) -> bool: Inserts key into the set. Returns True if key was not already present, or False if it was already in the set.
• remove(key: int) -> bool: Removes key from the set. Returns True if key was present and removed, or False otherwise.
• contains(key: int) -> bool: Returns True if key is present in the set, and False otherwise.
• size() -> int: Returns the total number of unique elements currently in the set.

Rehashing Requirements

• Initialize with an internal capacity of at least 8 or 16 buckets.
• Maintain a maximum load factor of 0.75 (load_factor = size / capacity). When inserting an element causes size / capacity > 0.75, double the internal array capacity and rehash all existing elements.

Class Interface

class CustomHashSet:
    def __init__(self):
        pass

    def add(self, key: int) -> bool:
        pass

    def remove(self, key: int) -> bool:
        pass

    def contains(self, key: int) -> bool:
        pass

    def size(self) -> int:
        pass

Examples

Example 1

my_set = CustomHashSet()
my_set.add(1)       # returns True
my_set.add(2)       # returns True
my_set.add(1)       # returns False (already present)
my_set.contains(1)  # returns True
my_set.contains(3)  # returns False
my_set.size()       # returns 2
my_set.remove(2)    # returns True
my_set.contains(2)  # returns False
my_set.size()       # returns 1

Constraints

• -10^9 <= key <= 10^9
• At most 10^5 calls will be made in total across all operations.
• You may not use built-in set, map, or hash table data structures.
• Average time complexity per operation should be O(1). Worst-case time complexity without rehashing can be O(n) on hash collisions.
• Space complexity should be O(n + capacity).

Edge Cases to Consider

• Handling negative integer keys in hash index computations (e.g., hash(key) % capacity must map to a non-negative index).
• Deletions when using open addressing: avoid breaking probe chains by using tombstone markers (or use separate chaining).
• Large volumes of duplicate insertions should not trigger unnecessary resizing.