Помогая разработчикам iOS подготовиться к техническим собеседованиям, я часто обсуждаю хеш-таблицы. Из-за своей эффективности хеш-таблицы являются отличным инструментом, который кандидаты должны учитывать при решении проблем кодирования, а также в реальных приложениях. В этом эссе мы исследуем концепцию хеш-таблицы и сравним ее с другими типами коллекций, такими как словари и наборы.

Словарь

Чтобы понять, чем полезны хеш-таблицы, следует ознакомиться с их конструкцией. Когда их спрашивают, многие студенты предполагают, что «хеш-таблица - это словарь». Чтобы проверить эту идею, давайте рассмотрим стандартный тип словаря Swift:

var list = Dictionary<String, String>()
//add dictionary values - constant time O(1)
list["WB"] = "Wayne Bishop"
list["FB"] = "Frank Hobbs"
list["LP"] = "Larry Page"
list["AE"] = "Albert Einstein"
//retrieve keys
for s in list.keys {
    print(s)
}
//retrieve values
for v in list.values {
    print(v)
}
//retrieve value with key - constant time O(1)
let item = list["WB"] //retrieves "Wayne Bishop"

Словари - это полезные типы, которые обрабатывают множество сценариев. Поскольку и ключи, и значения предоставляются во время выполнения, можно написать процедуры для получения отдельных ключей, значений или их комбинации. Кроме того, поскольку каждое предоставленное значение связано с ключом, можно также выполнять вставку, поиск и извлечение необходимых данных в O (1) - постоянное время.

Хеш-таблица

Хеш-таблицы близки к словарям, но отличаются в двух областях. Хеш-таблицы также поддерживают пары ключ-значение, но их ключи генерируются программно с помощью дополнительной функции, называемой хеш-алгоритмом. Поскольку ключи хеш-таблицы создаются во время выполнения (и не подлежат изменению), они часто не сохраняются вместе со структурой данных. Эти функции позволяют выполнять хеш-таблицы за O (1) - постоянное время, занимая при этом минимальное пространство. Рассмотрим следующую индивидуальную реализацию, взятую из книги:

let list = HashTable<String>(capacity: 4)
//add hash table items - constant time O(1)
 = list.insert("Wayne Bishop")
 = list.insert("Frank Smith")
 = list.insert("Jennifer Hobbs")
 = list.insert("Tim Cook")
//evaluation test - constant time O(1)
if list.contains("Tim Cook") {
   print("user found!")
}

Если у вас была возможность программировать на других языках (например, Java), вы должны быть знакомы с типами HashTable или HashMap. В разработке для iOS нет официального соответствующего типа HashTable. Однако на его место у нас есть популярный протокол Hashable. Идея состоит в том, что любой тип можно расширить для поддержки функций , подобных хеш-таблице. Рассмотрим следующий компонент, используемый для создания алгоритма блокчейна:

//custom type (used with graph programming)
public class Vertex {
    
    var key: String?
    var neighbors: Array<Edge>
    var visited: Bool = false
    
    init() {
     self.neighbors = Array<Edge>()
    }
}

...

//type conformance for Hashable
extension Vertex: Hashable {
    
    public var hashValue: Int {
        
        var remainder: Int = 0
        var divisor: Int = 0
        
        //test early exit
        guard let scalars = self.key?.unicodeScalars else {
            return 0
        }
   
   for item in scalars {
            divisor += Int(item.value)
        }
        
        remainder = divisor % 10
                       
        return remainder        
    }
    
    //note: requirement for inherited Equatable protocol     
    public static func == (lhs: Vertex, rhs: Vertex) -> Bool {
       return lhs.key == rhs.key
    }    
    
}

В качестве протокола Hashable обеспечивает правильную индексацию всех соответствующих типов с помощью уникального числового значения. В рамках этой модели требуемое вычисляемое свойство hashValue действует как алгоритм хеширования. Мы также можем увидеть эту функциональность в действии при работе со стандартными типами коллекций Swift, такими как Наборы:

var items = Set<String>() //note: Swift Strings conform to Hashable

//add set items - constant time O(1)
items.insert("Wayne Bishop") 
items.insert("Frank Hobbs")
items.insert("Larry Page")
items.insert("Albert Einstien")

//obtain hash index for first set item
if let itemvalue = items.first?.hashValue {
   print(itemvalue)  //prints -312247953819291399
}

Поскольку собственный тип Swift String уже соответствует Hashable, он поддерживает встроенное соответствие для вычисляемого свойства hashValue. Наконец, разработчики iOS, которым нужна большая гибкость, могут полностью отказаться от модели Hashable, чтобы создать уникальную реализацию. Умение написать простой алгоритм хеширования становится особенно полезным на техническом собеседовании. Рассмотрим следующий дизайн, также взятый из книги. В этом подходе применяется методика, ориентированная на протокол, за счет использования расширения протокола:

protocol Keyable {       
       
       var keystring: String {get}
       
       //note: in this case hashValue operates as a function
       func hashValue(for key: String!, using buckets: Array<T>) -> Int 
 }
    
extension Keyable {
        
        //compute item hash
        func hashValue<T>(for key: String!, using buckets: Array<T>) -> Int {
                    
            var remainder: Int = 0
            var divisor: Int = 0
            
            //trivial case
            guard key != nil else {
                return -1
            }        
            
            for item in key.unicodeScalars {
            divisor += Int(item.value)
            }        
            
            remainder = divisor % buckets.count        
            return remainder
         }        
  }

Понравилось это эссе? Прочтите и откройте для себя мою книгу по Swift Algorithms в разделе Средний.