Do swift hashable protocol hash functions need to return unique values?
Collisions are not "generally OK". The underlying assumption is that the hash value of x
is the hash value of y
if and only if x == y
. If you consider column 2, row 1 the same as column 1, row 2, then fine. But I don't think you do! The application may appear to work, but presumably you have done nothing that requires hashability - yet.
What is the use of hashable protocol in swift4?
To make an object conform to Hashable we need to provide a hashValue property that will return a unique, consistent number for each instance.
The Hashable protocol inherits from Equatable, so you may also need to implement an == function.
Note: If two objects compare as equal using == they should also generate the same hash value, but the reverse isn’t true – hash collisions can happen.
Before Swift 4.1, conforming to Hashable was complex because you needed to calculate a hashValue property by hand.
In Swift 4.1 this improved so that hashValue could be synthesized on your behalf if all the properties conform to Hashable .
Swift 4.2 introduces a new Hasher struct that provides a randomly seeded, universal hash function to make all our lives easier. Refer for more
Make all elements of array that are Hashable unique with a UUID hashValue?
You probably want to do this a slightly different way. Could your array be of Identifiable
instead? Then your example could be:
struct Person: Identifiable, Hashable {
let id = UUID()
let name: String
}
And each instance of Person
will have a unique hashValue:
let people = [Person(name: "Joe"), Person(name: "Joe"), Person(name: "Joe")]
people.map(\.hashValue) // e.g. -> [7672515142881976808, -2470749298227582550, 3252810522385000211]
What is the use of Hashable and Equatable in Swift? When to use which?
When you conform to Hashable
, you provide a method that returns the hash value of self
.
When you conform to Equatable
, you provide a method that returns whether the given object and self
are equal.
They seem to serve two very different purposes, why does Hashable
inherit Equatable
? Because the hash values for two equal objects are equal!
What can and can't you do with Hashable
and Equatable
?
Equatable
has more limited uses than Hashable
. It can only compare the equality of two objects, and that's it.
For Hashable
, because you can get a number that represents the object, you can kind of treat the objects as numbers. You can compare the objects: whether it is less than, greater than, or equal to another object, just like you do with numbers:
if objA.hashValue > objB.hashValue
This also means you can sort objects with Hashable
.
Last but not least, you can use Hashable
objects as keys for maps! this is because maps' keys cannot duplicate, so how can the system check whether you put a duplicate item in it? It uses the hash values of the keys!
How to implement the Hashable Protocol in Swift for an Int array (a custom string struct)
Update
Martin R writes:
As of Swift 4.1, the compiler can synthesize
Equatable
andHashable
for types conformance automatically, if all members conform to
Equatable/Hashable (SE0185). And as of Swift 4.2, a high-quality hash
combiner is built-in into the Swift standard library (SE-0206).Therefore there is no need anymore to define your own hashing
function, it suffices to declare the conformance:struct ScalarString: Hashable, ... {
private var scalarArray: [UInt32] = []
// ... }
Thus, the answer below needs to be rewritten (yet again). Until that happens refer to Martin R's answer from the link above.
Old Answer:
This answer has been completely rewritten after submitting my original answer to code review.
How to implement to Hashable protocol
The Hashable protocol allows you to use your custom class or struct as a dictionary key. In order to implement this protocol you need to
- Implement the Equatable protocol (Hashable inherits from Equatable)
- Return a computed
hashValue
These points follow from the axiom given in the documentation:
x == y
impliesx.hashValue == y.hashValue
where x
and y
are values of some Type.
Implement the Equatable protocol
In order to implement the Equatable protocol, you define how your type uses the ==
(equivalence) operator. In your example, equivalence can be determined like this:
func ==(left: ScalarString, right: ScalarString) -> Bool {
return left.scalarArray == right.scalarArray
}
The ==
function is global so it goes outside of your class or struct.
Return a computed hashValue
Your custom class or struct must also have a computed hashValue
variable. A good hash algorithm will provide a wide range of hash values. However, it should be noted that you do not need to guarantee that the hash values are all unique. When two different values have identical hash values, this is called a hash collision. It requires some extra work when there is a collision (which is why a good distribution is desirable), but some collisions are to be expected. As I understand it, the ==
function does that extra work. (Update: It looks like ==
may do all the work.)
There are a number of ways to calculate the hash value. For example, you could do something as simple as returning the number of elements in the array.
var hashValue: Int {
return self.scalarArray.count
}
This would give a hash collision every time two arrays had the same number of elements but different values. NSArray
apparently uses this approach.
DJB Hash Function
A common hash function that works with strings is the DJB hash function. This is the one I will be using, but check out some others here.
A Swift implementation provided by @MartinR follows:
var hashValue: Int {
return self.scalarArray.reduce(5381) {
($0 << 5) &+ $0 &+ Int($1)
}
}
This is an improved version of my original implementation, but let me also include the older expanded form, which may be more readable for people not familiar with reduce
. This is equivalent, I believe:
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
}
The &+
operator allows Int
to overflow and start over again for long strings.
Big Picture
We have looked at the pieces, but let me now show the whole example code as it relates to the Hashable protocol. ScalarString
is the custom type from the question. This will be different for different people, of course.
// 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
}
Other helpful reading
- Which hashing algorithm is best for uniqueness and speed?
- Overflow Operators
- Why are 5381 and 33 so important in the djb2 algorithm?
- How are hash collisions handled?
Credits
A big thanks to Martin R over in Code Review. My rewrite is largely based on his answer. If you found this helpful, then please give him an upvote.
Update
Swift is open source now so it is possible to see how hashValue
is implemented for String
from the source code. It appears to be more complex than the answer I have given here, and I have not taken the time to analyze it fully. Feel free to do so yourself.
Swift, how to implement Hashable protocol based on object reference?
If you are working with classes and not structs, you can use the ObjectIdentifier
struct. Note that you also have to define ==
for your class in order to conform to Equatable
(Hashable
requires it). It would look something like this:
class MyClass: Hashable { }
func ==(lhs: MyClass, rhs: MyClass) -> Bool {
return ObjectIdentifier(lhs) == ObjectIdentifier(rhs)
}
class MyClass: Hashable {
var hashValue: Int {
return ObjectIdentifier(self).hashValue
}
}
Make struct Hashable?
Simply return dbName.hashValue
from your hashValue
function. FYI - the hash value does not need to be unique. The requirement is that two objects that equate equal must also have the same hash value.
struct PetInfo: Hashable {
var petName: String
var dbName: String
var hashValue: Int {
return dbName.hashValue
}
static func == (lhs: PetInfo, rhs: PetInfo) -> Bool {
return lhs.dbName == rhs.dbName && lhs.petName == rhs.petName
}
}
Conforming to Hashable protocol?
You're missing the declaration:
struct DateStruct: Hashable {
And your ==
function is wrong. You should compare the three properties.
static func == (lhs: DateStruct, rhs: DateStruct) -> Bool {
return lhs.year == rhs.year && lhs.month == rhs.month && lhs.day == rhs.day
}
It's possible for two different values to have the same hash value.
How to handle hash collisions for Dictionaries in Swift
func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.hashValue == rhs.hashValue
}
Note the global function to overload the equality operator (==) in order to conform to the Equatable Protocol, which is required by the Hashable Protocol.
Your problem is an incorrect equality implementation.
A hash table (such as a Swift Dictionary or Set) requires separate equality and hash implementations.
hash gets you close to the object you're looking for; equality gets you the exact object you're looking for.
Your code uses the same implementation for hash and equality, and this will guarantee a collision.
To fix the problem, implement equality to match exact object values (however your model defines equality). E.g.:
func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.id == rhs.id
}
Related Topics
Tvos Button Inside Navigationlink Is Not Working
Swift Getnameinfo Unreliable Results for Ipv6
What Is The Advantage of Closure Stored Property Initialisation
Create Custom Action in a Class for Use in Interface Builder
Load a Spritekit Scene from Another Bundle
How to Calculate The Camera Position from Vuforia Gl Matrix
Dynamic Links Firebase Function Not Being Called at All Xcode 12
Rlmexception', Reason: 'Attempting to Modify Object Outside of a Write Transaction
Parse Migration Error to Mlabs and Heroku
Swift Error "Static Member Cannot Be Used on Instance of Type"
Why Cannot Read The Receipt Data for On-Device Validation
How to Use Nscalendar Range Function Within Calendar
Uitextfield with a Placeholder Containing an Image and Text
How to Save Text Field Value in UIcollectionviewcell
User Specific Avatar in Jsqmessagesviewcontroller with Sdwebimage