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

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

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

1. Внедрить Equatable protocol (Hashable наследует от Equatable)
2. Возвратить вычисленный hashValue

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

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

, где x и y являются значениями некоторого типа.

Реализация Equatable protocol

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

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
}

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

• Какой алгоритм хеширования лучше всего подходит для уникальности и скорости?
• Операторы переполнения
• Почему 5381 и 33 настолько важны в алгоритме djb2?
• Как обрабатываются хэш-столкновения?

Кредиты

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

Обновить

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