Article View: pl.comp.lang.c
Article #308663Re: Szukam dobrej funkcji hash
From: M.M.
Date: Sat, 11 Jun 2016 16:49
Date: Sat, 11 Jun 2016 16:49
30 lines
2372 bytes
2372 bytes
On Saturday, June 11, 2016 at 2:37:48 PM UTC+2, Borneq wrote:
> W dniu 11.06.2016 o 14:23, Borneq pisze:
> > Musi być:
> > - prostsza od CRC
> > - szybka
> > - dosyć mało kolizji, różniąca się dla podobnych ciągów
> > - szybko działająca w kodzie C/C++ a nie assemblera i MMX
>
> Będę korzystał z FNV-1: http://isthe.com/chongo/tech/comp/fnv/
> ale mam pytanie: Hasz wymagany do unordered_map ma byc liczbą size_t,
> która ma 32 lub 64 bity. Od tego zależy liczba FNV_prime. Jak
> skompilować warunkowo dla 32 lub 64 bitów lub zależnie od sizeof(size_t)?
> To chyba prosto:
> if (sizeof(size_t) != 8)
> printf("4");
> else
> printf("8");
Co myślicie o takiej? Na pewno jest bardzo szybka:
uint64 keys[256] = {random_values};
uint64 mkHash( unsigned char begin[] , unsigned size ) {
uint64 hash = 0;
for( unsigned i=0 ; i<size ; i++ )
hash ^= keys[ (data[i]+hash) & 0xFF ];
return hash;
}
Pozdrawiam
Technical Details
Message-ID:
<b2ac56c5-ee76-4c02-8d29-0fbc37db26ff@googlegroups.com>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!news.unit0.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!peer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!p34no5524124qgp.1!news-out.google.com!107ni258qgx.1!nntp.google.com!v48no594167qgd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mailReferences:
<njgvse$2qm$1@node1.news.atman.pl> <njh0mr$3n1$1@node1.news.atman.pl>Show Full Headers
Complete Article Headers
X-Received: by 10.140.225.207 with SMTP id v198mr5584922qhb.6.1465663753210; Sat, 11 Jun 2016 09:49:13 -0700 (PDT) X-Received: by 10.36.213.134 with SMTP id a128mr130557itg.8.1465663753153; Sat, 11 Jun 2016 09:49:13 -0700 (PDT) Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!news.unit0.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!peer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!p34no5524124qgp.1!news-out.google.com!107ni258qgx.1!nntp.google.com!v48no594167qgd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: pl.comp.lang.c Date: Sat, 11 Jun 2016 09:49:12 -0700 (PDT) In-Reply-To: <njh0mr$3n1$1@node1.news.atman.pl> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=178.37.232.66; posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj NNTP-Posting-Host: 178.37.232.66 References: <njgvse$2qm$1@node1.news.atman.pl> <njh0mr$3n1$1@node1.news.atman.pl> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <b2ac56c5-ee76-4c02-8d29-0fbc37db26ff@googlegroups.com> Subject: Re: Szukam dobrej funkcji hash From: "M.M." <mmarszik@gmail.com> Injection-Date: Sat, 11 Jun 2016 16:49:13 +0000 X-Received-Bytes: 2224 X-Received-Body-CRC: 3200102652 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit