Is my understanding of Hashsets correct?(Python)
<p>I'm teaching myself data structures through this python book and I'd appreciate if someone can correct me if I'm wrong since a hash set seems to be extremely similar to a hash map.</p>

<p><strong>Implementation:</strong>
A Hashset is a list [] or array where each index points to the head of a linkedlist</p>

<p>So some hash(some_item) --> key, and then list[key] and then  add to the head of a LinkedList. This occurs in O(1) time</p>

<p>When removing a value from the linkedlist, in python we replace it with a placeholder because hashsets are not allowed to have Null/None values, correct?</p>

<p>When the list[] gets over a certain % of load/fullness, we copy it over to another list</p>

<p><strong>Regarding Time Complexity Confusion:</strong>
So one question is, why is Average search/access O(1) if there can be a list of N items at the linkedlist at a given index?</p>

<p><strong>Wouldnt the average case be the searchitem is in the middle of its indexed linkedlist so it should be O(n/2) -> O(n)?</strong></p>

<p>Also, when removing an item, if we are replacing it with a placeholder value, isn't this considered a waste of memory if the placeholder is never used?</p>

<p>And finally, what is the difference between this and a HashMap other than HashMaps can have nulls? And HashMaps are key/value while Hashsets are just value?</p>

<p>The lookup time wouldn't be <code>O(n)</code> because not all items need to be searched, it also depends on the number of buckets. More buckets would decrease the probability of a collision and reduce the chain length.</p>

<p>The number of buckets can be kept as a constant factor of the number of entries by resizing the hash table as needed. Along with a hash function that evenly distributes the values, this keeps the expected chain length bounded, giving constant time lookups.</p>

<p>The hash tables used by hashmaps and hashsets are the same except they store different values. A hashset will contain references to a single value, and a hashmap will contain references to a key and a value. Hashsets can be implemented by delegating to a hashmap where the keys and values are the same.</p>

python algorithm data-structures