Помогая разработчикам 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 keysfor
s in list.keys {for
v in list.values {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") {
Если у вас была возможность программировать на других языках (например, Java), вы должны быть знакомы с типами HashTable или HashMap. В разработке для iOS нет официального соответствующего типа HashTable. Однако на его место у нас есть популярный протокол Hashable. Идея состоит в том, что любой тип можно расширить для поддержки функций , подобных хеш-таблице. Рассмотрим следующий компонент, используемый для создания алгоритма блокчейна:
//custom type (used with graph programming) public classVertex
{ var key:String
? var neighbors:Array
<Edge> var visited:Bool
= false init() { self.neighbors =Array
<Edge>() } } ... //type conformance for Hashableextension
Vertex:Hashable
{ publicvar
hashValue:Int
{ var remainder:Int
= 0 var divisor:Int
= 0 //test early exitguard
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 staticfunc
== (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 itemif let
itemvalue = items.first?.hashValue {
Поскольку собственный тип Swift String уже соответствует Hashable, он поддерживает встроенное соответствие для вычисляемого свойства hashValue. Наконец, разработчики iOS, которым нужна большая гибкость, могут полностью отказаться от модели Hashable, чтобы создать уникальную реализацию. Умение написать простой алгоритм хеширования становится особенно полезным на техническом собеседовании. Рассмотрим следующий дизайн, также взятый из книги. В этом подходе применяется методика, ориентированная на протокол, за счет использования расширения протокола:
protocolKeyable
{var
keystring:String
{get} //note: in this case hashValue operates as a function func hashValue(for key:String
!, using buckets:Array
<T>) ->Int
} extensionKeyable
{ //compute item hashfunc
hashValue<T>(for key:String
!, using buckets:Array
<T>) ->Int
{ var remainder:Int
= 0 var divisor:Int
= 0 //trivial caseguard
key != nilelse
{ return -1 }for
item in key.unicodeScalars
{ divisor +=Int
(item.value) } remainder = divisor % buckets.count
return
remainder } }
Понравилось это эссе? Прочтите и откройте для себя мою книгу по Swift Algorithms в разделе Средний.