アルゴリズム

[水泳] Swift AlgorithmClub-ハッシュテーブル



Swift Algorithm Club Hash Table



この記事は正しいです スウィフトアルゴリズムクラブ 翻訳された記事。

スウィフトアルゴリズムクラブ はい raywenderlich.com Swiftを使用してアルゴリズムとデータ構造を実装するWebサイトのオープンソースプロジェクトは、現在GitHubで18000以上です。私はそれについて少し統計を持っています。約100のアルゴリズムとデータ構造があります。基本的に、それらはすべて、iOSerの学習アルゴリズムとデータ構造に適したリソースです。



andyRon / swift-algorithm-club-cn これは、Swift Algorithm Clubの私のプロジェクトであり、学習しながら翻訳します。能力が限られているため、エラーが見つかった場合、または翻訳が正しくない場合は、私を訂正して、プルリクエストを歓迎してください。興味があり時間のかかるパートナーも翻訳と学習に参加できます。もちろん、戴冠式を歓迎します。

この記事の翻訳されたテキストとコードを見ることができます swift-algorithm-club-cn /ハッシュテーブル



ハッシュ表

ハッシュテーブルを使用すると、「キー」を使用してオブジェクトを保存および取得できます。

ハッシュテーブルは、ディクショナリ、マップ、連想配列などの構造を実装するために使用されます。これらの構造はツリーまたは通常の配列で実装できますが、ハッシュテーブルを使用する方が効率的です。



これは、Swiftが組み込まれている理由も説明できます。Dictionary型要件キーの一致Hashable合意：内部Dictionaryここで学習するように、ハッシュテーブルの実装を使用します。

それはどのように機能しますか？

ハッシュテーブルは配列にすぎません。最初、この配列は空です。キーの下のハッシュテーブルに値を入力すると、そのキーを使用して配列内のインデックスが計算されます。これは例です：

hashTable['firstName'] = 'Steve' The hashTable array: +--------------+ | 0: | +--------------+ | 1: | +--------------+ | 2: | +--------------+ | 3: firstName |---> Steve +--------------+ | 4: | +--------------+ Copy code

この例では、キー'firstName'配列インデックス3にマップします。この例では、キー'firstName'配列インデックス3にマップします。

別のキーの下に値を追加すると、別の配列インデックスに配置されます。別のキーの下に値を追加すると、別の配列インデックスに配置されます。

hashTable['hobbies'] = 'Programming Swift' The hashTable array: +--------------+ | 0: | +--------------+ | 1: hobbies |---> Programming Swift +--------------+ | 2: | +--------------+ | 3: firstName |---> Steve +--------------+ | 4: | +--------------+ Copy code

秘訣は、ハッシュテーブルがこれらの配列インデックスにどのように応答するかです。そこでハッシュが登場します。次のステートメントを作成する場合、ここでの秘訣は、ハッシュテーブルがこれらの配列インデックスを計算する方法です。 。これがハッシュの出番です。次のステートメントを書くと、

hashTable['firstName'] = 'Steve' Copy code

キーを使用してテーブルをハッシュする'firstName'そしてそれについて尋ねるhashValue属性。したがって、キーはHashableプロトコルと一致する必要があります。

書き込むとき'firstName'.hashValue大きな整数を返すとき：-4799450059917011053。同じ、'hobbies'.hashValueハッシュ値は4799405060928805186です（表示される値は異なる場合があります）。

これらの数値は大きく、配列へのインデックスとして使用できます。そのうちの1つは負の値です。これらの大きな数値を使用可能にする一般的な方法は、最初にハッシュ値を正にし、次に配列サイズをモジュロ（余りを含む）にします。これは配列のインデックスです。

配列サイズは5なので、'firstName'キーのインデックスがabs(-4799450059917011053) % 5 = 3に変わります。計算できます'hobbies'配列インデックスは1（ 注釈： abs(4799450060928805186) % 5 = 1）。

このようにハッシュを使用すると、ディクショナリが有効になります。ハッシュテーブルで要素を見つけるには、キーのハッシュを使用して配列インデックスを取得してから、基になる配列で要素を検索する必要があります。これらの操作はすべて一定の時間を必要とするため、挿入、取得、および削除は次のようになります。 または（1） 。

注意： 配列内のオブジェクトの最終的な位置を予測することは困難です。したがって、ディクショナリはハッシュテーブル内の要素の特定の順序を保証しません。

