ハッシュ表

ハッシュテーブル-Swiftの実装



Hash Table Swift Implementation



定義

  • ハッシュテーブルは、キーワードキーを使用して検索および保存するための構造です。ハッシュ方式を使用して、格納された値の場所とキーの間に特定の対応する関係を確立し、各キーが格納場所に対応するようにします。
  • ハッシュ方式は、ハッシュ関数またはハッシュ関数とも呼ばれます。
  • ほとんどの言語の辞書はハッシュテーブルを介して実装されており、Swiftには含まれていません。 Swiftの辞書のキーは、Hashableプロトコルに準拠するために必要です。

機能の説明

  • 実際、ハッシュテーブルは配列ですが、値が格納される場所は、キーを特定の「アルゴリズム」に入れることによって計算されます。
  • 上記には、直接アドレス指定、2乗減算、剰余、乱数など、多くの特定のアルゴリズムがあります。しかし、すべての方法は避けられず、key1とkey2の2つの異なる値がありますが、アルゴリズムが計算した後、配列内の同じ保存場所が取得され、この時点で競合が発生します。
  • 競合や、再ハッシュ、チェーンアドレスメソッドなどのアルゴリズムを回避します。以下で受け入れられる実装は、チェーンアドレスメソッドによって実装されます。
  • 要するに、ハッシュテーブルを実装する目的は、計算（つまり、アルゴリズム）が比較的単純であり、配列内の位置分布が比較的均一であることです。できるだけ魚とクマの足を作るようにしてください。

成し遂げる

辞書では、キーに従って値を読み取り、更新、保存し、これらの特性に従って実装できます。

//0 struct HashTable { //1 private typealias Element = (key: Key, value: Value) private typealias Bukets = [Element] //2 private var buckets: [Bukets] private(set) var count = 0 var isEmpty: Bool { return count == 0 } //3 init(_ capacity: Int) { Assert(capacity > 0, 'cannot be negative') buckets = Array.init(repeating: [], count: capacity) } //4 private func index(forKey key: Key) -> Int { return abs(key.hashValue) % buckets.count } }

0.KeyがHashTableを継承する2つの汎用KeyおよびValueシートキー値タイプを定義します



1. 2つのタイプ、タプル、祖先を含む配列タイプを定義します

2.ハッシュテーブルメモリストレージデータの配列を定義します。このバケットのタイプは[Bukets]で、内部要素は配列であり、配列内の要素はタプルです。
[[（key：Key、value：Value）、（key：Key、value：Value）、（key：Key、value：Value）]、[（key：Key、value：Value）、（key：Key、value ：値）]、[（キー：キー、値：値）]]



3.初期化方法で内部容量を設定します

  1. インデックス方式は、値に対応するキーの添え字値を計算するために使用されます。ここで使用する方法は、残りの方法を削除することです。

前の操作を達成するための添え字を通して、削除、チェック

private 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 } private mutating func upDateValue(value: Value, forKey key: Key) { let index = self.index(forKey: key) for (i, element) in buckets[index].enumerated() { if element.key == key { let bucketElement = buckets[index] var keyValue = bucketElement[i] keyValue.value = value return } } //If the key does not exist, insert a new one buckets[index].append((key, value)) count += 1 } private mutating func removeValue(forKey key: Key) -> Value? { let index = self.index(forKey: key) for (i, element) in buckets[index].enumerated() { if element.key == key { buckets[index].remove(at: i) count -= 1 return element.value } } return nil } ///Addition and deletion of operations by subscript subscript(key: Key) -> Value? { get { return value(forKey: key) } set { if let value = newValue { upDateValue(value: value, forKey: key) } else { let _ = removeValue(forKey: key) } } }

上記はハッシュテーブルの簡単な実装であり、徐々に改善されます。