Advanced techniques to implement fast hash tables | Attractive Chaos
Array and hash table are probably the most important data structures. Some programming languages such as Perl, Lua and Javascript, almost build the language core on top of the two data structures. While array is straightforward to implement, hash table is not. This is why we have paid continuous efforts in improving the hash table performance. This blog post reviews recent techniques not commonly
Gimli: Intro
Gimli is a 384-bit permutation designed to achieve high security with high performance across a broad range of platforms, including 64-bit Intel/AMD server CPUs, 64-bit and 32-bit ARM smartphone CPUs, 32-bit ARM microcontrollers, 8-bit AVR microcontrollers, FPGAs, ASICs without side-channel protection, and ASICs with side-channel protection. Contributors (alphabetical order) Daniel J. Bernstein, U
SipHash in the kernel [LWN.net]
A hash function performs a one-way computation on a set of data, producing a set of bytes that, one hopes, is effectively random and which cannot be used to derive the input data. The kernel uses hash functions in numerous places for everything from the generation of security-sensitive sequence numbers to the implementation of hash tables. The security of those functions is increasingly in doubt,
Multiformats
Self-describing hashes Multihash is a protocol for differentiating outputs from various well-established hash functions, addressing size + encoding considerations. It is useful to write applications that future-proof their use of hashes, and allow multiple hash functions to coexist. Safer, easier cryptographic hash function upgrades The Multihash Format Implementations Examples F.A.Q. About Specif
TommyDS
TommyDS is a C library of hashtables and tries designed to store and find objects with high performance. It's faster than all the similar libraries like rbtree, judy, googlebtree, stxbtree, khash, uthash, nedtrie, judyarray, concurrencykit, and others. Only googledensehash is a real competitor for TommyDS. See the benchmarks for some nice graphs. The data structures provided are: tommy_list - A do
GitHub - Cyan4973/xxHash: Extremely fast non-cryptographic hash algorithm
The following macros can be set at compilation time to modify libxxhash's behavior. They are generally disabled by default. XXH_INLINE_ALL: Make all functions inline, implementation is directly included within xxhash.h. Inlining functions is beneficial for speed, notably for small keys. It's extremely effective when key's length is expressed as a compile time constant, with performance improvement
Password Hashing Competition
and our recommendation for hashing passwords: Argon2 Password hashing is everywhere, from web services' credentials storage to mobile and desktop authentication or disk encryption systems. Yet there wasn't an established standard to fulfill the needs of modern applications and to best protect against attackers. We started the Password Hashing Competition (PHC) to solve this problem. PHC ran from 2
Rolling hash - Wikipedia
A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input. A few hash functions allow a rolling hash to be computed very quickly—the new hash value is rapidly calculated given only the old hash value, the old value removed from the window, and the new value added to the window—similar to the way a movi
tT4l8 - created on 3v4l.org
<?php var_dump(md5('240610708') == md5('QNKCDZO')); var_dump(md5('aabg7XSs') == md5('aabC9RqS')); var_dump(sha1('aaroZmOk') == sha1('aaK1STfY')); var_dump(sha1('aaO8zKZF') == sha1('aa3OFF9m')); var_dump('0010e2' == '1e3'); var_dump('0x1234Ab' == '1193131'); var_dump('0xABCdef' == ' 0xABCdef'); Output for 7.0.0 - 7.0.33, 7.1.0 - 7.1.33, 7.2.0 - 7.2.34, 7.3.0 - 7.3.33, 7.4.0 - 7.4.33, 8.0.0 - 8.0.30
A Fast, Minimal Memory, Consistent Hash Algorithm ご紹介(システム系論文紹介 Advent Calendar 2014）. - Qiita
A Fast, Minimal Memory, Consistent Hash Algorithm ご紹介(システム系論文紹介 Advent Calendar 2014）.hashシステム系論文紹介分散ストレージjumpconsistenthash (本稿は, システム系論文紹介 Advent Calendar 2014, 12/20 です http://www.adventar.org/calendars/440) 論文は arXiv から取得できます. http://arxiv.org/abs/1406.2294 Jump Consitent Hash と呼ばれる, 分散ストレージ系で有益なハッシュ関数を求めるアルゴリズムです. 現在史上最強のハッシュアルゴリズムのひとつと言えるでしょう. 無性に分散ストレージライブラリを作りたくなってきますね! 共著者の Eric Veach にも注
A Fast, Minimal Memory, Consistent Hash Algorithm
We present jump consistent hash, a fast, minimal memory, consistent hash algorithm that can be expressed in about 5 lines of code. In comparison to the algorithm of Karger et al., jump consistent hash requires no storage, is faster, and does a better job of evenly dividing the key space among the buckets and of evenly dividing the workload when the number of buckets changes. Its main limitation is
Feature Hashingを試す - Negative/Positive Thinking
はじめに Feature Hashingについて気になったことがあったので試してみた。 Feature Hashingとは Hashing trick ハッシュ関数を使って、素性群をM次元ベクトルにする 一種の次元圧縮 Bag of wordsなどの素性をそのままハッシュ値にすることで、素性とIDのペアの辞書などが必要なくなる スパムフィルタでは、新語やミススペルでフィルタ回避されてしまうと対応すべき語が増え続ける(辞書が大きくなる)問題などに使える ベクトルの作り方 いくつか提案されているが、各素性のhash値を計算してmod Mをとったインデクスの所に入れるものとしては主に2つがあるようなので、メモしておく。 Shiらの方法 Shiら(2009) 値をunsigned sumする φ_i (x) = Σ_{ j:h(j)=i } x_j h : ハッシュ関数 Weinbergerらの方
GitHub - efficient/cuckoofilter
Cuckoo filter is a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient data structures to serve queries like "if item x is in a set?", they do not support deletion. Their variances to enable deletion (like counting Bloom filters) usually require much more space. Cuckoo filters provide the flexibility to add and remove items dynamically
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - skarupke/flat_hash_map: A very fast hashtable
GitHub - rhash/RHash: Great utility for computing hash sums
GitHub - jedisct1/libsodium: A modern, portable, easy to use crypto library.
TLS徹底演習
GitHub - efficient/libcuckoo: A high-performance, concurrent hash table
GitHub - preshing/junction: Concurrent data structures in C++
Hashing Representations