So let's try to define a hash function
that has these properties. And what we want the
hash function to do is to take a string
as its input, we'll call the hash function hash_string,
and it'll produce as output a number between 0
and b. So, we also need another input to
our hash string, which is going to be the size
of the hash table. So that'll be the second
input is the size of the hash table, the
number of buckets. What we haven't seen yet, that
we're going to need for this function, is a way
to turn a string into a number. Python provides an
operation to do that. It's called ord as an
ordinal, and what ord takes as it's input is
a one letter string and produces as it's output
a number. And actual mapping between strings and numbers is
not so important. We just want something
that is going to map different string to
different numbers. There's another operator that goes in
the opposite direction that takes in a number,
and outputs the one-letter string that corresponds to
that number. And the property these functions have
is their inverses. That if we take the
character corresponding to the ordinal corresponding to any
one-letter string. We'll call that alpha. What we get as a result is the same
alpha that we passed in. So let's try
a few examples in the python interpreter to
see how ord and chr work. So we'll print ord of a, and
when we run that we see we get the number 97. If we try print ord of capital A.
That's different. We get 65. And if we print ord of B,
we get 66. So, the numbers are sort of sensible.
B is higher than A. The lower case letters have
different ordinals than the upper case. So, if we try
a lower case b, we should expect to get 98.
And that is indeed what we get. And these are
the numbers based on the ASCII enchar, character encoding, what
the actual numbers are, are not very important for us,
other than that we get different number for different letters.
So we'll be able to use the results
of ord to make different strings hash to different
values. And just to show that there are inter, inverses. If we do ord of u, and
then chart of that, what we get back
is the single letter string u that we started
with. The limit of ord is it only works
on one-letter strings. If it provided a mapping from
any string to a number that would be useful for a
hash table. Well, then we'd be done. But it doesn't do that.
If we try running it on a multi-letter string, we get
an error. It says that ord expects a single character, but it
got a string of length 7. So we're going to need to
use ord only on single letter strings. So with ord, we have
a way of converting strings to numbers. Converting single character strengths
to numbers. The other property we need our hash function to have,
is that our output number is always between 0 and B minus 1. We need it to be in
that range, because we're going to use that to index
the list, to find the bucket where that string belongs.
これらのプロパティを持つハッシュ関数を
定義してみましょう
ハッシュ関数に行わせたいことは
入力として文字列を使用することです
この関数をhash_stringと呼びましょう
出力としてゼロとbの間の数値を生成します
また別の入力もhash_stringにする必要があります
それがハッシュテーブルのサイズになります
それによって2つ目の入力がハッシュテーブルの入力
つまりバケット数になります
まだ学習していませんが
この関数に必要となるのが文字列を数値に
変換する方法です
Pythonがその関数を組み込んでいます
ordinalのordと呼ばれるものです
ordは入力として1文字の文字列を用い
その出力として数値を生成します
文字列と数値の実際の対応づけは
あまり重要ではありません
必要なのは異なる文字列を
異なる数値に対応づけることです
これとは反対に数値を用いて
数値に対応する1文字の文字列を出力する
別の演算子があります
これらの関数は反比例します
ある1文字の文字列に対応する序数に
対応する文字を使用する場合です
これをアルファと呼びます
結果として得られるものは渡した同じアルファです
ordとchrがどのように機能するのか確認するため
Pythonインタプリタで例を試してみましょう
aのordを出します
実行すると数値97を取得したことが確認できます
もし大文字のAのordを出すと
異なるものになります 65になりました
Bのordを出すと
66になります 数値はいくらか実用的です
BはAより高いです 小文字は大文字とは
異なる序数を有しています ですから小文字のbを
試してみると予想通り98になりました
それが実際に取得したものです
これらはASCII文字のコード化を基にした数値です
色々な文字の色々な数値を取得する以外に
実際の数は私たちにはあまり重要ではありません
様々な値の様々な文字列のハッシュを作成するために
ordの結果を使用します
逆があることを示すために
chr(ord(‘u’))を実行すれば
開始した1文字の文字列uを得ました
ordの制限は1文字の文字列のみ処理することです
文字列と数値の対応づけが可能なら
ハッシュテーブルにとても役立ちます
ここで終了ですがまだ終わりません
もし複数の文字の文字列でそれを実行した場合
エラーが出ます
ordは1文字を求めていると示されます
しかし長さ7の文字列を取得しました
1文字の文字列でのみordを使用する必要があります
ordで文字列を数値に変換する方法があります
1文字の文字列を数に変換します
ハッシュ関数に必要な別のプロパティは
ゼロとbー1の間に常にある出力数です
文字列が属しているバケットを見つけるために
インデックスリストにそれを使用したいので
範囲内に収める必要があります