Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
An Introduction to Hashing in the Era of Machine Learning
In December 2017, researchers at Google and MIT published a provocative research paper about their efforts into “learned index structures”. The research is quite exciting, as the authors state in the abstract: “[…] we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work just
Minimal Perfect Hash-Tables in Common Lisp
Recently, my twitter pal @ifesdjeen wrote a line that resonated with me: "Looks like it's easier for people to read 40 blog posts than a single whitepaper." And although he used it in a negative context, I recognized it as a very precise (and, actually, positive) description of what a research engineer does: read a whitepaper (or a dozen, for what it's worth) and transform it into working code and
私が書いた最速のハッシュテーブル – PART 1 | POSTD
結局、やり出したら止まりません。私は以前、” I Wrote a Fast Hashtable（私が書いた高速なハッシュテーブル） “という記事と、それに次いで” I Wrote a Faster Hashtable（私が書いたより高速なハッシュテーブル） “という記事をブログにアップしましたが、今回ついに、最速のハッシュテーブルを書き上げました。これが意味するところは、ルックアップがどのハッシュテーブルよりも速いということです。それに加えて、挿入や削除も（最速とまではいかないまでも）非常に速く行えます。 秘訣は、探索回数の上限を設定したロビンフッドハッシュ法を使用することです。ある要素が、その理想的な位置からX数以上、離れた位置にある場合、テーブルを拡張することで、全ての要素が、その大きなテーブル内において、理想的な位置に近づくようにします。結果的に、このやり方は非常にうまくいきました。
I Wrote The Fastest Hashtable
I had to get there eventually. I had a blog post called “I Wrote a Fast Hashtable” and another blog post called “I Wrote a Faster Hashtable.” Now I finally wrote the fastest hashtable. And by that I mean that I have the fastest lookups of any hashtable I could find, while my inserts and erases are also really fast. (but not the fastest) The trick is to use Robin Hood hashing with an upper limit on
⚙ D27155 Merge strings using concurrent hash map (3rd try!)
Here is yet another different implementation of string merging algorithm. And this is faster than the previous two (https://reviews.llvm.org/D27146, https://reviews.llvm.org/D27152). ParallelStringTableBuilder implemented in this patch is a concurrent hash table specialized for string table creation. It doesn't support resizing, and you cannot do anything other than inserting strings into the buil
Klib — a generic library in C
{ "tiddlers": { "$:/Acknowledgements": { "title": "$:/Acknowledgements", "type": "text/vnd.tiddlywiki", "text": "TiddlyWiki incorporates code from these fine OpenSource projects:\n\n* [[The Stanford Javascript Crypto Library|http://bitwiseshiftleft.github.io/sjcl/]]\n* [[The Jasmine JavaScript Test Framework|http://pivotal.github.io/jasmine/]]\n* [[Normalize.css by Nicolas Gallagher|http://necolas
Hash Functions and Block Ciphers
I have a lot of material related to hashing. Definitions and my offerings: Hash functions for hash table lookup Error Correction Codes Noncryptographic Checksums A noncryptographic hardware hash One-way functions (cryptographic hash functions, digital signatures) Block Ciphers Random Number Generators Stream Ciphers My functions: LOOKUP3.C, for hash table lookup SpookyHash, for hash table lookup a
Home page, Bob Jenkins
AI is sometimes producing usable art now. Here's Bing Image Creator's bushwalking koalas. I had to specify the paper-cut style, otherwise it was unbearably cutesy. Here's Suno's song about a weatherman who makes up predictions, though I heavily edited the lyrics. How to become rich slowly: open a brokerage account with Schwab. Whenever you have savings add it to the account. Keep nearly 100% of th
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - ronomon/hash-table: Fast, reliable cuckoo hash table for Node.js.
Will .hashcode() return a different int due to compaction of tenure space?
Efficient Hash Tables on the GPU