[音楽再生] DOUG LLOYD：今で 配列について多くのことを知っています、 あなたがリンクされたリストについて多くのことを知っています。 そして、我々は議論してきました 長所と短所、我々はしました リストをリンクされている議論 大きく、小さくなることができ、 彼らはより多くのサイズを取ります。 配列は、はるかに簡単にしています 使用していますが、彼らは同じくらいに限定的です 我々はのサイズを設定する必要がありますように 非常に先頭に配列 し、我々はそれに立ち往生しています。 

しかし、それは、私たちはかなりき、です 私たちのトピックをすべて使い果たし リンクされたリストと配列について。 それとも私たちは持っていますか？ 多分、我々は何かを行うことができます さらに創造。 そして貸すのその種 ハッシュテーブルのアイデア。 

だから、ハッシュテーブルに我々がしようとするつもりです リンクされたリストを配列に結合します。 我々は、利点を取るつもりです 配列の、ランダムアクセスのような、 ただ、アレイに移動することができるという 素子4または配列要素8 全体で反復処理する必要はありません。 それは右、かなり速いですか！ 

しかし、我々はまた、我々のデータを持つようにしたいです 構造が成長し、縮小することができます。 我々はない、必要はありません 制限されるようにします。 そして、我々はできるようにしたいです 物事を追加および削除するには 非常に簡単に、どのあなたが思い出すならば、 配列と非常に複雑です。 そして、我々はこれを呼び出すことができます 新しいものハッシュテーブル。 

そして場合は、正しく実装 私たちは、ソートの取っています 両データの利点 すでに見てきた構造、 配列やリンクリスト。 挿入はに開始することができます 1のθに向かって傾向があります。 シータ私たちは本当に、説明していません しかし、シータはちょうど平均的なケースです、 何が実際に起こるだろう。 あなたは、常にするつもりはありません 最悪のシナリオを持っています、 あなたは常に持っているつもりはありません 最良のシナリオ、だから何です 平均シナリオ？ 

まあ平均挿入 ハッシュテーブルに 近い一定の時間に取得するために開始することができます。 そして、削除が得ることができます 一定の時間があります。 そして、ルックアップは得ることができます 一定の時間があります。 我々はデータを持っていませんThat's-- 構造は、まだそれはそれを行うことができ、 そしてこれは、すでに聞こえます かなり大きい事のように。 私たちは本当に軽減しました 独自に各の欠点。 

このパフォーマンスを得るために、 、しかし我々をアップグレード 我々は追加方法を再考する必要があります 構造へのデータ。 具体的に私たちが望みます 私たちに伝えるために、データそのもの どこに構造に行く必要があります。 そして、我々はそれがでないかどうかを確認する必要がある場合 構造、我々はそれを見つけるために必要がある場合は、 我々は、データを見てみたいです 再びかつ効果的にできるように、 データを使用して、ランダムにアクセスします。 ちょうどを見て 私たちが持つべきデータ まさに我々がいる場所のアイデア ハッシュテーブルにそれを見つけるつもり。 

ハッシュの今欠点 テーブルには、彼らは本当にしているということです 注文やデータの並べ替えでかなり悪いです。 そして、実際には、あなたが開始した場合 注文やソートするためにそれらを使用します データはすべてを失います 利点は、以前 挿入および削除の点でした。 時間がに近づきます n個のシータ、私たちは基本的にしました リンクリストに回帰し。 そして、私たちはハッシュだけを使用したいです 私たちは気にしないのであれば、テーブル データがソートされているかどうか。 コンテキストのために あなたはCS50でそれらを使用します あなたはおそらく気にしません データがソートされていること。 

そのように、ハッシュテーブルは組み合わせであります 二つの異なる作品の これで、私たちは慣れています。 最初は、どの機能であります 我々は通常、ハッシュ関数を呼び出します。 そして、そのハッシュ関数をしようとしています 、いくつかの負でない整数を返しました 我々は通常、[OK]、ハッシュコードを呼び出しますか？ 二枚です配列です タイプ我々のデータを記憶することができます データ構造に配置します。 私たちは、上の延期ます 今のリンクリスト要素 だけの基礎で始まります その周りにあなたの頭を取得するには、ハッシュテーブル、 し、我々は多分打撃よ あなたの心は少しときに我々 一緒に配列やリンクリストを兼ね備えています。 

