Как реализовать Hashable протокол в Swift для массива Int (пользовательская строковая структура)

Question

Как реализовать Hashable протокол в Swift для массива Int (пользовательская строковая структура)

Я делаю структуру, которая действует как Stringза исключением того, что он работает только со скалярными значениями Unicode UTF-32. Таким образом, это массив UInt32, (Смотрите этот вопрос для получения дополнительной информации.)

Что я хочу сделать

Я хочу иметь возможность использовать мой обычай ScalarString структура как ключ в словаре. Например:

var suffixDictionary = [ScalarString: ScalarString]() // Unicode key, rendered glyph value

// populate dictionary
suffixDictionary[keyScalarString] = valueScalarString
// ...

// check if dictionary contains Unicode scalar string key
if let renderedSuffix = suffixDictionary[unicodeScalarString] {
    // do something with value
}

проблема

Чтобы сделать это, ScalarString необходимо реализовать Hashable протокол. Я думал, что смогу сделать что-то вроде этого:

struct ScalarString: Hashable {

    private var scalarArray: [UInt32] = []

    var hashValue : Int {
        get {
            return self.scalarArray.hashValue // error
        }
    }
}

func ==(left: ScalarString, right: ScalarString) -> Bool {
    return left.hashValue == right.hashValue
}

но потом я обнаружил, что массивы Swift не имеют hashValue,

Что я читаю

В статье " Стратегии реализации протокола Hashable в Swift" было много отличных идей, но я не видел ни одной, которая, казалось бы, сработала бы хорошо в этом случае. В частности,

Свойство объекта (массив не имеет hashValue)
Свойство ID (не уверен, как это может быть реализовано хорошо)
Формула (кажется, что любая формула для строки из 32-битных целых чисел была бы загружена процессором и имела бы много целочисленных переполнений)
ObjectIdentifier (я использую структуру, а не класс)
Наследование от NSObject (я использую структуру, а не класс)

Вот еще несколько вещей, которые я прочитал:

Вопрос

Swift Strings имеют hashValueсобственности, поэтому я знаю, что это можно сделать.

Как бы я создалhashValueдля моей пользовательской структуры?

Обновления

Обновление 1: я хотел бы сделать что-то, что не связано с преобразованием вStringа затем с помощьюString "s hashValue, Весь мой смысл в создании собственной структуры заключался в том, чтобы я мог избежать Stringпреобразования. Stringполучает это hashValue откуда-то Кажется, что я мог бы получить это, используя тот же метод.

Обновление 2: я изучал реализацию алгоритмов строковых хеш-кодов из других контекстов. У меня небольшие затруднения, зная, что лучше, и выражая их на языке Swift.

ДжаваhashCode алгоритм
C алгоритмы
хеш-функция для строки (ТАК вопрос и ответы в C)
Учебное пособие по хешированию (Исследовательская группа по визуализации технических алгоритмов штата Вирджиния)
Алгоритмы хэш-функции общего назначения

Обновление 3

Я бы предпочел не импортировать какие-либо внешние фреймворки, если это не рекомендовано для этих целей.

Я представил возможное решение с использованием хэш-функции DJB.

46

ios arrays swift string hashtable

Источник

user3681880 15 июл '15 в 18:24

4 ответа

Решение

