問題タブ [hash]

キーが正規表現であり、文字列が辞書に対して検索される辞書（またはハッシュ、マップ、またはお気に入りの言語がそれを呼び出すもの）で検索を実行するための合理的に効率的な方法があるかどうかを把握しようとしていますキーのセット。例 (Python 構文):

(明らかに、上記の例は Python で書かれたとおりには機能しませんが、それは私ができるようにしたいことです。)

これを実装する単純な方法を考えることができます。この方法では、辞書内のすべてのキーを反復処理し、渡された文字列をそれらに対して照合しようとしますが、ハッシュ マップの O(1) ルックアップ時間を失い、代わりに O(n) を使用します。ここで、n は辞書内のキーの数です。このディクショナリは非常に大きくなると予想されるため、これは大きな問題になる可能性があり、何度も何度も検索する必要があります (実際には、テキスト ファイルで読み取るすべての行に対して反復処理を行う必要があり、ファイルのサイズは数百メガバイトになる場合があります)。

O(n) 効率に頼らずにこれを達成する方法はありますか?

あるいは、データベースでこの種のルックアップを実行する方法を知っていれば、それも素晴らしいでしょう。

(どのプログラミング言語でも問題ありません。私は Python を使用していますが、ここでのデータ構造とアルゴリズムにもっと興味があります。)

複数の一致が可能であると誰かが指摘しましたが、それは完全に正しいです。理想的には、この状況では、すべての一致を含むリストまたはタプルを返したいと思います。しかし、私は最初の試合に落ち着くでしょう。

そのシナリオでは O(1) が可能であるとは思えません。ただし、O(n) 未満のもので解決します。また、基礎となるデータ構造は何でもかまいませんが、私が望む基本的な動作は、上で書いたものです: 文字列を検索し、正規表現キーに一致する値を返します。

PHP には md5()、sha1()、および hash() 関数があることは知っていますが、MySQL PASSWORD() 関数を使用してハッシュを作成したいと考えています。これまでのところ、私が考えることができる唯一の方法は、サーバーにクエリを実行することですが、MySQL にまったくクエリを実行せずに同じことを行う関数 (できれば php または Perl) が必要です。

例えば：

MySQL ハッシュ -> 464bb2cb3cf18b66

MySQL5 ハッシュ -> *01D01F5CA7CA8BA771E03F4AC55EC73C11EFA229

ありがとう！

Web からダウンロードした画像の画像サムネイル バージョンをキャッシュする単純な C++ クラスを作成しています。そのため、URL 文字列を取り込み、ファイル名として適切な一意の文字列を出力するハッシュ関数を使用したいと考えています。

関数を自分で書き直さずにこれを行う簡単な方法はありますか? 簡単なライブラリを探しましたが、何も見つかりませんでした。確かにこれはよくある問題です。

以下のコードを使用してパスワードをレジストリに保存していますが、元に戻すにはどうすればよいですか? 以下のコードは私のものではありませんが、うまく暗号化されています。

ありがとう

現在、ユーザーのログイン資格情報がSQLServerDBに保存されているアプリケーションがあります。これらは、基本的に、プレーンテキストのユーザー名、パスワードハッシュ、およびこのハッシュに関連付けられたソルトとして保存されます。

これらはすべて、ASP.NETのメンバーシップ/ロールシステムに組み込まれている関数によって作成されました。'joe'という名前のユーザーと'password'のパスワードの行は次のとおりです。

joe、kDP0Py2QwEdJYtUX9cJABg ==、OJF6H4KdxFLgLu + oTDNFodCEfMA =

このようなものをCSVファイルにダンプし、パスワードを次の形式で保存するDjangoで使用可能な形式にしようとしています。

[algo] $ [salt] $ [hash]

ここで、saltはプレーンな文字列であり、ハッシュはSHA1ハッシュの16進ダイジェストです。

これまでのところ、ASPがこれらのハッシュとソルトをbase64形式で保存していることを確認できました。上記の値は、バイナリ文字列にデコードされます。

リフレクターを使用して、ASPがこれらの値に対してどのように認証するかを収集しました。

基本的に、DBからソルトをプルし、b64はそれをバイナリ表現にデコードします。生のパスワードに対して「GetBytes」を実行し、次にそれらを連結します。最初にソルトします。

次に、この新しい文字列に対してSHA1アルゴリズムを実行し、base64でエンコードして、データベースに保存されている値と比較します。

Pythonでこれらのハッシュを再現するためのコードを作成しようとしましたが、失敗しました。これがどのように変換されるかを理解できるまで、Djangoでそれらを使用することはできません。これが私がテストしている方法です：

誰かが私のアプローチの欠陥を見ることができるか、または別の方法を提案できるかどうか疑問に思っています。おそらく、上記のアルゴリズムと上記の既知のパスワードとソルトを使用して、システムでハッシュを生成できますか？

これは失敗します：

このエラーで：

しかし、これは機能します：

なぜ？

複数の区切り文字を持つ単一の文字列を key=>value ハッシュ構造に変換したいと考えています。これを達成する簡単な方法はありますか？私の現在の実装は次のとおりです。

「config」には次が含まれます。

最後の数字も削除する必要があり、「ip」という名前の別のキー=>値のペアに保持する必要があります。(コードを長く複雑にしなければ、これを達成することはできませんでした)。

すべてのパスワードをハッシュ形式で保存しています。これらのパスワードを取得する必要があります。

私のパスワードは「123456」です。これをハッシュ化された「3453474852dfdsfdsfdf」値として保存します。

ハッシュ値から元のパスワードを取得する必要があります。（パスワードを取得）。

どうやってやるの？。私はSHA1ハッシュアルゴリズムをやっています。

キーのハッシュ コードからハッシュ テーブルのバケット インデックスを計算するときに、バケットの配列のサイズが 2 のべき乗である場合に、除算後の剰余 (モジュロ) を使用しないのはなぜですか?

ハッシュに関する情報へのリンクは探していません。

私は世界最大のハッシュ関数を探しているわけではありません。

を説明するミニストーリーに興味があります

• あなたが働いていた問題のドメイン
• 扱っていたデータの性質
• データのハッシュ関数を設計する際の思考プロセスについて教えてください。
• 結果にどれほど満足しましたか。
• その経験からあなたが学んだことは、他の人にとって価値があるかもしれません。