衝突を避ける

問題があります。ハッシュ値のモジュラスと配列のサイズを使用するため、2つ以上のキーに同じ配列インデックスが与えられる場合があります。これは競合と呼ばれます。

競合を回避する1つの方法は、大きな配列を使用することです。これにより、2つのキーが同じインデックスにマップされる可能性が低くなります。もう1つのトリックは、配列サイズとして素数を使用することです。ただし、競合は必然的に発生するため、競合を処理する方法を見つける必要があります。

私たちのテーブルは小さいので、衝突しやすいです。たとえば、キー'lastName'配列のインデックスも3ですが、この配列のインデックスですでに値を上書きしたくありません。

競合を処理する一般的な方法は、チェーンを使用することです。配列は次のようになります。

buckets: +-----+ | 0 | +-----+ +----------------------------+ | 1 |---> | hobbies: Programming Swift | +-----+ +----------------------------+ | 2 | +-----+ +------------------+ +----------------+ | 3 |---> | firstName: Steve |---> | lastName: Jobs | +-----+ +------------------+ +----------------+ | 4 | +-----+ Copy code

リンクを使用すると、キーとその値は配列に直接保存されません。代わりに、各配列要素は0個以上のキーと値のペアのリストです。配列要素はよく呼ばれます バケツ （バケットとして翻訳できます）、リストは呼び出されます チェーン （チェーンとして翻訳することができます）。ここに5つあります たる それらのうちの2つ たる 持ってる 鎖 。他の3つ たる それらはすべて空です。

ハッシュテーブルからアイテムを取得するために次のステートメントを作成すると、

let x = hashTable['lastName'] Copy code

最初にハッシュキーを使用します'lastName'配列インデックス（3）を計算するには、バケット3にチェーンがあるため、リストをステップスルーして、'lastName'キーの値で検索します。これは、文字列比較を使用してキーを比較することによって行われます。ハッシュテーブルは、キーがチェーンの最後のアイテムに属しているかどうかを確認し、対応する値'Jobs'を返します。

このチェーンメカ​​ニズムを実装する一般的な方法は、リンクリストまたは他の配列を使用することです。チェーン内のアイテムの順序は重要ではないため、リストではなくコレクションと考えることができます。 （これで、「バケット」という用語の由来を想像することもできます。すべてのオブジェクトをまとめてバケットにダンプします。）

ハッシュテーブルでのアイテムの検索が遅くなるため、チェーンが長くなることはありません。理想的には、チェーンがまったくないのですが、実際には競合を回避することは不可能です。高品質のハッシュ関数を使用してハッシュテーブルに十分なバケットを提供することにより、競合を回避する可能性を高めることができます。

注意： チェーンの代替手段は「オープンアドレス法」です。アイデアはこれです：配列インデックスが使用されている場合、次の未使用のバケットに要素を配置します。この方法には、独自の長所と短所があります。

コード

Swiftでのハッシュテーブルの基本的な実装を見てみましょう。徐々に積み上げていきます。

public struct HashTable<Key: Hashable, Value> { private typealias Element = (key: Key, value: Value) private typealias Bucket = [Element] private var buckets: [Bucket] private(set) public var count = 0 public var isEmpty: Bool { return count == 0 } public init(capacity: Int) { assert(capacity > 0) buckets = Array<Bucket>(repeatElement([], count: capacity)) } Copy code

HashTableジェネリックコンテナであり、2つのジェネリック型にKey（Hashable）with Valueという名前が付けられています。また、他の2つのタイプも定義します。Elementチェーンで使用されるキーと値のペアであり、BucketそのようなElements配列です。

メインアレイ名buckets。初期化方法init(capacity)固定容量を使用してアレイのサイズを決定します。 count変数は、ハッシュテーブルに追加されたアイテムの数を追跡することもできます。

新しいハッシュテーブルオブジェクトを作成する方法の例：

var hashTable = HashTable<String, String>(capacity: 5) Copy code

ハッシュテーブルはまだ何もできないので、次の機能を追加しましょう。まず、指定されたキーの配列インデックスを計算するヘルパーメソッドを追加します。

private func index(forKey key: Key) -> Int { return abs(key.hashValue) % buckets.count } Copy code

これにより、前に見た計算が実行されます。キーhashValueバケットの絶対値は、バケット配列のサイズを法として計算されます。いくつかの異なる場所で使用されているため、独自の機能に配置しました。

ハッシュテーブルまたはディクショナリに関係する一般的なことは4つあります。

