Robin Hood Hashing (Papers We Love SF August 2017)
Robin Hood Hashing (1986) provided a breakthrough algorithm for storing data in hash tables, and has a really cool name. These slides were presented at the Papers We Love, Too meetup in San Francisco.
Robin Hood Hashing (1986) resolving collisions: open addressing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL 2 4 0 4 5 9 6 8 LEIA:ALDERAAN HAN:CORELLIA + REY:JAKKU LUKE:TATTOOINE + FINN:CORUSCANT+ CHEWIE:KASHYYK LANDO:BESPIN MAUL:DATHOMIR
10 Robin Hood Hashing (1986) data 6 slots away from ideal LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA + REY:JAKKU LUKE:TATTOOINE + FINN:CORUSCANT+ CHEWIE:KASHYYK+ LANDO:BESPIN+ MAUL:DATHOMIR+ WICKET:ENDOR LEIA:ALDERAAN
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 REY:JAKKU 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 REY:JAKKU 0 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 FINN:CORUSCANT 1 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 FINN:CORUSCANT 1 CHEWIE:KASHYYK 0 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 FINN:CORUSCANT 1 CHEWIE:KASHYYK 0 LANDO:BESPIN 1 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 FINN:CORUSCANT 1 CHEWIE:KASHYYK 0 LANDO:BESPIN 1 MAUL:DATHOMIR 0 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 FINN:CORUSCANT 1 CHEWIE:KASHYYK 0 LANDO:BESPIN 1 MAUL:DATHOMIR 0 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 WICKET:ENDOR 2 CHEWIE:KASHYYK 0 LANDO:BESPIN 1 MAUL:DATHOMIR 0 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 WICKET:ENDOR 2 CHEWIE:KASHYYK 0 FINN:CORUSCANT 2 MAUL:DATHOMIR 0 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 WICKET:ENDOR 2 CHEWIE:KASHYYK 0 FINN:CORUSCANT 2 LANDO:BESPIN 2 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 WICKET:ENDOR 2 MAUL:DATHOMIR 1 FINN:CORUSCANT 2 LANDO:BESPIN 2 LEIA:ALDERAAN 0
10 Robin Hood Hashing (1986) data stored in an array with robin hood hashing LEIA HAN REY LUKE FINN CHEWIE LANDO MAUL WICKET 2 4 0 4 5 9 6 8 4 HAN:CORELLIA 0 REY:JAKKU 0 LUKE:TATTOOINE 1 WICKET:ENDOR 2 MAUL:DATHOMIR 1 FINN:CORUSCANT 2 LANDO:BESPIN 2 LEIA:ALDERAAN 0 CHEWIE:KASHYYK 1
(1986 original paper) ‣ Robin Hood Hashing with Linear Probing paper (2005) ‣ Paul Khuong experimenting with hashing options (2009) ‣ Paul’s follow-up and conclusions (2011) ‣ Sebastian Sylvan saying robin hood should be the default (2013) ‣ Sebastian following up on slowness after deletions (2013) ‣ Emmanuel Goossaert benchmarking in C++ (2013) ‣ Paul Kuhong again, on linear probing for performance (2013) ‣ Emmanuel benchmarking again after tweaking deletions (2013)