So update's going to be pretty similar to look
up. So let's start by copying that code and
seeing how we need to change it. So we
have lookup. We're going to change it to be update.
Now instead of taking a key as its input, it's going to take a key and a value.
But it's not going to return anything, so we're going to get rid
of the returns. Right. remember all update is doing is modifying the
value of entry. So now we still have what we had for
lookup, we're still getting the bucket and we want to do that.
We want to make sure that we update the value in the
right bucket. We still need to look through the entries in the
bucket, to find if one matches. If we find one that matches,
well what we did in lookup, was just return it. And update,
what we want to do is change the value associated with
that key. So we are going to have an assignment that replaces
whatever value is there before with a new value. And now
instead of returning the value, we want to stop going through the
loop, and we actually are done with update, so we can
return here. We found the entry, we updated the value. We
also need to deal with a case where we didn't find
the entry. So now we've gone through the loop enough times.
When it was a look-up we just returned none. When it's
an update what we want to do when the key is not
already in the table, is add it. So now we're going
to use, append, to add a new entry to bucket, that has
the key and the value. So that's how we defined update.
There's certainly lots of other ways to do it, and one
thing you should be thinking about is, well this is actually
very similar to look up, right. We duplicated a lot of code.
Maybe there's a way to define update and lookup so
we don't have to have two copies of the code,
that scans through the bucket to find the right entry.
We'll leave that as a homework question for this unit.
For now we're going to be happy that we've got correct
implementations of both lookup and update. And, let's test them.
So, what we did before, we're going to replace the adds
with updates, and now, the second time, what happened with
the add was we added an entry, but we could
never reach that entry because it had the same keyword.
Now we're used update, the second time we should be
updating that value, and we'll see that the lookup now produces
the value 27, for the second lookup. That's good, right,
the first time the value was 23. We did the update,
we got 27, and we can see that the bucket
only contains one entry. So this is great, we finished our
implementation of the hash table. We can do updates that will
either add new values to the hash table, if they don't
already exist, or change the value of ones that exist. And
we can do lookups and lookup will know where to look, which
bucket to look in to find that key, if it exists.
So this has the great property that as the number of keys
increase. As long as we increase the numbers of buckets accordingly,
the time to do both an update and a lookup is constant.
This means the time doesn't increase even as the number of keywords increases,
as long as we increase the number of buckets. So, this size of
each bucket stays the same size, because the expensive cost of this is
going through the elements in the bucket looking for the key that matches.
アップデートはlookupとよく似ています
そのコードをコピーしどのように変更するか
確認することから始めましょう
lookupがあります これをupdateに変更します
入力としてキーのみではなくキーと値を使用します
ですが何も返しませんのでreturnを削除します
updateで行うのはエントリの値の
修正だということを忘れないでください
lookupのためのコードがまだあります
バケットをまだ取得しますがこれは必要な処理です
適切なバケットで値を更新しますが
一致するか調べるためにバケットのエントリを
1つずつ見る必要がまだあります
一致するものを見つけた時
lookupで行ったのはそれを返すことです
updateの場合はそのキーに関連する値を更新します
ですから新たな値にする前に
どんな値でも置き換えられる代入をします
そして値を返す代わりに
ループを停止させる必要があります
これでupdateは終了でここに戻ります
エントリを見つけ値を更新しました
エントリが見つからない場合の対処も必要です
ですから十分な時間のループを行っています
lookupの時はNoneを返すだけでした
updateで行うことはキーがテーブルにない場合
それを追加することです
ここでappendを使用し
新たなエントリをバケットに追加します
これにはキーと値があります
これがupdateを定義する方法です
もちろん他にもたくさんの方法があります
1つ考えるべきことは
実際にこれはlookupとよく似ているということです
たくさんのコードが重複しました
updateとlookupを定義する方法が
あるかもしれません
そうすれば適切なエントリを見つけるために
バケットをスキャンするコードのコピーを
2つ持つ必要がありません
これをこのレッスンのホームワーク問題にします
今のところはlookupとupdate両方の実装が
正しくできたことを喜んでください
さあテストしてみましょう
以前行ったことですがaddをupdateに置き換えます
今回は2度目です
addで行ったのはエントリを追加したことです
しかしそのエントリに達することはありませんでした
なぜなら同じキーワードがあったからです
ですからupdateを使用し
2度目はその値を更新する必要があります
lookupが2度目のlookupで
値27を返しているのが確認できます いいですね
1度目の値は23でした
updateを行い27を取得しました
バケットが1つのエントリだけを含んでいるのが
確認できます
ハッシュテーブルの実装を完了しました
キーワードが存在していなくても
ハッシュテーブルに新たな値を追加する
または既存のキーワードの値を
変更するupdateが行えます
そして私たちはlookupができ
キーが存在していればそれを見つけるために
lookupはどのバケットを調べるか把握するでしょう
キー数が増えるという
すばらしいプロパティを持っています
それに応じてバケット数が増える限り
updateとlookupを行う時間は変わりません
つまりたとえキーワード数が増えても
バケット数も増える限り
時間は増えないということです
ですから各バケットのサイズは同じままです
なぜならメモリ数を多く使うのは
一致するキーを探すバケット内の各要素を
探すことだからです