Accessing Swift Set Elements by Their Hash Value

Accessing Swift set elements by their hash value

Preamble:

1. Since there are 64 squares an array of optional pieces is probably best
2. In general you use a dictionary with an Int key as a sparse array (see example below)
3. You should not use hashValue for location alone since it should take into account all properties (I changed to location in example below) - though I get that in this case except transiently no 2 pieces can have the same location and therefore it is probably OK

How I might code it:

struct Piece {
    var row: Int
    var column: Int
    let player: Player
    let type: PieceType

    var location: Int {
        return 8 * row + column
    }
}

struct Board {
    var pieces = [Int : Piece]()

    init(pieces: Piece...) {
        pieces.forEach {
            self.pieces[$0.location] = $0
        }
    }
}

let whiteKing = Piece(row: 0, column: 4, player: .White, type: .King)
let blackKing = Piece(row: 7, column: 3, player: .Black, type: .King)

let board = Board(pieces: whiteKing, blackKing)

board.pieces // [4: {row 0, column 4, White, King}, 59: {row 7, column 3, Black, King}]

Get position as int from Set.index in Swift

Set is unordered, try using an Array for example

How to write to an Element in a Set?

You are getting the error because columns might be a set of struct. So columns.first will give you an immutable value. If you were to use a class, you will get a mutable result from columns.first and your code will work as expected.
Otherwise, you will have to do as explained by @Sweeper in his answer.

Getting hash values from object in swift

NSLog is probably showing you the GCController's debugDescription property whereas print and the likes will show you the description property.

Set's contains method returns different value at different time

The synthesized implementation of the Hashable requirement uses all stored
properties of a struct, in your case string and number. Your implementation
of == is only based on the string:

let first = SimpleStruct(string: "a", number: 2)
let second = SimpleStruct(string: "a", number: 3)

print(first == second) // true
print(first.hashValue == second.hashValue) // false

This is a violation of a requirement of the Hashable protocol:

Two instances that are equal must feed the same values to Hasher in hash(into:), in the same order.

and causes the undefined behavior. (And since hash values are randomized
since Swift 4.2, the behavior can be different in each program run.)

What probably happens in your test is that the hash value of second is used to determine the “bucket” of the set in which the value
would be stored. That may or may not be the same bucket in which first is stored. – But that is an implementation detail: Undefined behavior is undefined behavior, it can cause unexpected results or even
runtime errors.

Implementing

var hashValue: Int {
    return string.hashValue
}

or alternatively (starting with Swift 4.2)

func hash(into hasher: inout Hasher) {
    hasher.combine(string)
}

fixes the rule violation, and therefore makes your code behave as expected.

How does Set ensure equatability in Swift?

An object that conforms to Hashable must also be Equatable. Set uses == to test for equality, it doesn't depend only on the hashValue.

From Apple's documentation on Hashable:

Conforming to the Hashable Protocol
To use your own custom type in a
set or as the key type of a dictionary, add Hashable conformance to
your type by providing a hashValue property. The Hashable protocol
inherits from the Equatable protocol, so you must also add an equal-to
operator (==) function for your custom type.

The documentation goes on to say:

Set and dictionary performance depends on hash values that minimize
collisions for their associated element and key types, respectively.

So, the hashValue is just used a first test for uniqueness; if the hashValues match then Set will use the more computationally expensive == to test for uniqueness.

Swift: Using ObjectID of class for hashable protocol results in random behaviour in set.contains method. What is wrong with the code?

Simply put, Set relies on func hash(into hasher: inout Hasher) and ==. It is invalid to have an unmatched pair of these. In your case, your equality is value-based (dependant upon self.number), whereas your hash is identity based. This isn't legal.

Your mySet.contains(secondNumber1) line is failing because secondNumber2 might have a hash collision with number1. Whether a collision occurs or not is undefined, because Swift uses a random seed to defend against hash-flood DDoS attacks. If a hash collision does occur, then your equality operator (==) falsely identifies as number1 as a match for secondNumber1

Instead, what you could do is implement a wrapper struct that implements equality and hashing based on an object's identity. The object itself could have its own value-based equality and hash, for other purposes.

struct IdentityWrapper<T: AnyObject> {
    let object: T

    init(_ object: T) { self.object = object }
}

extension IdentityWrapper: Equatable {
    static func == (lhs: IdentityWrapper, rhs: IdentityWrapper) -> Bool {
        return lhs.object === rhs.object
    }
}

extension IdentityWrapper: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(ObjectIdentifier(self.object))
    }
}

Using the IdentityWrapper in a set requires you to manually wrap objects before interacting with the set. It's performant (since struct don't need any array allocation), and most likely the struct is entirely inlined anyway, but it can be a little annoying. Optionally, you could implement a struct IdentitySet<T> which just wraps a Set<IdentityWrapper<T>>, which tucks away the wrapping code.

class MyClass: Hashable {
    var number: Int

    init(_ number: Int) {
        self.number = number
    }

    // Value-based equality
    static func == (lhs: MyClass, rhs: MyClass) -> Bool {
        return lhs.number == rhs.number
    }

    // Value-based hashing
    func hash(into hasher: inout Hasher) {
        hasher.combine(self.number)
    }
}

var mySet: Set<IdentityWrapper<MyClass>> = []

let number1 = MyClass(1)
let secondNumber1 = MyClass(1)

number1 == secondNumber1        // true: integer values are equal, so are the wrapping classes
number1 === secondNumber1       // false: two different instances

mySet.insert(IdentityWrapper(number1))

print(mySet.contains(IdentityWrapper(number1))) // true
print(mySet.contains(IdentityWrapper(secondNumber1))) // false

Getting set of objects from NSSet using the HASH

if you want the object in an array just call -allObjects, if you want all hashes, then you will have to iterate through them, because they are longs and can't be stored in an NSArray directly.

I had the idea to make a mock object that overrides its own hash, then you could search through an array for the index of this object that is pretending to be your object.

@interface MockHasher : NSObject{
    NSUInteger mockHash;
}

@property(assign,nonatomic,getter = hash,setter = setHash:)NSUInteger mockHash;
@end

@implementation MockHasher

@synthesize mockHash;

-(BOOL)isEqual:(id)object{return YES;}
-(BOOL)isEqualTo:(id)object{return YES;}

@end

example:

NSSet * myset = [NSSet setWithObject:@(1)];
MockHasher * mockObject = [[MockHasher new] autorelease];
mockObject.hash = @(1).hash;
NSArray * allObjects = [myset allObjects];
NSUInteger i = [allObjects indexOfObject:mockObject];
id result = [allObjects objectAtIndex:i];
NSLog(@"result = %@",result);

It is fragile, because it is depending on the array asking the object passed in for isEqual: rather than asking the iterated object... I don't know how reliable this is... but it worked in my test.

---

Related Topics