基本的な考え方けれども 我々はいくつかのデータを取ることです。 私たちは、そのデータを介して実行します ハッシュ関数。 それでデータが処理され、 そして、それはOK、数を出してくれるか？ そして、その番号の 私たちはデータを保存します 我々はに格納します その位置での配列。 したがって、たとえば、私たちは多分持っています 文字列のこのハッシュテーブル。 それはそう、その中に10個の要素を持っています 我々はそれに10の文字列を収めることができます。 

我々はジョンをハッシュしたいとしましょう​​。 だからジョンはデータとして、我々は挿入したいです どこかにこのハッシュテーブルに。 我々はそれをどこに置けばいいの？ まあ、一般的で 配列これまでに我々はおそらく アレイ位置0にそれを置くことになります。 しかし、今、私たちはこの新しいハッシュ関数を持っています。 

そして、我々はジョンを実行するとしましょう このハッシュ関数を介して、 それは4を出してくれるです。 私たちがしているところまあ、それはです ジョンを配置するつもり。 私たちは、アレイの場所にジョンを入れたいです 4、我々はハッシュしまうとジョンagain-- それでは、後で私たちをしましょう 検索して見てみたいです ジョンはこのハッシュに存在する場合 私たちが行うために必要なすべてをtable-- 同じハッシュを介して実行されます 関数、数4アウトを取得し、 ジョンを見つけることができます すぐに我々のデータ構造です。 これはかなり良いです。 

我々は今、これを行うとしましょう 再び、我々はポールをハッシュします。 我々はポールを追加します このハッシュテーブルに。 のは、この時間は私たちが実行していることを言ってみましょう ハッシュ関数を介して、ポール、 生成されたハッシュコードは6です。 まあ今はポールを置くことができます アレイ位置6インチ そして、私たちがいるかどうかを確認する必要がある場合は ポールはこのハッシュテーブルにあります、 私たちが行う必要があるのはポールを実行しています ハッシュ関数を介して、再び そして我々は再び6アウトを取得するつもりです。 

そして、我々はただ見て アレイ位置6に。 ポールはありますか？ もしそうであれば、彼はハッシュテーブルにあります。 ポールはありませんか？ 彼は、ハッシュテーブルにはありません。 それはかなり簡単です。 

今、どのようにハッシュ関数を定義していますか？ まあに制限は本当にありません 可能なハッシュ関数の数。 実際の数は、実際にあります インターネット上で本当に良いもの。 実際の数があります、 インターネット上では本当に悪いもの。 また、非常に簡単です 悪いものを書き込みます。 

それでは、良いを構成します ハッシュ関数は、右？ まあ良いハッシュ関数べき ハッシュされたデータのみを使用し、 そして、、すべてのデータは、ハッシュ化されています。 だから我々はanything--使用したくありません 私たちは何かを組み込んでいません データ以外の他の。 そして、我々は、すべてのデータを使用します。 私達はちょうど作品を使用する必要はありません それを、我々はそれをすべて使用します。 ハッシュ関数べき また、決定論的です。 どういう意味ですか？ まあそれはつまりたびに、私たち データの正確な同じ部分に合格 ハッシュ関数は常に私たちに 同じハッシュコードを出します。 私はにジョンを渡した場合 ハッシュ関数は、私は4を得ます。 私はそれを行うことができるはず万 時間と私はいつも4を取得します。 だから、無乱数効果 私たちのハッシュに関与することができtables-- 私たちのハッシュ関数です。 

ハッシュ関数はまたべき 均一にデータを配布します。 たびにあなたがを介してデータを実行した場合 ハッシュ関数は、ハッシュコード0を得ます それは右、おそらくそれほど大きくありませんの？ あなたは、おそらく大にしたいです ハッシュコードの範囲。 また、物事を広げることができます テーブル全体でアウト。 そしてまた、それがあれば、本当に素晴らしいことです ジョンとジョナサンのような同様のデータ、 多分比較検討することが広がりました ハッシュテーブル内の異なる場所。 それは素敵な有利であろう。 

