クックパッド開発者ブログスマートフォン用の表示で見るクックパッド開発者ブログ2018-03-22ハッシュ値の使い方についてモバイル基盤グループのヴァンサン(@vincentisambart)です。先日以下のツイートを拝見しました。4.1にはまだ入りませんが、4.2か5.0に入るはずです。コードレビューでこの変更が問題を起こそうなコードを指摘したことあるので、ハッシュ値のおさらいをする良いタイミングではないでしょうか。Swiftのことを考えて書いていますが、多くのプログラミング言語にも当てはまります。ハッシュ値はSwiftではhashValueというプロパティが返しますが、多くの言語では単にhashというメソッド・関数が返します。ハッシュマップハッシュ値はハッシュマップ(別名ハッシュテーブル)に一番使われるのではないでしょうか。SwiftではDictionary、RubyではHash、C++ではunordered_map、RustではHashMapと呼ばれるものです。ハッシュマップはマップの一種であって、マップというのはキーに値を結びつけるためのものです。1つのキーに1つの値しか結びつけない場合が多いです(値は配列を使えますが)。漫画の連載開始の年のマップを作ると以下のようになります。2007ハッシュマップは基本的にキーに順がない場合が多いです。キーが挿入された順で列挙されると保証する実装(例えばRubyのHash)もありますが。ハッシュマップのキーに一番使われるのは文字列ですが、以下の2つの条件を満たせば何でも使えます。2つのキーが等しいかどうか比較できる(SwiftではEquatableというプロトコルに準拠すること)キーからハッシュ値を計算できる(SwiftではHashableというプロトコルに準拠すること。比較できないとハッシュ値が使い物にならないのでHashableはEquatableに準拠している)ハッシュマップは別のマップの種類に比べてどういうメリットあるかと言いますと、ハッシュ関数(ハッシュ値を計算する関数)が良ければ、キーが多くても値を早く取得できるところです。ハッシュ値とそれを生成するハッシュ関数ハッシュマップに使われるハッシュ値は基本的に32-bitか64-bitの整数です。ハッシュ値を元にキーと値がメモリ上どこに置かれるのか決まります。ハッシュマップで使うには、ハッシュ値が以下の条件を満たす必要があります。プログラムが終了するまで、ハッシュ関数(ハッシュ値を計算する関数)に同じキーを渡すと必ず同じハッシュ値が返るべきハッシュ値が違っていれば、ハッシュ関数に渡されたキーが異なるべき違う2つのキーが同じハッシュ値を持っても良い。可変長の文字列から計算されるハッシュ値が固定長数バイトだけに収まるので、すべてのキーが違うハッシュ値を持つはずがありません。上記の条件を満たす一番シンプルなハッシュ関数が固定値を返すだけです。それだとハッシュマップは一応動きますが、性能がすごく落ちて、ハッシュマップを使うメリットがなくなります。ハッシュ値を計算するハッシュ関数なんですが、良いハッシュ関数はハッシュ値の計算が速くて、色んなキーを渡すとできるだけ違うハッシュ値を返してくれた方がハッシュマップの性能が出ます。良いハッシュ関数を作るのはすごく大変なので、既存の研究されたものが使われる場合が多いです。気を付けるべきところハッシュ値が満たすべき条件に「プログラムが終了するまで、ハッシュ関数に同じキーを渡すと必ず同じ値が返る」と書きましたが、「プログラムが終了するまで」が重要です。プログラムをまた実行すると変わる可能性があります。Rubyで試してみると分かりやすいと思います。"abcd".hash'-771890369285024305今までSwiftではプログラムを何回実行しても標準のhashValueが毎回同じハッシュ値を返していましたが、この記事の頭にリンクされていた変更でプログラムが実行される度にハッシュ値が変わるようになります。して変わるようになったのかと言いますと、DoS攻撃のリスクを下がるためです。DoS攻撃というのは簡単にいうとマシンがやるべき処理に追いつけなくなることです。ハッシュマップに同じハッシュ値を持つキーをたくさん入れると、性能がどんどんと落ちていきます。ハッシュ値を事前に予測できると同じハッシュ値を持つキーを大量用意できます。サーバーがハッシュマップのキーにしそうなもの(例えばリクエストの引数名)に用意された大量のキーを使わせてサーバーがやるべき処理に追いつかなくなります。ハッシュ値がプログラムの実行ごとに変わると、ハッシュ値の予測がかなり困難になるのでリスクを減らせます。ハッシュマップでもどうして同じハッシュ値が多いとハッシュマップの性能が落ちていくのでしょうか。理解するにはハッシュマップの仕組みをもっと細かく見る必要があります。ハッシュマップのコアな部分が単なる配列です。配列の項目がバケット(bucket)と呼ばれています。配列のサイズ(バケット数)に満たすべき条件が特にありませんが、基本的に項目が増えるともっと大きい配列が用意されて、以前の項目を新しい配列に移し替えます(新しい配列でバケットが変わる可能性あるので要注意)。挿入されるキーと値がどこに入るのかはハッシュ値で決まります。バケット数がハッシュ値の数ほど多いわけではないので、モジュロ(剰余演算)を使ってバケット数以下にします。8が0なので以下のようになります。8が6なので以下のようになります。空ただし、それだと同じバケットに別のキーが入っていたら代入すると前のキーがなくなります。同じバケットに複数のキーが入るケースを衝突(collision)といいます。衝突の扱いは様々あります。シンプルなのは連結リストや動的配列ですが、例えばキーを次に空いているバケットに入れることもあります。8が6なので以下のようになります。空"宇宙兄弟"↓2007シンプルなハッシュマップを実装してみると以下のようになります。}}肝心なところは衝突の扱いです。同じバケットにキーが増えると、バケットに入っている項目のリストが少しずつ伸びます。項目が増えると読み込みも書き込みも比較が増えて処理が重くなります。バケットに項目が1つしかなかった場合、アクセスする時は行われるのはハッシュ値の計算1回と、ハッシュ値の比較1回と、キー自体の比較1回です。同じハッシュ値のキーが100個入っていると、全部同じバケットになるので、アクセスすると行われるのはハッシュ値の計算1回と、ハッシュ値の比較100回と、キー自体の比較100回です。100個目なので、前の99回分の挿入ももちろんあります。逆にすべてのキーが別のバケットに入ると挿入する度に比較は各1回だけです。できるだけ多くのバケットが使われる方が性能が出ます。コードレビューで気づいた間違いこの記事の冒頭でハッシュ値に関する間違いを指摘したと言いましたが、具体的にいうと大きい間違いが以下の2つでした。}}lhsとrhsが違っても、ハッシュ値が同じの可能性があります。ハッシュ値が違っていたらlhsとrhsが必ず違いますけど。fooHashValueKey)プログラムの次の実行でハッシュ値が変わる可能性があります。元からHashableの公式ドキュメントには明確に書いてありました。execution.実際冒頭でリンクした変更がSwiftに入ったら、プログラムの次の実行でハッシュ値が変わっていない可能性が極めて低いです。まとめハッシュ値を扱っている場合、以下の項目を覚えておきましょう。NEWS技術部の笹田(ko1)と遠藤(mame)です。...2019-08-16UICollectionViewでページングスクロールを実装するこんにちは。新規サービス開発部の中村です。f...技術部の笹田です。インタプリタの開発をしている笹田です。使ったセキュリティログ検索基盤の構築サービス特性にあった検索システムの設計戦略クックパッド採用説明会「クックパッドはサービスの作り手を採用したいんです。/*}*/スターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。