Open2
ハッシュについての雑多な理解
yamazakingハッシュの目的について
まずは、ハッシュの目的について
GPT-4oの回答はこちら
- データの整合性確認：フィアルやメッセージが改ざんされていないかを確認するためにハッシュ値が利用される。たとえば、ファイルのハッシュ値を事前に知っておけば、ダウンロード後に同じハッシュ値であることを確認することで、ファイルが正しくダウンロードされたことがわかる
- 高速なデータ検索：ハッシュテーブルというデータ構造では、ハッシュ関数をつかってデータの格納場所を決定する。これにより、データの検索が高速化される。DBやキャッシュシステムでよく利用される技術
- パスワードの保存と認証：ユーザーのパスワードをそのまま保存するのは危険なので、ハッシュ化して保存する。認証の際は入力されたパスワードをハッシュ化し、頬zんされているハッシュ値と比較することで本人確認を行う
- デジタル署名と暗号化：ハッシュ関数は暗号化技術やデジタル署名でも使われ、データの改ざん検知や送信者の確認に役立つ。
３番目のパスワードのところで使用することがメインだったので、他のところでも確かに聞いたことあるな、という説明。
２番目のハッシュテーブルについては、詳しく知らないので、具体例を聞いてみた
ハッシュテーブルは、キーと値のペアを保存するデータ構造で、効率的にデータの格納と検索を行えるように設計されています。
具体例として電話帳が挙げられます
電話帳アプリに名前と電話番号のペアを保存したいとします。このとき、ハッシュテーブルを使うことで、名前から迅速に電話番号を検索することができます。
- データの挿入
2. 例えば田中という名前に080-1234-5678という電話番号を保存したい場合、ハッシュ関数が田中という名前を特定のハッシュ値（インデックス）に変換し、そのインデックスに080-1234-5678を保存します
3. ハッシュ関数の例として、文字t列の各文字のASCIIコードを足し合わせたものを配列の長さで割る方法などが考えられます - データの検索
3. 田中さんの電話番号を知りたい、となったときに、再び田中をハッシュ関数に通してインデックスを取得し、そのインデックスのいちにある電話番号を即座に返す
4. この方法では、リストや配列で一つづつデータを探す必要がなく、計算で直接位置がわかるため、検索速度が非常に早くなる - ハッシュの衝突
4. 同じハッシュ値が複数のキーで発生することがある。これをハッシュの衝突という
5. 解決法としては、チュイニング（同じインデックスに複数の値をリスト形式で保存する）やオープンアドレス（別のあいてるインデックスに保存する）などが使われる
辞書型との違いを聞いてみた
- データのアクセス速度
2. ハッシュテーブルでは、キーをハッシュ関数で直接インデックスに変換するため、データの検索や挿入平均O（1）となるため、非常に高速に計算できる
3. 一方辞書テーブルでは、データを順番に並べるか特定の構造をもたせることが一般的。そのため、検索や挿入にはO（logn）やO(n)の時間がかかる場合がある - スケーラビリティ
3. ハッシュテーブルは、データ量が増えても効率的にデータを格納しやすく、大規模なデータセットに対しても安定した高速性を維持できる
4. 辞書テーブルは、特定のデータ量以上になると挿入や検索にかかる時間が増えやすく、特に大規模データセットでは、効率が低下しやすい - 辞書テーブルが有利な場面
6. データが小規模な場合や、データがソート済であることが求められる場面には有利です。また、ツリーデータ構造の辞書テーブルではデータを順番に取得できるため、順序が重要なアプリケーションではハッシュテーブルよりも適している
ハッシュ値の数字で列を作れるの？という問いへの回答
ハッシュテーブルで、新しいキーと値のペアが追加されるときの、流れ
- ハッシュ値の計算：新しいキーをハッシュ関数に通してハッシュ値を計算し、ハッシュテーブル内のインデックス（位置）を求める
- 空きインデックスの確認：計算されたインデックスが空いていれば、その位置に新しいキーと値を保存する（INSERTに相当）
- 衝突処理：計算されたインデックスにすでにデータがある場合、衝突が発生する。この場合、ハッシュテーブルでは上記に述べたようなチュイニングやオープンアドレスの処理を行い、新しい位置にデータを格納する
なるほど。ハッシュ関数について聞いてみた。一番多いのは、乗算ハッシュ法と多項式ハッシュ関数だったので、それについて
- 乗算ハッシュ法
- 数学的な定数を用いる方法で、ハッシュ値=(キー*定数)%テーブルサイズ
- この場合、定数として黄金比などの特定の値を使うことがあり、キーの分散が良くなる
- 乗算ハッシュは計算が高速で、衝突も比較的少なく済むことが多い
- 多項式のハッシュ関数
- 文字列を数値に変換する際、各文字に特定の基数（通常は31や37の素数）をかけ合わせて計算する方法
- これにより、類似したキーが異なるハッシュ値になりやすく、衝突が減る傾向になる
モバイルのデータストア（iOSではUserDefault,AndroidだとSharedPreferences）も似てるなと思って、聞いてみた
モバイルのデータベースでも内部的にハッシュテーブルのようなデータ構造が利用されることが多いです
以下略
yamazaking暗号学的なハッシュ関数
以下GPT-4oで回答。
主要なものをあげてもらった
- MD5
- 任意の長さの入力を128ビットのハッシュ値に変換
- 一般的に広く利用されてきたが、衝突性が高いことが判明しており、重要なセキュリティ用途には推奨されない
- SHA-1
- 160ビットのハッシュ値を生成する。かつては、暗号化の標準とされていた
- こちらも衝突性が高いことが判明した。現在では、セキュリティ用途には非推奨とされ、SHA-256などのより安全なアルゴリズムに置き換えられている
- SHA-256
- SHA-256はSHA-2ファミリーの一部であり、256ビットのハッシュ値を生成する。SHA-2はSHA-1の後継として、セキュリティ強度が高いアルゴリズムとされている
- 多くのセキュリティやプロトコル、暗号通貨で使用されており、幅広い用途で信頼されている
- 計算量が多いため、MD5やSHA-1に比べて処理が重い傾向があるが、その分セキュリティが強化されている。SHA-256は衝突耐性が高く、現時点での技術水準では衝突を見つけるのは非常に困難とされている
- SHA-3
- SHA-2に対する代替として、特に将来的なセキュリティの脅威に対応するための用途で採用されている。SHA-2に脆弱性が見つかった場合に備えた、次世代の暗号学的ハッシュ関数として期待されている
- SHA-2はSHA-2とは異なる構造を持っており、アルゴリズムの内部構造が根本的に異なる。SHA-3はSha-256やSHA-512と同等のビット長で使用することができ、さらに強力なセキュリティが期待されている
- BLAKE2
- SHA-2やSHA-3と同様に安全性が高く、さらにSHA-256よりも計算が高速な特徴を持つハッシュアルゴリズム
- ファイルのハッシュ化、認証、デジタル署名などで利用されている
- ビット長は任意（128~512）
また、これらのハッシュは一方向性関数であるため、ハッシュ値をもとの値にデコードすることはできない（不可逆）。
そのため、検算する場合は入力値をハッシュ化したものを保存しておき、再度値が入ったときにハッシュ化して比べる。