ここでは、ハッシュ関数の例です。 私は前にこの1を書きました。 それは特にありません 良いハッシュ関数 本当にない理由のために 今に入る負うものとします。 しかし、あなたはここで何が起こっているの見ていますか？ 我々は変数を宣言しているように思えます 和と呼ばれ、0に等しい、それを設定します。 そして、どうやら私は何かをやっています そう長くはstrstr [j]が等しくないとして バックスラッシュを0に。 私はそこに何をしているのですか？ 

これは、基本的にちょうど別です [を実装する方法はありますか？技研？] あなたがきたときを検出 文字列の末尾に到達しました。 だから私は実際にはありません 文字列の長さを計算し、 私が打つとき、私はちょうど使用しています バックスラッシュ0の文字私が知っています 私は、文字列の最後に到達しました。 そして私は続けるつもりです その文字列を反復処理、 合計する[j]をはstrstrを加え、その後に 一日の終わりには、和のmodを返しに行きます HASH_MAX。 

基本的にはすべてこのハッシュ 関数が合算されています のASCII値のすべて 私の文字列が、それはです いくつかのハッシュコードを返します HASH_MAXによってモッド。 それはおそらく大きさです 私の配列の、右？ 私はハッシュを取得する必要はありません コー​​ド私の配列のサイズが10である場合、 私が取得する必要はありません アウトハッシュコード11、12、 13、私はに何かを置くことができません 配列のこれらの位置、 それは違法になります。 私は、セグメンテーションフォールトを被るだろう。 

今ここに、別のクイックはさておきです。 一般的に、あなたはおそらくするつもりはありません 独自のハッシュ関数を書きたいです。 これは、実際のビットです 芸術、科学ではありません。 そして、彼らに入るがたくさんあり​​ます。 インターネットは、私が言ったように、いっぱいです 本当に良いハッシュ関数の、 あなたがインターネットを使用する必要があります それは本当にだからハッシュ関数を見つけます 不必要なだけの種類 独自に作成するための時間の無駄。 

あなたはシンプルなものを書くことができます テスト目的のために。 しかし、あなたが実際に行っているとき データをハッシュし、それを保存を開始 ハッシュテーブルにあなたがいます おそらくするつもり 生成されたいくつかの機能を使用するには あなたのために、それは、インターネット上に存在します。 あなただけ必ずしなければ あなたのソースを引用します。 理由はありません ここで何かを盗用。 

コンピュータサイエンスのコミュニティです 間違いなく成長していると、本当に値 オープンソース、それは本当に重要です あなたのソースを引用することにより、人々 以下のための帰属を得ることができます 彼らがしている仕事 社会の利益のためにやって。 だから、常にsure--こと だけではなく、ハッシュのために 一般的に機能しますが、ときに 外部ソースからのコードを使用し、 常にあなたのソースを引用しています。 やった人に信用を与えます あなたがする必要はありませんので、作品の一部。 

[OK]それでは、これを再検討しましょう 第二のハッシュテーブルです。 我々は左の場所です 我々は挿入後にオフ このハッシュテーブルにジョンとポール。 あなたはここでの問題を参照していますか？ 次の2つが表示される場合があります。 しかし、特に、あなたを行います この問題の可能性を参照してください？ 

私はリンゴをハッシュし、その場合 処理した後ことが判明 ハッシュ関数を介して、そのデータ リンゴもハッシュコード6を生成しました。 私はすでにでデータを持っています hashcode--アレイ位置6。 だから、おそらく少しになるだろう 今の私のための問題の、右？ 

私たちは、衝突、これを呼び出します。 そして、衝突が発生したときに、2つの 同じハッシュを通るデータの断片 この関数は、同じハッシュコードをもたらします。 おそらく、我々はまだ両方を取得したいです ハッシュテーブルへのデータの片 そうでなければ、私たちはリンゴを実行されません 任意のハッシュ関数を通じて。 私たちは、おそらく取得したいです その配列にリンゴ。 

