Re: Reinventing the wheel.

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: Reinventing the wheel.
Date	2020-02-20 22:56 +0000
Organization	A noiseless patient Spider
Message-ID	<87ftf4c1g0.fsf@bsb.me.uk> (permalink)
References	<7ca1c103-6910-48ad-8eee-b2f47e7b1db0@googlegroups.com> <r2ml8q$614$1@news.albasani.net> <VRA3G.968213$4c1.653214@fx31.am4> <87v9o1as7k.fsf@bsb.me.uk> <pXC3G.440164$Uz.43777@fx32.am4>

Show all headers | View raw

Bart <bc@freeuk.com> writes:

> On 20/02/2020 21:01, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> 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.

The other way is the more obvious one of shuffling entries with the
same hash value down when you delete.

-- 
Ben.

Thread

Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-20 10:33 -0800
  Re: Reinventing the wheel. Bonita Montero <Bonita.Montero@gmail.com> - 2020-02-20 20:04 +0100
    Re: Reinventing the wheel. Bart <bc@freeuk.com> - 2020-02-20 19:11 +0000
      Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-20 21:50 +0100
      Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-20 21:01 +0000
        Re: Reinventing the wheel. Bart <bc@freeuk.com> - 2020-02-20 21:34 +0000
          Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-20 22:56 +0000
            Re: Reinventing the wheel. Bart <bc@freeuk.com> - 2020-02-21 00:34 +0000
            Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-21 09:40 +0100
            Re: Reinventing the wheel. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-02-22 14:06 -0800
  Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-20 20:06 +0100
    Re: Reinventing the wheel. Bonita Montero <Bonita.Montero@gmail.com> - 2020-02-20 20:08 +0100
    Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-20 12:46 -0800
      Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-20 13:55 -0800
        Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 00:12 -0500
          Re: Reinventing the wheel. scott@slp53.sl.home (Scott Lurndal) - 2020-02-21 16:16 +0000
            Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 09:20 -0800
              Re: Reinventing the wheel. jadill33@gmail.com - 2020-02-21 10:07 -0800
              Re: Reinventing the wheel. scott@slp53.sl.home (Scott Lurndal) - 2020-02-21 23:23 +0000
                Re: Reinventing the wheel. Richard Damon <Richard@Damon-Family.org> - 2020-02-21 18:41 -0500
                Re: Reinventing the wheel. scott@slp53.sl.home (Scott Lurndal) - 2020-02-22 16:20 +0000
                Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-22 10:33 -0800
                Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-22 15:00 -0500
                Re: Reinventing the wheel. Richard Damon <Richard@Damon-Family.org> - 2020-02-22 15:16 -0500
          Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 08:42 -0800
            Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-21 18:23 +0100
      Re: Reinventing the wheel. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-02-22 17:06 -0800
        Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-23 06:18 -0800
  Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-20 21:14 +0000
    Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 00:24 -0500
  Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 13:15 -0800
    Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-20 13:44 -0800
      Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 14:21 -0800
        Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 14:22 -0800
  Re: Reinventing the wheel. Robert Wessel <robertwessel2@yahoo.com> - 2020-02-20 15:19 -0600
    Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 00:28 -0500
  Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 23:27 -0800
    Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 23:52 -0800
  Re: Reinventing the wheel. jadill33@gmail.com - 2020-02-21 08:20 -0800
  Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-22 03:15 -0800
    Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-22 10:38 -0800
      Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-24 02:50 -0800
        Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-24 16:36 +0000
          Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-25 04:08 -0800
            Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-25 13:42 +0100
              Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-25 05:00 -0800
                Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-26 10:53 +0100
          Re: Reinventing the wheel. chad <cdalten@gmail.com> - 2020-02-26 06:51 -0800
    Re: Reinventing the wheel. Anton Shepelev <anton.txt@gmail.com> - 2020-02-24 22:40 +0300
      Re: Reinventing the wheel. Robert Wessel <robertwessel2@yahoo.com> - 2020-02-24 16:37 -0600
        Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-25 01:37 -0800
          Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-25 13:07 +0300
            Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-25 04:50 -0800
              Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-25 19:30 +0300
                Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-25 08:43 -0800
                Re: Reinventing the wheel. Anton Shepelev <anton.txt@gmail.com> - 2020-02-29 01:25 +0300
              Re: Reinventing the wheel. Robert Wessel <robertwessel2@yahoo.com> - 2020-02-25 15:40 -0600
                Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-26 13:40 +0300
            Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-25 11:29 -0800
              Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-26 13:47 +0300
                Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-26 09:32 -0500
                Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-26 21:26 +0300
  Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-22 23:32 -0800
    Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-03-07 22:22 -0800
      Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-03-07 22:38 -0800

csiph-web