Swisstable Hash に使われているビット演算の魔術 - methaneのブログ

テクノロジーカテゴリーの変更を依頼記事元:

methane.hatenablog.jp

45 usersがブックマークコメント

記事へのコメント0件

注目コメント
新着コメント

新着コメントはまだありません。
このエントリーにコメントしてみましょう。

注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています

リンクを埋め込む

以下のコードをコピーしてサイトに埋め込むことができます

<iframe marginwidth="0" marginheight="0" src="https://b.hatena.ne.jp/entry.parts?url=https%3A%2F%2Fmethane.hatenablog.jp%2Fentry%2F2022%2F02%2F22%2FSwisstable_Hash_%25E3%2581%25AB%25E4%25BD%25BF%25E3%2582%258F%25E3%2582%258C%25E3%2581%25A6%25E3%2581%2584%25E3%2582%258B%25E3%2583%2593%25E3%2583%2583%25E3%2583%2588%25E6%25BC%2594%25E7%25AE%2597%25E3%2581%25AE%25E9%25AD%2594%25E8%25A1%2593" scrolling="no" frameborder="0" height="230" width="500"><div class="hatena-bookmark-detail-info"><a href="https://methane.hatenablog.jp/entry/2022/02/22/Swisstable_Hash_%E3%81%AB%E4%BD%BF%E3%82%8F%E3%82%8C%E3%81%A6%E3%81%84%E3%82%8B%E3%83%93%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97%E3%81%AE%E9%AD%94%E8%A1%93">Swisstable Hash に使われているビット演算の魔術 - methaneのブログ</a><a href="https://b.hatena.ne.jp/entry/s/methane.hatenablog.jp/entry/2022/02/22/Swisstable_Hash_%E3%81%AB%E4%BD%BF%E3%82%8F%E3%82%8C%E3%81%A6%E3%81%84%E3%82%8B%E3%83%93%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97%E3%81%AE%E9%AD%94%E8%A1%93">はてなブックマーク - Swisstable Hash に使われているビット演算の魔術 - methaneのブログ</a></div></iframe>

プレビュー

規約違反を報告

いまの話題をアプリでチェック！

バナー広告なし
ミュート機能あり
ダークモード搭載

アプリをダウンロード

Swisstable Hash に使われているビット演算の魔術 - methaneのブログ

Googleが開発したSwisstableと呼ばれるハッシュテーブル実装がAbseilとして公開されて、Rustの標準のHas... Googleが開発したSwisstableと呼ばれるハッシュテーブル実装がAbseilとして公開されて、Rustの標準のHashMap実装にもその移植であるhashbrownが採用されました。 Swisstable の面白いところは、8または16要素をグループ化して、グループ内の各要素のハッシュ値のうち7bitをそれぞれ1byteに格納した8または16バイトの配列を作り、その配列に対して一気に並列でマッチングを行うことです。この並列マッチングにはSSE2もしくはビット演算が使われます。この記事ではこの並列マッチング部分について解説します。 SSE2を使う場合 SSE2を使う場合は、グループのサイズは16になります。ハッシュ値を格納する配列のことを control と呼ぶことにすると、 control は char control[16] になります。control の各バイトの状態は次の