彼ならば、我々は、しかし、それをどのようにをしますか ポールは、両方のハッシュコード6が得？ 私たちは、パウ​​ロを上書きしたくありません、 私たちは、パウ​​ロはあまりにもそこになりたいです。 だから我々は、取得する方法を見つける必要があります ハッシュテーブルに要素をその まだ私たちの迅速なを保持し 挿入とクイックルックアップ。 そして、それに対処するための1つの方法はにあります プロービング線形と呼ばれる何かをします。 

我々が持っている場合は、この方法を使用します 衝突は、よく、私たちは何をしていますか？ さて、私たちは、アレイの場所に彼を置くことができません 6、または任意のハッシュコードを生成しました、 ハッシュコードはプラス1で彼を入れてみましょう。 そしてそれは完全レッツだ場合 ハッシュコードプラス2に彼を置きます。 彼がいた場合、この幸福の利益 ない正確に我々は彼があると思う場合は、 我々は検索を開始する必要があり、 多分私達はあまりにも遠くに行く必要はありません。 多分、我々は、検索する必要はありません ハッシュテーブルのすべてのn個の要素。 多分、我々は、検索する必要が それらのカップル。 

だから我々はまだ方向に収束しています その平均的なケースは、1対に近いです Nに近いので、多分それが動作します。 それでは、どのようにこれを見てみましょう 現実に出て働くかもしれません。 そして多分私達が検出できる場合を見てみましょう ここで発生する可能性がある問題。 

我々はバートをハッシュとしましょう​​。 だから今、私たちは新しいセットを実行するつもりです ハッシュ関数を介して、文字列の、 私たちは、ハッシュを介しバートを実行します 機能、我々はハッシュコード6を得ます。 我々は6を参照して、外観をされ取ります 空、私たちはそこにバートを置くことができます。 

今、私たちはリサとそのハッシュ また、ハッシュコード6を生成します。 さて、私たちはこれを使用していること 私たちは6で開始する方法をプロービング線形、 私たちは、6がいっぱいであることがわかります。 私たちは6でリサを置くことはできません。 だからここで私達は行くのですか？ 7に行きましょう。 7の空には、そのように動作します。 それでは、そこにリサを入れてみましょう。 

今、私たちはホーマーをハッシュし、我々は7を得ます。 [OK]をよく私たちはその7のフル知ります 今、私たちはそこにホーマーを置くことはできません。 それでは、8に行ってみましょう。 8は可能ですか？ うん、および7から8の近くに、そうであれば 私たちがしている検索を開始する必要があります 行き過ぎしているつもりはありません。 そしてそうのは8でホーマーを入れてみましょう。 

今、私たちは、マギーとハッシュ 3を返し、良さに感謝 私たちはそこにマギーを置くことができるしています。 我々は、いずれかを行う必要はありません そのため、プロービングの一種。 今、私たちは、マージをハッシュし、 マージはまた、6を返します。 

ウェル6は、8が一杯になる、7がいっぱいである、完全です 図9は、すべての権利9が空である、神に感謝します。 私は9でマージを置くことができます。 すでに我々は開始していることがわかります 今私たちがしているこの問題を持っています 親切な事を伸ばすために開始 遠くそのハッシュコードから。 1とθ、その平均 一定時間であることの場合、 少しmore--を取得し始めています もう少し傾向があるために開始 n個のシータに向けました。 我々はそれを失うことを開始しています ハッシュテーブルの利点。 

私たちは見て、この問題 クラスタリングと呼ばれるものです。 約本当に悪いものです クラスタリングは、あなたの一回になりました に並べている2つの要素を持っています それもやすくなる側 あなたは二重持っています チャンス、あなたが行っています 別の衝突を持っています そのクラスタと、 クラスタは、いずれかによって成長します。 そして、あなたが成長し、成長しておこう 衝突を持っていることのあなたの可能性。 そして、最終的には同じように悪いです すべてのデータを並べ替えていないとして。 

