[ノイズ]。ハッシュテーブルに入る前に、みましょう最初にいくつかの長所と短所を検討単純なデータ構造で始まる配列。アレイは、私たちが保存することができたことを思い出してください単一のデータ·タイプの要素連続してメモリ内の。各要素に関連付けられているためインデックス、または場所、我々は、全てのランダムアクセスを有する配列の要素。換言すれば、我々は任意の要素にアクセスすることができのインデックスで、1つのステップで配列。これは、アルゴリズム大したことバイナリサーチのようにランダムに依存アクセス。配列の欠点は、その大きさ固定されている。配列データを格納するため、連続して中メモリには、配列のサイズを指定する必要がありますあなたは配列を宣言するとき。あなたが効果的に動作を求めている適切な量を確保するためのシステム配列の要素のためのメモリの。より多くのメモリという保証はありません、お使いのアレイに隣接して、利用できるようになります後で使用するために。だから、配列は、容易に成長することはできません。我々はまた、リンクについて学んだことを思い出してくださいそのため、成長することができますリスト、要素は、メモリ内に連続していない。リンクされたリスト内の各ノードは含まれています私たちが保存したい要素だけでなく、の後続の要素へのポインタリスト。残念ながら、我々が支払ってきた価格ダイナミックなサイズは、ランダムアクセスで要素。特定の要素にアクセスするためには、全体を横断する必要の目的の要素があるまでリスト達した。私は9番を探していますので、もし、私がしたいノードからノードへのポインタをたどる、各ノードの値かどうかをチェックする 9に等しい。このように、最悪の場合には、ルックアップ遠くから効率的であるO（n）で、。まだながら、我々は（N）、Oよりも優れて行うことができます我々のデータ構造が上に成長させること時間？ハッシュテーブルは、ソリューションを提供します。ハッシュテーブルが使用される場合に迅速な挿入、削除、およびルックアップ要素が優先事項である。理論的には、挿入、欠失、および参照でも一定で達成することができる時間。そのため、ハッシュテーブルはとにかく何ですか？ハッシュテーブルは、結合されただけの配列です我々は、ハッシュと呼ぶことにします機能付き機能。ハッシュ関数は、データの一部を取る入力として、我々は重要なこのことを電話するよ、と一般に呼ばれる、整数値を出力するハッシュ値である。ハッシュ値は、当社のキーにマップハッシュテーブル内の特定のインデックス。あなたが最初ににハッシュ関数を使用すると思いますここで、ハッシュテーブル内に決定する指定されたキーを格納します。後で、同じハッシュ関数を使用すると思いますここで、ハッシュテーブル内に決定する指定されたキーを検索します。このため、ハッシュことが重要だこの関数は、一貫して出力するように動作同じキーに対して同じハッシュ値。ハッシュテーブルをするために使用できることを知っているすべてのタイプのデータを記憶する。しかし、物事を単純化するために、我々はに焦点を合わせることにします今の文字列。ここに文字列の単純なハッシュ関数です。このハッシュ関数は、ハッシュを計算の最初の文字に基づいた機能キーを押します。「Appleは "文字" A "で始まるので、だハッシュテーブル内のインデックス0にマッピングされています。同様に、「バナナ」は、インデックス1にマッピングされていると「猫」は、インデックス2にマッピングされている。単語 "犬"である場合、友人が尋ねられた場合表は、ハッシュへの入力 "犬"をよ機能、意志出力ハッシュ値 3の。「犬」は、インデックス3で保存されていないので、「犬は」ではないという確信を持って言うことができます表中、我々は唯一の1を確認したにも関わらず、テーブルの26の指標をハッシュ。物事にスパナをスローする時間。我々はに "アリ"を保存したい場合はどうテーブルにも？ "アリ"は "アップル"が行ったように、インデックス0にハッシュします。これは、衝突の一例であり、同じにハッシュする2キーの結果インデックス。あなたのハッシュテーブルがより大きい場合であってもあなたのデータが設定され、あなたは良いを選択したハッシュ関数は、あなたはまだに対処するための計画が必要です衝突、もし、彼らが発生する。それでは2の長所と短所を説明しましょう衝突を解決するための共通の方法：プロービング線形および個別の連鎖。キーのハッシュにした場合の直線は、プロービング以前に保存されたと同じインデックスキーは、次の利用可能な割り当てられているテーブル内のスロット。だから、 "アリ"は今以来、インデックス3で保存されているインデックス0,1、および2が既に使用中であった。そして、我々は第3ワードを保存しようとすると、その文字「A」で始まるが、それが割り当てられているインデックス4に日時のインデックス0,1,2、および3 満ちている。あなたも、この単純なものから見ることができるように例では、一度衝突が、あなたを発生する大幅にその可能性を高める別の衝突が同じで発生しますエリア。これは、クラスタリングと呼ばれ、それがださ重大な欠点は、線形でプロービングする。また、最悪の場合の挿入、欠失、ルックアップの時間は、O（n）に委譲している、次の使用可能なスロットが持っている可能性があるため潜在的に表の最後のスロットであっ。多分別々の連鎖はより多くを提供します説得力のあるソリューションを提供します。別々の連鎖モデルでは、ハッシュ表には、実際にはポインタの配列にあるリンクされたリスト。衝突が発生したときに、キーがあってもよいの先頭に一定の時間内に挿入された適切なリンクリスト。私たちは「りんご」を検索すると、今何が起こるかハッシュテーブル内の？最悪のケースでは、通過しなければならないインデックス0から始まる全体のリンクリスト、。ハッシュのワーストケースの検索時間別々の連鎖を使用するテーブルですしたがって、kはO（n個/ k）は、ハッシュテーブルのサイズ。ちょっと待って、Kは定数である。そのようにはO（n / k）は、実際にはO（n）はのための最悪の場合の検索時間であったリンクされたリスト。私たちは本当にすべてを介して行っているハッシュテーブルについての学習の悩み我々はスタート地点だけ戻ってしまいますか？つまり、理論上からの場合もある視点が、現実の世界では、 O（N / K）以上の大幅な改善可能性 O（n）である。それをこのように考えて：Kであることを前提とし 10 - あなたではなく100秒待機していましたまたは100 / K？終了するのは、Microsoft Wordから10秒文書をスペルチェック。あなただけの見たように、衝突を解決する 1線形探索のようなものかを伴う物事を遅くしている別の、かなり。そのため、ハッシュを選択するとよいでしょうの可能性を最小限にする機能最初の場所で発生した衝突。ここでは良いハッシュのいくつかのプロパティがあります心に留めておくべき機能。良いハッシュ関数はを利用する必要があります指定されたキーによって提供されるすべての情報の数を最大にするために可能なハッシュ値。例えば、我々は二つの文字列があれば、「CAT」そして「キャタピラー」、我々は彼らがハッシュしたいと思いますテーブルの上に別の場所へ。ハッシュ関数は、考慮した場合第一、二、または3文字文字列で、衝突が発生する、両方の単語は同じで始まるので、 3文字。ハッシュ値が均等に分散させる必要がありハッシュテーブルを横断。これは、リンクの長さを減少させるリストには、衝突が発生する必要があります。また、良い兆候だ場合、あなたのハッシュ値非常に異なる生成することができる類似したキーのハッシュ値、衝突がはるかに少ない可能性が高いこと。私たちの目標は、迅速な挿入、削除され、と検索。ハッシュ関数は、に重要な役割を果たしているこれらの各プロセスとなります非常に頻繁に呼び出される。したがって、それは非常に採用して確認してください実行を最小限にするための簡単、迅速なオペレーション時間。私は、あなたがこの簡単に楽しんできた願っていますハッシュテーブルの概要。私の名前はローレンであり、これはCS50である。