Изменить (31 мая '17): Пожалуйста, обратитесь к принятому ответу. Этот ответ в значительной степени просто демонстрация того, как использовать CommonCrypto Фреймворк

Хорошо, я опередил и расширил все массивы с Hashable протокол с использованием алгоритма хеширования SHA-256 из среды CommonCrypto. Вы должны положить

#import <CommonCrypto/CommonDigest.h>

в заголовок моста для этого, чтобы работать. Жаль, что указатели должны быть использованы, хотя:

extension Array : Hashable, Equatable {
    public var hashValue : Int {
        var hash = [Int](count: Int(CC_SHA256_DIGEST_LENGTH) / sizeof(Int), repeatedValue: 0)
        withUnsafeBufferPointer { ptr in
            hash.withUnsafeMutableBufferPointer { (inout hPtr: UnsafeMutableBufferPointer<Int>) -> Void in
                CC_SHA256(UnsafePointer<Void>(ptr.baseAddress), CC_LONG(count * sizeof(Element)), UnsafeMutablePointer<UInt8>(hPtr.baseAddress))
            }
        }

        return hash[0]
    }
}

Редактировать (31 мая '17): Не делайте этого, даже если SHA256 практически не имеет хеш-коллизий, неправильно определять равенство по хеш-равенству

public func ==<T>(lhs: [T], rhs: [T]) -> Bool {
    return lhs.hashValue == rhs.hashValue
}

Это так хорошо, как это происходит с CommonCrypto, Это некрасиво, но быстро и ~~не так много,~~ конечно, никаких коллизий

Редактировать (15 июля '15): Я только что сделал несколько тестов скорости:

Случайно заполненный Int массивы размером n заняли в среднем более 1000 прогонов

n      -> time
1000   -> 0.000037 s
10000  -> 0.000379 s
100000 -> 0.003402 s

Принимая во внимание, что с методом хеширования строки:

n      -> time
1000   -> 0.001359 s
10000  -> 0.011036 s
100000 -> 0.122177 s

Таким образом, путь SHA-256 примерно в 33 раза быстрее, чем строковый. Я не говорю, что использование строки - это очень хорошее решение, но это единственное, с чем мы можем сравнить это прямо сейчас.

5

Источник

user3443689 15 июл '15 в 20:12

Это не очень элегантное решение, но оно прекрасно работает:

"\(scalarArray)".hashValue

или же

scalarArray.description.hashValue

Который просто использует текстовое представление в качестве источника хеша

4

Источник

user3443689 15 июл '15 в 18:57

Одно предложение - так как вы моделируете StringБудет ли это работать, чтобы преобразовать ваши [UInt32] массив к String и использовать String"s hashValue? Как это:

var hashValue : Int {
    get {
        return String(self.scalarArray.map { UnicodeScalar($0) }).hashValue
    }
}

Это может позволить вам сравнить ваши обычаи struct против StringНо и то, что это хорошая идея, зависит от того, что вы пытаетесь сделать...

Отметим также, что, используя этот подход, случаи ScalarString будет иметь то же самое hashValue если их String представления были канонически эквивалентны, что может или не может быть то, что вы хотите.

Итак, я полагаю, что если вы хотите hashValue представлять уникальный StringМой подход был бы хорош. Если вы хотите hashValue представлять уникальную последовательность UInt32 значения, ответ @Kametrixom является путь...

3

Источник

user4051126 15 июл '15 в 18:57

Другие вопросы по тегам ios arrays swift string hashtable

user3681880 16 июл '15 в 02:47 2015-07-16 02:47 · Accepted Answer · 2015-07-16 02:47

Обновить

Мартин Р пишет:

Начиная с Swift 4.1, компилятор может синтезировать Equatable а также Hashable для соответствия типов автоматически, если все элементы соответствуют Equatable/Hashable (SE0185). Начиная с Swift 4.2, в стандартную библиотеку Swift встроен высококачественный хеш-объединитель (SE-0206).
Поэтому больше не нужно определять собственную хеш-функцию, достаточно объявить соответствие:
struct ScalarString: Hashable, ... {

    private var scalarArray: [UInt32] = []

    // ... }

Таким образом, ответ ниже необходимо переписать (еще раз). Пока это не произойдет, обратитесь к ответу Мартина Р. по ссылке выше.

Старый ответ:

Этот ответ был полностью переписан после отправки моего исходного ответа на проверку кода.

Как реализовать протокол Hashable

Протокол Hashable позволяет использовать ваш пользовательский класс или структуру в качестве ключа словаря. Для реализации этого протокола вам необходимо

Реализация протокола Equatable (Hashable наследует от Equatable)
Вернуть вычисленное hashValue

Эти пункты следуют из аксиомы, приведенной в документации:

x == y подразумевает x.hashValue == y.hashValue

где x а также y значения некоторого типа.

Реализуйте Equatable протокол

Для реализации протокола Equatable вы определяете, как ваш тип использует == оператор (эквивалентности). В вашем примере эквивалентность может быть определена так:

func ==(left: ScalarString, right: ScalarString) -> Bool {
    return left.scalarArray == right.scalarArray
}

== Функция является глобальной, поэтому она выходит за пределы вашего класса или структуры.

Вернуть вычисленное `hashValue`

Ваш пользовательский класс или структура также должны иметь вычисляемый hashValue переменная. Хороший алгоритм хеширования обеспечит широкий диапазон хеш-значений. Однако следует отметить, что вам не нужно гарантировать, что все значения хеш-функции являются уникальными. Когда два разных значения имеют одинаковые значения хеш-функции, это называется коллизией хеш-функции. Это требует дополнительной работы при столкновении (поэтому желательно хорошее распределение), но следует ожидать некоторых столкновений. Насколько я понимаю, == Функция делает эту дополнительную работу. (Обновление: похоже == может сделать всю работу.)

Есть несколько способов вычислить значение хеша. Например, вы можете сделать что-то простое, например, вернуть количество элементов в массиве.

var hashValue: Int {
    return self.scalarArray.count
}

Это давало бы коллизию хешей каждый раз, когда два массива имели одинаковое количество элементов, но разные значения. NSArray по-видимому, использует этот подход.

Хэш-функция DJB

Обычной хеш-функцией, которая работает со строками, является хеш-функция DJB. Это тот, который я буду использовать, но посмотрите некоторые другие здесь.

Реализация Swift, предоставляемая @MartinR, выглядит следующим образом:

var hashValue: Int {
    return self.scalarArray.reduce(5381) {
        ($0 << 5) &+ $0 &+ Int($1)
    }
}

Это улучшенная версия моей первоначальной реализации, но позвольте мне также включить более старую расширенную форму, которая может быть более читабельной для людей, не знакомых с reduce, Это эквивалентно, я считаю:

var hashValue: Int {

    // DJB Hash Function
    var hash = 5381

    for(var i = 0; i < self.scalarArray.count; i++)
    {
        hash = ((hash << 5) &+ hash) &+ Int(self.scalarArray[i])
    }

    return hash
}

&+ оператор позволяет Int переполнить и начать заново для длинных строк.

Большая фотография

Мы рассмотрели фрагменты, но позвольте мне теперь показать весь пример кода в части, касающейся протокола Hashable. ScalarString это пользовательский тип из вопроса. Конечно, это будет отличаться для разных людей.

// Include the Hashable keyword after the class/struct name
struct ScalarString: Hashable {

    private var scalarArray: [UInt32] = []

    // required var for the Hashable protocol
    var hashValue: Int {
        // DJB hash function
        return self.scalarArray.reduce(5381) {
            ($0 << 5) &+ $0 &+ Int($1)
        }
    }
}

// required function for the Equatable protocol, which Hashable inheirits from
func ==(left: ScalarString, right: ScalarString) -> Bool {
    return left.scalarArray == right.scalarArray
}

Другое полезное чтение

кредиты

Большое спасибо Мартину Р. в Code Review. Мое переписывание во многом основано на его ответе. Если вы нашли это полезным, пожалуйста, дайте ему голос.

Обновить

Swift является открытым исходным кодом, так что можно увидеть, как hashValue реализован для String из исходного кода. Он кажется более сложным, чем ответ, который я дал здесь, и я не потратил время на его полный анализ. Не стесняйтесь делать это самостоятельно.

Как реализовать Hashable протокол в Swift для массива Int (пользовательская строковая структура)

Что я хочу сделать

проблема

Что я читаю

Вопрос

Обновления

4 ответа

Обновить

Старый ответ:

Как реализовать протокол Hashable

Реализуйте Equatable протокол

Вернуть вычисленное hashValue

Большая фотография

Другое полезное чтение

кредиты

Обновить

Вернуть вычисленное `hashValue`