他の問題は、しかし、私たちです まだ、これまでにこの時点まで、 私たちは、ソートのしてきました ハッシュテーブルが何であるかを理解し、 我々はまだのみ10文字列のための部屋を持っています。 私たちは、ハッシュを継続したい場合は スプリングフィールドの市民、 我々はそこだけでそれらの10を得ることができます。 そして、我々は、試してみて、11日または12日を追加した場合 私たちはそれらを置く場所がありません。 私達はちょうどの周り紡績することができ 円は、何もない場所を見つけよう 私たちは多分立ち往生 無限ループインチ 

だから、考えに貸すこの種の 連鎖と呼ばれるものの。 そして、これは我々が持って行っているところであります バック画像にリンクされたリスト。 どのような場合だけではなく保存します 配列内のデータ自体、 配列の各要素にはできました 複数のデータを保持しますか？ まあそれは右、意味がありませんか？ 私たちは、配列のみをすることができます知っています 配列の各要素をhold-- 一つだけを保持することができます そのデータ型のデータ。 

しかし、どのような場合、そのデータ型 リンクリストは、右ですか？ だから何ごとであれば 配列の要素ました リンクリストの先頭へのポインタ？ そして、我々が構築できます それらのリンクリスト そして、、任意にそれらを育てます リンクされたリストができるので 私たちは成長し、より多くの縮小します 柔軟アレイはよりも。 それでは、私たちが今使用している場合、 我々は正しい、これを活用しますか？ 私たちはこれらの鎖を成長し始めます これらの配列位置のうち。 

今、私たちは無限に合うことができます データの量、または無限ではありません、 任意の量 私たちのハッシュテーブルにデータ、 これまでに実行せず 衝突の問題。 また、排除しました これを行うことにより、クラスタリング。 そして、よく私たちは挿入​​したときにことを知っています リンクされたリストに、あなたが思い出す場合 単独で、リンクされたリスト上の私たちのビデオから リンクされたリストと二重リンクリスト、 それは、一定時間操作です。 私達はちょうど前に追加しています。 

そして、ルックアップのために、よく私たちは知っています それは、リンクされたリストで調べます 右、問題になることができますか？ 私たちは、全体を検索する必要があります 最初からそれが終了します。 全くランダムはありません リンクされたリスト内のアクセス。 しかし、もし代わりに、1つを有するのリンク ルックアップは、nのO、になるリスト 我々は今、10リンクリストを持っています、 または千リンクリスト、 今では、10で割ったn個のOです あるいはnのO 1000で割ったもの。 

そして、我々は話をしている間 理論的には複雑さについて 我々はリアルタイムで、定数を無視 これらのことは、実際には問題の世界、 右？ 私たちは実際に気づくでしょう この問題が発生したこと より速い10回実行するには、 または1000倍速く、 私たちは長いものを配布しているので、 千小さいチェーン全体のチェーン。 だから私たちが持っているたびに検索します 私たちすることができますこれらのチェインのうちの1つを介して 私たちは気にしない999チェーンを無視 そしてちょうどそのいずれかを検索します。 

これに平均であります 1000倍短いこと。 だから我々はまだ一種のです この平均的なケースの方に傾向 一定の時間であるが、 我々は活用されているという理由だけで いくつかの巨大な一定の係数で割ます。 これはどのようにかもしれない見てみましょう 実際にかかわらず、見て。 だから、これは私達が持っていたハッシュテーブルでした 私たちは、そのハッシュテーブルを宣言する前に、 10文字列を格納することができました。 私たちはもうそれをするつもりはありません。 我々はすでに知っています その方法の限界。 現在、私たちのハッシュテーブルがあることになるだろう 10ノード、ポインタの配列 リンクリストの頭に。 

そして今は、nullです。 これらの10のポインタのそれぞれはnullです。 何も私たちにはありません 今の表をハッシュ。 

それでは、いくつかを置くために始めましょう このハッシュテーブルに物事。 そして、のは、このメソッドがどのように見てみましょう 私たちに少しの利益のために行きます。 今度はジョーイをハッシュしてみましょう。 私たちは、文字列ジョーイを通じて実行されますよ ハッシュ関数、我々は6を返します。 さて、私たちは今何をしますか？ 

