あなたの知らないハッシュテーブルの世界Please select the category that most closely reflects your concern about the presentation, so that we can review it and determine whether it violates our Terms of Use or isn't appropriate for all viewers.
Hopscotch hashing - Wikipedia
Hopscotch hashing. Here, H is 4. Gray entries are occupied. In part (a), the item x is added with a hash value of 6. A linear probe finds that entry 13 is empty. Because 13 is more than 4 entries away from 6, the algorithm looks for an earlier entry to swap with 13. The first place to look in is H−1 = 3 entries before, at entry 10. That entry's hop information bit-map indicates that d, the item at
Jean-Philippe Aumasson
Cryptographer, co-founder & chief security officer @ Taurus. Books Serious Cryptography (No Starch Press, 2017) Translations' covers 🚧 Second edition: to appear in 2024 (No Starch Press) 🚧 French translation: to appear in 2024 (Dunod) Petit Pingouin (self-published, 2021) Crypto Dictionary (No Starch Press, 2020) The Hash Function BLAKE (Springer, 2014) Crypto projects Hash functions BLAKE, BLAK
ruby 1.9 におけるハッシュ飽和攻撃による DoS 脆弱性 (CVE-2012-5371)
Posted by usa on 9 Nov 2012 ruby 1.9 系列で使用しているハッシュ関数について、ハッシュ飽和攻撃によってサービスを停止させることができる脆弱性が報告されました。 この脆弱性は 1.8.7 に対して公表された CVE-2011-4815 とは異なるものです。 全ての ruby 1.9 ユーザーは、この問題に対するセキュリティフィックスが含まれた ruby-1.9.3 patchlevel 327 に更新することが推奨されます。 影響 綿密に構築された文字列の並びをサーバーに対して送信することにより、そのサーバーがこの文字列の並びを文字列をキーとした Hash オブジェクトの生成に利用する場合、サービス停止攻撃が成立します。 例えば、信頼できない送信元から送られた JSON データを解釈する Web アプリケーションなどがこの脆弱性の影響を受けます。 詳細 こ
データ分散とインデックス最適化のためのハッシュ関数の利用 - Articles Advent Calendar 2011 Hacker
はじめに こんにちは、piarra です。みなさん、意識は高まっていますか？私は上々です。 という書き出しをやめたくてやめられなかったのが心残りです。 昨年までは、Casual Trackで寄稿させていただいていましたが、今年はYAPCで話したこともあり、Hacker Trackに初挑戦させていただきます。得意のMD5暗算法とその習得法について解説したいと思っていたところですが、より日常に役立つ方がよいかと思い、MD5やその他のハッシュ関数の活用法について少し触れてみたいと思います。 データサンプル DBMSを考慮せず、以下のようなデータサンプルがあったと考えてみましょう。 +----+-----------------------+ | id | url | +----+-----------------------+ | 1 | http://www.google.com | | 2
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
GitHub - google/cityhash: Automatically exported from code.google.com/p/cityhash
CityHash, a family of hash functions for strings. Introduction ============ CityHash provides hash functions for strings. The functions mix the input bits thoroughly but are not suitable for cryptography. See "Hash Quality," below, for details on how CityHash was tested and so on. We provide reference implementations in C++, with a friendly MIT license. CityHash32() returns a 32-bit hash. CityHash
Google製ハッシュアルゴリズム「CityHash」が登場 - CtrlShift.net
IT業界の動向、ソフトウェア開発技術、ネットの情報、アイデアをまとめて配信Googleが新しいハッシュ・アルゴリズム「CityHash」を考案したようです。 Introducing CityHash - Google Open Source Blog このハッシュ・アルゴリズムを考案したGoogle社員は、「Geoff Pike」氏と「Jyrki Alakuijala」氏で共にSoftware Engineering Teamに所属しているようです。 「CityHash」は特に文字列に対して有効なハッシュ・アルゴリズムで、文字列から64bit、128bitへのハッシュを生成してくれます。 このアルゴリズムは暗号化処理などに向いているわけではないそうですが、ハッシュ・テーブル用として有効だそうです。 もともと「Austin Appleby」氏が考案した「MurmurHash」というハッシュ・
C/C++ で使える Hashtable - いけむランド
Java のように豊富なライブラリを標準で提供している開発言語を使い慣れてしまうと、ふと C に戻った時に「リストとかハッシュテーブルがないから、再実装するか...いやそれともライブラリを探してきた方がいいか...。」と嘆くこともしばしば。 そこで以前 C/C++ 言語で使用できるハッシュテーブルについて調べたものを簡単にまとめておく。 glibc 言わずと知れた GNU の標準 C ライブラリ。search.h というヘッダがあり、その中にハッシュテーブルを管理できる API が提供されている。 STL (Standard Template Library) C++ の標準テンプレートライブラリ。hash_map がハッシュテーブルを提供するクラス。 GLib gtk+ のために設計・実装された低レベルライブラリ。GHashTable がハッシュテーブルを提供する構造体。 Eet EFL
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.machu.jp/posts/20071023/p01/