Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Reinventing the wheel. Date: Sat, 22 Feb 2020 14:06:59 -0800 Organization: A noiseless patient Spider Lines: 67 Message-ID: <86sgj2b7jw.fsf@linuxsc.com> References: <7ca1c103-6910-48ad-8eee-b2f47e7b1db0@googlegroups.com> <87v9o1as7k.fsf@bsb.me.uk> <87ftf4c1g0.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="a1e79922b2c02e9149a52088916eaff2"; logging-data="26227"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+uhY/oApJ+/y4XagCmpQh8/8EwjKXAq/c=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:AOQIGu0H2O7ldrfGQyKbvTIZ+W8= sha1:HUtyaQlEvuQTCMq7uYlri5xwaLA= Xref: csiph.com comp.lang.c:150165 Ben Bacarisse writes: > Bart writes: > >> On 20/02/2020 21:01, Ben Bacarisse wrote: >> >>> Bart writes: >>> >>>> A hashtable was my first thought. However, items need to removed >>>> when they are looked up. This would be problematic in the kind >>>> of hashtable I normally use. >>> >>> That's curious. What do you usually use that makes removal >>> problematic? >> >> Suppose a fragment of the hashtable already looks like this (index >> and value): >> >> .... >> 100 ABC >> 101 DEF >> 102 --- (free) >> .... >> >> Say that ABC and DEF both have the same hash value of 100 (modulo >> table size). Then in looking up DEF, 100 doesn't match, but 101 >> does - fine. >> >> But suppose that before looking up DEF, a successful lookup for ABC >> is done, which is then removed to result in: >> >> .... >> 100 --- (free) >> 101 DEF >> 102 --- (free) >> >> Now, you look up DEF, but location 100 is empty, a sign usually >> that what you're looking for doesn't exist. Lookup fails. > > Removal from a hash table using open addressing is a well-known > algorithm (actually there are two) so I probably would not call > implementing it "problematic", but it is certainly the most fiddly > part. I was imagining some design that made it well-neigh > impossible. > >> Maybe your hash algorithm is different, but with mine: >> >> * Starting at the first hash index: you compare successive entries >> until either a match or an empty slot is found (wrapping as >> needed). Empty means not found. > > If you do what's called lazy deletion (I did not know it had a name > until just now!) you delete by invalidating the entry while keeping > the entry marked as occupied. The search operation works exactly as > above (the invalidated entries won't match any valid key), but you > make a note of the first invalid-but-occupied slot you see on the > way. If the key is found, and there was an invalid-but-occupied > slot on the way, you move the entry to that slot just before the > return. That helps with lookup times, but it doesn't help with occupancy rate. If the hash table is never cleaned up, a long term steady state of adding and removing will eventually fill up the hash table with "occupied but invalid" tombstones (ie, besides the actual still-live entries). So there needs to be more than just marking a removed table entry with a tombstone (as I am used to calling them).