さてリンクリストでの作業、 私たちは、配列を使用していません。 そして、私たちが作業しているとき リンクリストと我々 我々は動的に開始する必要があります知っています スペースや建物のチェーンを割り当てます。 それは一種のものが中心ですhow--です リンクリストを構築するための要素。 だから、動的にしてみましょう ジョーイのためのスペースを割り当て、 そしてその後のチェーンに彼を追加してみましょう。 

だから今私たちが何をやったかに見えます。 我々はジョーイをハッシュするとき、我々はハッシュコード6を得ました。 アレイ位置6で今すぐポインタ リンクリストの先頭を指し、 そして今それだけです リンクされたリストの要素。 そして、その内のノード リンクリストは、ジョーイです。 

だから我々はジョーイをルックアップする必要がある場合 それ以降、私たちは、再びジョーイをハッシュ 私たちのために我々は再び6を取得 ハッシュ関数は、決定論的です。 そして、我々は先頭にスタート リンクリストの指摘 アレイ位置によって 6、私たちは繰り返すことができます ジョーイを見つけようと、その全体で。 そして、我々はをビルドする場合 、効率的にテーブルをハッシュ 効果的に、私たちのハッシュ関数 よくデータを配信するために、 平均してそれらの各々は、リンクされました すべての配列位置でのリスト 我々の場合の10分の1サイズになります 単に1つの巨大なようにそれを持っていました その中にすべてのものを持つリンクリスト。 

我々は巨大ながリンクされていることを配布する場合 10リンクリスト全体のリスト 各リストは1/10サイズになります。 そして、このように10倍速く 検索します。 それでは、再びこれをしましょう​​。 今度はロスをハッシュしてみましょう。 

そして、我々はそれを行うときのは、ロスを言わせて 我々は戻っハッシュコードは2です。 まあ今は動的に割り当て 新しいノード、我々は、そのノードでロスを置きます 私たちは今、アレイ位置を言います 2、代わりにヌルを指し、 リンクの先頭にポイント その唯一のノードリストは、ロスです。 そして、我々は、我々がこの1つのより多くの時間を行うことができます レイチェルをハッシュし、ハッシュコード4を得ることができます。 でレイチェルを入れて、新しいノードををmalloc アレイ位置をノードと言います 4今の頭を指し そのリンクリストの 唯一の要素は、レイチェルであることを起こります。 

[OK]が、どのような場合に起こります 我々は、衝突がありますか？ 我々は、衝突を扱う方法を見てみましょう 別個の連鎖方法を用いて。 のはフィービーをハッシュしてみましょう。 私たちは、ハッシュコード6を得ます。 前の例では、ちょうどでした 配列内の文字列を格納します。 これが問題でした。 

我々は壊したくありません ジョーイ、私たちはすでにしました 我々はいくつかのクラスタリングを得ることができることがわかります 問題我々がしようとした場合、ステップ 通って、プローブ。 しかし、どのような場合、私たちだけの種類 これは右、同じように扱いますか？ それだけで要素を追加するようなものです リンクリストの先頭に。 フィービーのためのただのmallocスペースをしてみましょう。 

我々はフィービーの次のポインタポイントを言いますよ リンクリストの古い頭に、 し、その後6だけを指します 連結リストの新しいヘッド。 そして今、我々はでフィービーを変更した、見て。 私たちは今、2を格納することができます ハッシュコード6を持つ要素、 私たちは何の問題もありません。 

それはほとんどすべてです チェーンにあります。 チェーンは間違いなくあります だ方法 場合あなたのために最も効果的になるだろう あなたはハッシュテーブルにデータを格納しています。 しかし、この組み合わせ 配列やリンクリスト 一緒に実際にハッシュテーブルを形成します 劇的にあなたの能力を向上させます 大量のデータを格納する、及び 非常に迅速かつ効率的に検索 そのデータを通じ。 

もう一つは、まだあります そこにデータ構造 それが少しでもあるかもしれません 保証の面でより良いです 我々の挿入、欠失、およびその ルックアップする時間があっても高速です。 そして、我々は試行のビデオでそれを見ることができます。 私はダグロイドだけど、これはCS50です。