Swisstable Hash に使われているビット演算の魔術 - methaneのブログ
Googleが開発したSwisstableと呼ばれるハッシュテーブル実装がAbseilとして公開されて、Rustの標準のHashMap実装にもその移植であるhashbrownが採用されました。 Swisstable の面白いところは、8または16要素をグループ化して、グループ内の各要素のハッシュ値のうち7bitをそれぞれ1byteに格納した8または16バイトの配列を作り、その配列に対して一気に並列でマッチングを行うことです。 この並列マッチングにはSSE2もしくはビット演算が使われます。この記事ではこの並列マッチング部分について解説します。 SSE2を使う場合 SSE2を使う場合は、グループのサイズは16になります。ハッシュ値を格納する配列のことを control と呼ぶことにすると、 control は char control[16] になります。control の各バイトの状態は次の
GitHub - BLAKE3-team/BLAKE3: the official Rust and C implementations of the BLAKE3 cryptographic hash function
BLAKE3 is a cryptographic hash function that is: Much faster than MD5, SHA-1, SHA-2, SHA-3, and BLAKE2. Secure, unlike MD5 and SHA-1. And secure against length extension, unlike SHA-2. Highly parallelizable across any number of threads and SIMD lanes, because it's a Merkle tree on the inside. Capable of verified streaming and incremental updates, again because it's a Merkle tree. A PRF, MAC, KDF,
abseil / Swiss Tables and <code>absl::Hash</code>
By Sam Benzaquen, Alkis Evlogimenos, Matt Kulukundis, and Roman Perepelitsa We are extremely pleased to announce the availability of the new “Swiss Table” family of hashtables in Abseil and the absl::Hash hashing framework that allows easy extensibility for user defined types. Last year at CppCon, We presented a talk on a new hashtable that we were rolling out across Google’s codebase. When asked
Sqids (formerly Hashids) · Generate Short Unique IDs
What is Sqids? Sqids (pronounced "squids") is an open-source library that lets you generate short unique identifiers from numbers. These IDs are URL-safe, can encode several numbers, and do not contain common profanity words. Read more . This is what they look like: Use Cases The main use of Sqids is purely visual. If you'd like to use IDs instead of numbers in your project, Sqids could be a good
私が書いた最速のハッシュテーブル – PART 2 | POSTD
素数か2のべき乗か ハッシュテーブルのアイテムをルックアップする際に高負荷なステップが3つあります。 キーをハッシングする キーをスロットにマッピングする 該当スロットのメモリをフェッチする ステップ1は、キーが整数であれば、低負荷になります。単にintをsize_tにキャストするだけです。しかし、文字列のようなタイプのキーの場合は高負荷となります。 ステップ2はよくある整数モジュロ演算です。 ステップ3はポインタの間接参照です。std::unordered_mapの場合は複数のポインタ間接参照となります。 処理の遅いハッシュ関数でなければ、直観的にステップ3が最も高負荷になると考えると思います。しかし、全てのルックアップでキャッシュミスが生じなければ、整数モジュロが最も高負荷な処理となります。現代のハードウェアにおいても整数モジュロは非常に遅いのです。 Intelマニュアル では、整数モ
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
パスワードのハッシュに使うべきPBKDF2、Bcrypt、HMACの各言語実装一覧 - このブログはURLが変更になりました
いつも忘れるのでメモ。 元ネタ:Are you sure SHA-1+salt is enough for passwords? 日本語訳:「SHA-1+salt」はパスワードに十分だと思いますか？ こうしたスキームをいくつか選ぶことができる： PBKDF2 http://en.wikipedia.org/wiki/PBKDF2 Bcrypt http://www.openwall.com/crypt/ HMAC http://en.wikipedia.org/wiki/HMAC 各選択肢はそれぞれの強みと弱みがあるが、これらは全てSHA1+saltのような汎用ハッシュのインプリメンテーションより、はるかに強力だ。 ということで、各言語での実装を調べてみた。実装が正しいかは調べてない。別実装もあるかもしれない。 言語 PBKDF2 Bcrypt HMAC Java Bouncy Castl
MurmurHash - Wikipedia
MurmurHash is a non-cryptographic hash function suitable for general hash-based lookup.[1][2][3] It was created by Austin Appleby in 2008[4] and is currently hosted on GitHub along with its test suite named 'SMHasher'. It also exists in a number of variants,[5] all of which have been released into the public domain. The name comes from two basic operations, multiply (MU) and rotate (R), used in it
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GoogleがFarmHashを公開，文字列ハッシュ関数のニューファミリー
高速ハッシュの 脆弱性