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>For your first question - why is the average time complexity of a lookup O(1)? - this statement is in general only true if you have a good hash function. An ideal hash function is one that causes a nice spread on its elements. In particular, hash functions are usually chosen so that the probability that any two elements collide is low. Under this assumption, it's possible to formally prove that the expected number of elements to check is O(1). If you search online for "universal family of hash functions," you'll probably find some good proofs of this result.</p>

<p>As for using placeholders - there are several different ways to implement a hash table. The approach you're using is called "closed addressing" or "hashing with chaining," and in that approach there's little reason to use placeholders. However, other hashing strategies exist as well. One common family of approaches is called "open addressing" (the most famous of which is linear probing hashing), and in those setups placeholder elements are necessary to avoid false negative lookups. Searching online for more details on this will likely give you a good explanation about why.</p>

<p>As for how this differs from HashMap, the HashMap is just one possible implementation of a map abstraction backed by a hash table. Java's HashMap does support nulls, while other approaches don't.</p>

python algorithm data-structures