前回の終わりに「次は throwing function と autoclosure あたりを眺めてみよう」と話してましたけれど、先日の iOS インターン成果報告会で ハッシュ に関する話題が挙がって、思いのほか混乱しがちな分野に感じたのと、話していく中で自分自身も思い違いしている部分にも気づいたりしたので、今回はちょっと寄り道をして ハッシュ 周りの基本的なところを再確認していってみようと思います。よろしくお願いしますね。
今回は参加者の一般参加者を募って、ゆめみの外の人たちも訪れての開催になる見通しです。
——————————————————————————————————————————— 熊谷さんのやさしい Swift 勉強会 #197
00:00 開始 00:10 前回の修正と補足 01:56 Hashable な値そのものの比較は速くならない 03:23 NSString なら ObjectIdentifier で一致することも 03:57 ハッシュ値の比較自体の速度観察 04:24 Swift の Hashable は比較も可能 07:13 タスク完了までの経過時間を取得 10:55 Dispatch を使って再挑戦 12:44 hashValue を使う方が遅い様子 15:44 String のハッシュ値 17:46 ハッシュ値の計算量 19:20 予測できないハッシュ値の生成 21:20 ハッシュの目的 26:17 クロージング ———————————————————————————————————————————
Transcription & Summarize : 熊谷さんのやさしい Swift 勉強会 #197
さて、始めていきましょうかね。ハッシュについてどの話から始めますかね。調べてみると意外と前回言ってたことが数字違いだったなというところがあって、その数字違いのところから話すべきなのかどうかわからないけど、まずはその話から始めていきます。
前回、ハッシュの比較が早くなるみたいな話をしました。これはある意味正しいのですが、ハッシュ値そのものの比較が早くなるものと勘違いしてしまっていた感じがあります。たとえば、ある値 hashable 同士の比較についてです。具体的には、文字列のキー1とキー2があって、この2つのキー同士が同じか違うかを早く比較できるという話になっていました。あくまでもハッシュテーブルを使ったときに早く見つけられるよという話だったかと思います。
ところが、実際にはキーそのものの一致が早いかどうかをハッシュハッシャブルによって判定できると思っていました。確かに、ハッシュ値を取り終わった後であれば比較は早いのですが、そのときも指摘があったように、ハッシュ値を計算するためには一定のコストがかかります。実際、Swiftのソースコードを見てみると、文字列のハッシュ値を取るときには計算が行われています。
したがって、キー1とキー2を純粋に比較するのと、キー1とキー2のハッシュ値を比較するのでは、必ずしもハッシュ値の方が早くなるというわけではありません。文字列の場合は特に、C言語系の文字列の内部保存方法などによる影響があります。例えば、Objective-CのNSStringの場合、同じ値であれば同じインスタンスを指すような最適化がされているため、純粋な文字列比較がかなり最適化されていることもあります。
ここが自分がちょっと勘違いしていたところで、実際に本当にそうかどうかも計算してみましょう。あるHashable な値 a があって、これを例えば以下のように比較するコードを書いてみます。
struct MyStruct: Hashable {
let value: String
}
let a = MyStruct(value: "a")
let b = MyStruct(value: "a")
if a == b {
print("Equal")
} else {
print("Not Equal")
}
例えば、2つの関数 compareDirectly と compareUsingHash を定義し、これらを使って比較してみようと思います。
func compareDirectly() {
let startTime = Date()
for _ in 0..<10000 {
_ = a == b
}
let endTime = Date()
print("Direct comparison took \\(endTime.timeIntervalSince(startTime)) seconds")
}
func compareUsingHash() {
let startTime = Date()
for _ in 0..<10000 {
_ = a.hashValue == b.hashValue
}
let endTime = Date()
print("Hash comparison took \\(endTime.timeIntervalSince(startTime)) seconds")
}
compareDirectly()
compareUsingHash()
これを実行してみると、どちらが早いか分かるかと思います。もちろん、計測の仕方や環境によって結果が変わることもあるので、あくまで参考程度に見てください。
実際に実行すると、比較のためのコストがどの程度かかっているかを感じ取ることができます。ハッシュ値の計算自体も時間がかかる場合があるので、その辺りも考慮する必要があります。
以上がハッシュ値の比較についての話でした。次に、Swift の Hashable の実装方法などについてもう少し掘り下げてみましょう。 次はプログラミングの実践に入ります。まずはコードについての話ですが、以下のように書くことで結果が確認できます。
DispatchQueue.global().async {
executeA()
executeB()
}
上記のようにすれば止まることが少なくなり、ディスパッチキューを使って非同期に処理を行うことができます。これにより、同期的な await を使わずにすみますので、処理がブロックされることもありません。
次に進む前に、コードの実行環境であるPlaygroundでの確認をしましょう。Playgroundでは以下のようにすることで、無限ループを実行することができます。
import PlaygroundSupport
PlaygroundPage.current.needsIndefiniteExecution = true
これを行うことで、Playgroundのページが無限に実行される状態になります。次に、この設定をした上で再度コードを確認してみましょう。
なお、asyncとdispatchの使い方にも触れておきます。例えば以下のコードのように、ディスパッチキューで非同期処理を行う場合の記述方法です。
DispatchQueue.global().async {
// 実行したい処理
executeA()
executeB()
}
これにより、処理が非同期に実行されるため、メインスレッドのブロックを防ぎます。もし、この中で何かクラッシュやエラーが発生した場合は、その原因を詳細にデバッグする必要があります。
さらには、Swiftの標準ライブラリを使った処理の速度についても見ておきましょう。Swiftでは、。Equatableプロトコルを実装することで、オブジェクトの比較が可能になります。ただし、Hashableの方が速度的には若干早い場合もあります。
struct MyStruct: Hashable {
var id: Int
}
このようにしてMyStructがHashableプロトコルを準拠すると、その後のハッシュ計算などが効率よく行えます。
また、長い文字列のハッシュ化も検討する必要があります。長い文字列をハッシュ化する際には、内部バッファの処理単位でハッシュ計算が行われますので、その速度の違いも理解しておくとよいでしょう。
ここまで説明したように、非同期処理やプロトコルの実装方法、そして内部処理の詳細について確認することで、より効率的なプログラミングが可能になります。 ハッシュという言葉についてです。ハッシュは特定の意味を持つ言葉ですが、ここでは文脈によって理解が変わりますね。実際にはハッシュに関する話題は、多岐にわたると思います。
つまり、全体を並べてみて少しずつ変化していくと理解すべきです。バッファーコードを見て確認する必要がありますが、バッファーコードの時間に関わらないため、物によるかもしれません。それは実装方法によって違ってくるのです。ソースコードのサイズや、何を見るかによっても異なります。
具体的には、ソースボックスファイルやREADMEファイルを見ているのか、ソースのスタンダードライブラリーの中にStringがHashableであることが確認できます。エクステンションされている部分を見ると、StringがHashableになっており、hash(into:)メソッドを使っていることがわかります。
例えば、UTF-8エンコードの文字列に対してハッシュ値を計算するとき、そのバイトを渡す操作を行っているかもしれません。これも実装に依存し、ソースコードのループなどに細かく影響してきます。
コメントでピーターさんの話もありますが、確かに、ハッシュ値をキャッシュしておくと比較が早くなります。キャッシュなしの場合はどうしても遅くなります。名前がパッと見悪いので、「ハッシュバリュー」という名前に変更したほうがいいかもしれません。Appleが公式に使っているように、ユーザーにとってわかりやすい名前にしましょう。
また、ガイドラインでは、コンピューテッドプロパティはO(1)である必要があるという指摘も正しいです。Swiftのガイドラインに基づいていない場合、コンパイン（combine）する必要があるため、計算量が増えてしまいます。内部的にキャッシュしていればO(1)になるかもしれませんが、そうでない場合はO(n)になりますね。
このように、ハッシュに関する具体的な実装やガイドラインに基づいた設計は重要です。全体の計算量やハッシュの効率化を考慮しながら、プロパティの設計も検討しましょう。 とりあえずね、一般的には自分もとんでもない勘違いをしていたんですよ。思い返せば、確かにそうなんですよね。微妙な違和感というのを感じるとき、それを拾えるかどうかで、プログラマーに限らず、より安全に進んでいけるかどうかの境目です。
Swift 4.2から、昔は、例えば整数型だったら同じハッシュ値を返してしまうことがあって、それによってハッシュ値と普通の値との一致性を混同してしまうことがありました。しかし、Swift 4.2以降ではハッシュが完全にランダムで変わるようになりました。ランタイム中は同じハッシュ値が返されますが、次の実行時には同じハッシュ値になるとは限りません。ハッシュの計算速度を求めていないので、乱数を出している時点で時間はかかるのですが、それでも安全性を考慮した結果です。
ハッシュ値に関する違和感を感じ取れるかどうかが、勘違いに気付けるポイントです。ハッシュ値というものが何なのか、調べてみると、ハッシュというのはあるデータから算出した小さな値、つまりハッシュ関数によってある値にマッピングすることです。このハッシュ値が暗号学的なものであるかどうか、例えばパスワードとかの応用に使うハッシュなど、さまざまな種類があります。
ハッシュ関数にはいろいろな性質があり、それをどう応用するかによって目的も変わります。例えば、検索や探索の法則をデータの中から目的のデータを探すときに使います。ディクショナリーのキーとしてハッシュ値を使用することで、ディクショナリー自体の操作が高速化されます。また、ファイルのダウンロード時にMD5ハッシュ値を用いてファイルの整合性を確認することもあります。
ハッシュはパスワードの認証にも応用されます。手元でパスワードをハッシュして、そのハッシュ値を送信、データベース上のハッシュ値と比較することで、パスワードを見せずに認証を行うことができます。
こうしたハッシュの応用方法は多岐にわたります。だからこそ、ハッシュに対する理解が深まれば、それだけ確実にプログラムを設計する上での安全性が増します。
以上で、ハッシュについての説明を終わりにします。今日はこれで勉強会を終了しますね。お疲れ様でした。ありがとうございました。