  • 新しい要素を挿入します

  • 新しい要素を挿入します

  • 要素を見つける

  • 既存の要素を更新する

  • 要素を削除

これらの構文は次のとおりです。

hashTable['firstName'] = 'Steve' // insert let x = hashTable['firstName'] // lookup hashTable['firstName'] = 'Tim' // update hashTable['firstName'] = nil // delete Copy code

subscriptも使用できますこの関数は次のすべてを実行します。

public subscript(key: Key) -> Value? { get { return value(forKey: key) } set { if let value = newValue { updateValue(value, forKey: key) } else { removeValue(forKey: key) } } } Copy code

これには、実際の作業を行うために3つのヘルパー関数が必要です。ハッシュテーブルからオブジェクトを取得するvalue(forKey:)を見てみましょう。

public func value(forKey key: Key) -> Value? { let index = self.index(forKey: key) for element in buckets[index] { if element.key == key { return element.value } } return nil // key not in hash table } Copy code

まず、index(forKey:)キーを配列インデックスに変換します。これによりバケット番号がわかりますが、衝突が発生した場合、このバケットは複数のキーで使用される可能性があります。value(forKey:)バケットからチェーンをループし、キーを1つずつ比較します。見つかった場合は対応する値を返し、見つからなかった場合はnilを返します。

新しい要素を挿入したり、既存の要素を更新したりするためのコードは、updateValue(_:forKey:) inにあります。これはもう少し複雑です：

public mutating func updateValue(_ value: Value, forKey key: Key) -> Value? { let index = self.index(forKey: key) // Do we already have this key in the bucket? for (i, element) in buckets[index].enumerated() { if element.key == key { let oldValue = element.value buckets[index][i].value = value return oldValue } } // This key isn't in the bucket yet add it to the chain. buckets[index].append((key: key, value: value)) count += 1 return nil } Copy code

繰り返しますが、最初のステップは、キーを配列インデックスに変換してバケットを見つけることです。次に、バケットのチェーンをループします。チェーン内でキーが見つかった場合は、新しい値で更新します。キーがチェーンにない場合は、チェーンの最後に新しいキーと値のペアを挿入します。

ご覧のとおり、チェーンを短くする（ハッシュテーブルを十分に大きくする）ことが非常に重要です。そうでなければ、あなたはこれらにいますfor ... inループに費やされた時間が長すぎるため、ハッシュテーブルのパフォーマンスは低下します または（1） そしてもっと好き オン） 。

削除も同様で、チェーンを再度トラバースします。

public mutating func removeValue(forKey key: Key) -> Value? { let index = self.index(forKey: key) // Find the element in the bucket's chain and remove it. for (i, element) in buckets[index].enumerated() { if element.key == key { buckets[index].remove(at: i) count -= 1 return element.value } } return nil // key not in hash table } Copy code

これらはハッシュテーブルの基本的な機能です。それらはすべて同じように機能します：ハッシュ値を使用してキーを配列インデックスに変換し、バケットを見つけてから、チェーンのチェーンを反復処理して必要な操作を実行します。

遊び場でこれらのことを試してみてください。標準のSwiftのようになりますDictionary同じように動作します。

ハッシュテーブルのサイズを調整します

このバージョンのHashTableは常に固定サイズまたは容量の配列を使用します。ハッシュテーブルに多くのアイテムを格納する場合は、容量として、アイテムの最大数よりも大きい素数を選択します。

ハッシュ表 負荷率 現在使用中の容量のパーセンテージです。 5つのバケットを持つハッシュテーブルに3つのアイテムがある場合、負荷係数は3/5 = 60％です。

ハッシュテーブルが小さく、チェーンが長い場合、負荷係数が1より大きくなる可能性がありますが、これはお勧めできません。

負荷率が75％を超えて大きくなった場合は、ハッシュテーブルのサイズを調整できます。この条件を追加するコードは、練習するために読者に任されています。バケット配列を大きくすると、キーがマップされる配列インデックスが変更されることに注意してください。これには、配列のサイズを変更した後、すべての要素を再度挿入する必要があります。

それならどこへ行くの？ （ここからどこへ行くの？）

HashTable非常に基本的です。 Swift標準ライブラリとしての効率的な統合SequenceType。

著者：Matthijs Hollemans
翻訳： アンディロン
校正： アンディロン