hashing   3276

« earlier    

David Ashby on SHA256 [PWL NYC] - YouTube
Welcome to the GDC YouTube channel, where you'll find clips and full length videos from GDC -- www.gdconf.com GDC is the world's largest professional game in...
sha256  hashing  algorithm 
14 days ago by mac
Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo) | Probably Dance
Fibonacci hashing solves both of these problems. 1. It’s really fast. It’s a integer multiplication followed by a shift. It takes roughly 1.5 nanoseconds on my machine, which is fast enough that it’s getting real hard to measure. 2. It mixes up input patterns. It’s like you’re getting a second hashing step for free after the first hash function finishes. If the first hash function is actually just the identity function (as it should be for integers) then this gives you at least a little bit of mixing that you wouldn’t otherwise get. But really it’s better because it’s faster. When I worked on hash tables I was always frustrated by how much time we are spending on the simple problem of “map a large number to a small number.” It’s literally the slowest operation in the hash table.
hashing  compsci  computerscience 
16 days ago by dlkinney
Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo)
Turns out I was wrong. This is a big one. And everyone should be using it. Hash tables should not be prime number sized and they should not use an integer modulo to map hashes into slots. Fibonacci hashing is just better. Yet somehow nobody is using it and lots of big hash tables (including all the big implementations of std::unordered_map) are much slower than they should be because they don’t use Fibonacci Hashing.


Apparently this is binary multiplicative hashing, and Google's brotli, webp, and Snappy libs all use a constant derived heuristically from a compression test corpus along the same lines (see comments).

(Via Michael Fogleman)
algorithms  hashing  hash  fibonacci  golden-ratio  coding  hacks  brotli  webp  snappy  hash-tables  hashmaps  load-distribution 
4 weeks ago by jm
Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo) | Probably Dance
Turns out I was wrong. This is a big one. And everyone should be using it. Hash tables should not be prime number sized and they should not use an integer modulo to map hashes into slots. Fibonacci hashing is just better. Yet somehow nobody is using it and lots of big hash tables (including all the big implementations of std::unordered_map) are much slower than they should be because they don’t use Fibonacci Hashing. So let’s figure this out.
cs  hashing 
4 weeks ago by euler

« earlier    

related tags

****  algorithm  algorithms  architecture  argon2  article  attention  b-tree  bcrypt  bear  blockchain  brotli  bytell_hash_map  c++  c  castle  cave  checksum  code  coding  commandline  comparison  compsci  computer-science  computerscience  consistent-hashing  consistent  consistent_hashing  crypto  cryptography  cs  css  data_structures  database  databases  datascience  datastores  datastructure  datastructures  ddos  design  detection  dev  dht  distributed  distributed_computing  documentation  duplicate  encryption  explanation  fibonacci  forensics  fuzzy  gdpr  github  go  golang  golden-ratio  google  hacks  hangover  hash-tables  hash  hashmaps  hashtable  hood  image  imageanalysis  indexes  indexing  java  javascript  key-value  learned  learning  library  libsodium  load-distribution  loadbalancing  locality  lsh  machine-learning  machine_learning  machinelearning  map  math  md5  merkle  michael-mitzenmacher  minimal  minimal_perfect_hashing  ml  module  new  number-theory  numpy  opensource  package  paper  password  passwords  perfect  performance  photo  photodna  picture  postcss  postquantum  primer  probability  programming  pycrypto  pynacl  python  rabbit  randomness  reference  research-article  research  robin  rust  salt  salting  scaling  security  sensitive  sha1  sha256  sharding  shirt  slicing  snappy  software  solution  song  stackoverflow  storage  strings  toread  trail  trees  tries  tutorial  utility  va  video  webp  webpack  wikipedia  windows 

Copy this bookmark:



description:


tags: