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>A lot has been written here about open hash tables, but some fundamental points are missed.</p>

<p>Practical implementations generally have O(1) lookup and delete because they guarantee buckets won't contain more than a fixed number of items (the <em>load factor</em>). But this means they can only achieve <em>amortized</em> O(1) time for insert because the table needs to be reorganized periodically as it grows. </p>

<p>(Some may opt to reorganize on delete, also, to shrink the table when the load factor reaches some bottom threshold, gut this only affect space, not asymptotic run time.)</p>

<p>Reorganization means increasing (or decreasing) the number of buckets and re-assigning all elements into their new bucket locations. There are schemes, e.g. <em>extensible hashing</em>, to make this a bit cheaper. But in general it means touching each element in the table.</p>

<p>Reorganization, then, is O(n). How can insert be O(1) when any given one may incur this cost? The secret is amortization and the power of powers.  When the table is grown, it <em>must</em> be grown by a <em>factor</em> greater than one, two being most common.  If the table starts with 1 bucket and doubles each time the load factor reaches F, then the cost of N reorganizations is</p>

<pre><code>F + 2F + 4F + 8F ... (2^(N-1))F = (2^N - 1)F
</code></pre>

<p>At this point the table contains <code>(2^(N-1))F</code> elements, the number in the table during the last reorganization. I.e. we have done <code>(2^(N-1))F</code> inserts, and the total cost of reorganization is as shown on the right.  The interesting part is the <em>average</em> cost per element in the table (or insert, take your pick):</p>

<pre><code>(2^N - 1)F      2^N
---------- ~= ------- = 2
(2^(N-1))F    2^(N-1)
</code></pre>

<p><em>That's</em> where the amortized O(1) comes from.</p>

<p>One additional point is that for modern processors, linked lists aren't a great idea for the bucket lists. With 8-byte pointers, the overhead is meaningful. More importantly, heap-allocated nodes in a single list will almost never be contiguous in memory.  Traversing such a list kills cache performance, which can slow things down by orders of magnitude. </p>

<p>Arrays (with an integer count for number of data-containing elements) are likely to work out better. If the load factor is small enough, just allocate an array equal in size to the load factor at the time the first element is inserted in the bucket. Otherwise, grow these element arrays by factors the same way as the bucket array! Everything will still amortize to O(1).</p>

<p>To delete an item from such a bucket, don't mark it deleted. Just copy the last array element to the location of the deleted one and decrement the element count. Of course this won't work if you allow external pointers into the hash buckets, but that's a bad idea anyway.</p>

python algorithm data-structures