[HN Gopher] High Speed Hashing for Integers and Strings (2015)
       ___________________________________________________________________
        
       High Speed Hashing for Integers and Strings (2015)
        
       Author : PartiallyTyped
       Score  : 21 points
       Date   : 2021-02-12 10:48 UTC (1 days ago)
        
 (HTM) web link (arxiv.org)
 (TXT) w3m dump (arxiv.org)
        
       | listenallyall wrote:
       | I thought this was going to be about xxHash, which is awesome
        
       | zcw100 wrote:
       | Why is this a published paper? Someone should write a web service
       | that renders stackoverflow posts in latex so that colleagues
       | think I'm researching something complicated.
        
         | dkjaudyeqooe wrote:
         | It's a survey paper.
        
         | [deleted]
        
         | mattkrause wrote:
         | As the abstract says:
         | 
         | Some of the most practical hash functions have only appeared in
         | theory papers, and some of them requires combining results from
         | different theory papers. The goal here is to combine the
         | information in lecture-style notes that can be used by
         | theoreticians and practitioners alike, thus making these
         | practical fruits of theory more widely accessible.
         | 
         | Reviews are pretty common and while they might seem trivial,
         | writing a good one is an astonishing amount of work.
        
         | zokier wrote:
         | As far as I can tell, it's not published anywhere?
        
         | [deleted]
        
         | PartiallyTyped wrote:
         | It is not a published paper, but it appears you did not pay
         | much attention besides 'skimming' through (perhaps not even
         | that).
         | 
         | The tl:dr; is that certain non cryptographic hash functions
         | provide certain guarantees in different applications such as
         | signatures, expected runtimes on hashmaps, distributed sampling
         | and so on, it also shows some fast solutions with good
         | guarantees and explains the mathematics behind said guarantees.
         | 
         | The professor mentions in the document that the document exists
         | because modern textbooks do not go into detail on hashing.
         | 
         | The content in the document is sufficient for 1 or 2 lectures
         | on introduction to hashing. We spent 1 lecture during a
         | graduate course in Advanced Algorithms and Data-structures.
        
       | cb321 wrote:
       | Knuth, The Art Of Computer Programming V3, Sorting & Searching
       | covered both multiply & shift and modulo prime integer hashing in
       | some detail in its first edition written in the 1960s, published
       | in 1973. While not "modern", Knuth has always been a bona fide
       | classic, especially as regards hashing, and should really be
       | cited by this survey paper, IMO. (EDIT: people now call this
       | "Fibonacci Hashing" even though, in the source material itself,
       | Knuth mentions many irrational numbers will do, not just his
       | motivating choice of the golden ratio from Fibonacci numbers
       | fame. There are blog posts about it being "the optimization that
       | time forgot", etc.)
       | 
       | For not entirely clear reasons (maybe multiplier selection?),
       | only Knuth's modulo prime suggestion "propagated" well in the 70s
       | and 80s. This suggestion reception bias also aged poorly over
       | ensuing decades with the CPU cost of modulo vs. multiply evolving
       | from a 2x performance delta to more like 10x.
        
       | nanis wrote:
       | > last revised 9 May 2020 (this version, v9)]
        
       ___________________________________________________________________
       (page generated 2021-02-13 23:02 UTC)