You don't have to atomically update a hash table and the queue. You can first insert into the queue, then update the hash table.

The article does seem to make assumptions that there is a lockless hash table and a lockless queue. It clarified that the lockless queue need not support removal from the middle.