ProbingDictionary.swift

import Foundation

struct ProbingDictionary<Key: Hashable, Value> {
    enum Item: CustomStringConvertible {
        case element(Key, Value)
        case empty
        case tombstone

        var isEmpty: Bool {
            if case .empty = self {
                return true
            }
            return false
        }

        var isEmptyOrTombstone: Bool {
            return !hasElement
        }

        var hasElement: Bool {
            if case .element = self {
                return true
            }
            return false
        }

        var value: Value? {
            if case let .element(_, value) = self {
                return value
            }
            return nil
        }

        var key: Key? {
            if case let .element(key, _) = self {
                return key
            }
            return nil
        }

        var description: String {
            switch self {
            case .tombstone:
                return "☠️"
            case .empty:
                return "_"
            case let .element(key, _):
                return "\"\(key)\""
            }
        }
    }

    private var storage: Array<Item>

    init() {
        storage = Array(repeating: .empty, count: 8)
    }

    subscript(key: Key) -> Value? {
        get {
            let index = abs(key.hashValue % storage.count)
            let rotated = storage[index...] + storage[..<index]
            return rotated
                .prefix(while: { !$0.isEmpty })
                .first(where: { $0.key == key })?
                .value
        }
        set {
            resizeIfNeeded()
            if let newValue = newValue {
                let index = abs(key.hashValue % storage.count)
                let rotated = storage[index...] + storage[..<index]
                let insertionIndex = rotated.firstIndex(where: { $0.isEmptyOrTombstone || $0.key == key })! % storage.count
                storage[insertionIndex] = .element(key, newValue)
            } else {
                let index = abs(key.hashValue % storage.count)
                let rotated = storage[index...] + storage[...index]
                if let deletionIndex = rotated.firstIndex(where: { $0.key == key }) {
                    storage[deletionIndex % storage.count] = .tombstone
                }
            }
        }
    }

    private mutating func resizeIfNeeded() {
        guard self.storage.filter({ $0.hasElement }).count > storage.count / 2 else { return }
        let originalStorage = self.storage
        self.storage = Array(repeating: .empty, count: originalStorage.count * 2)
        for case let .element(key, value) in originalStorage {
            self[key] = value
        }
    }
}

extension ProbingDictionary: Collection {
    var startIndex: Int {
        return storage.firstIndex(where: { $0.hasElement }) ?? storage.endIndex
    }

    var endIndex: Int {
        return storage.endIndex
    }

    func index(after i: Int) -> Int {
        return storage[i...].dropFirst().firstIndex(where: { $0.hasElement }) ?? endIndex
    }

    subscript(index: Int) -> (Key, Value) {
        return (storage[index].key!, storage[index].value!)
    }

    var keys: AnySequence<Key> {
        return AnySequence(storage.lazy.compactMap({ $0.key }))
    }

    var value: AnySequence<Value> {
        return AnySequence(storage.lazy.compactMap({ $0.value }))
    }
}

ProbingDictionaryTests.swift

import XCTest
@testable import ProbingDictionary

struct Hash: Hashable {

    let equalityValue: String

    let hashValue: Int

    init(value equalityValue: String, hashValue: Int) {
        self.equalityValue = equalityValue
        self.hashValue = hashValue
    }

    static func == (lhs: Hash, rhs: Hash) -> Bool {
        return lhs.equalityValue == rhs.equalityValue
    }
}

class ProbingDictionaryTests: XCTestCase {

    func testGettingFromAnEmptyDictionary() {
        var dictionary = ProbingDictionary<String, String>()
        XCTAssertEqual(dictionary["a"], nil)
        XCTAssertEqual(dictionary.count, 0)
    }

    func testSettingAndGettingAValue() {
        var dictionary = ProbingDictionary<String, String>()
        dictionary["a"] = "123"
        XCTAssertEqual(dictionary["a"], "123")
        XCTAssertEqual(dictionary.count, 1)
    }

    func testMultipleValues() {
        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 1)] = "123"
        dictionary[Hash(value: "b", hashValue: 5)] = "abc"
        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 1)], "123")
        XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 5)], "abc")
        XCTAssertEqual(dictionary.count, 2)
    }

    func testACollision() {
        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 1)] = "123"
        dictionary[Hash(value: "b", hashValue: 1)] = "abc"
        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 1)], "123")
        XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 1)], "abc")
        XCTAssertEqual(dictionary.count, 2)
   }

    func testARolloverCollision() {
        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 7)] = "123"
        dictionary[Hash(value: "b", hashValue: 7)] = "abc"
        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 7)], "123")
        XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 7)], "abc")
        XCTAssertEqual(dictionary.count, 2)
   }

    func testATripleCollision() {
        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 7)] = "123"
        dictionary[Hash(value: "b", hashValue: 7)] = "abc"
        dictionary[Hash(value: "c", hashValue: 7)] = "def"
        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 7)], "123")
        XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 7)], "abc")
        XCTAssertEqual(dictionary[Hash(value: "c", hashValue: 7)], "def")
        print(dictionary.indices)
        XCTAssertEqual(dictionary.count, 3)
   }

    func _testResizing() {
        let letters = "abcdefghijklmnopqrstuvwxyz"
        let values = (1...1000).map({ (String(letters.randomElement()!), $0) })
        var dictionary = ProbingDictionary<Hash, String>()
        for (key, hash) in values {
            dictionary[Hash(value: key, hashValue: hash)] = key
        }

        for (key, hash) in values {
            XCTAssertEqual(dictionary[Hash(value: key, hashValue: hash)], key)
        }

        XCTAssertEqual(dictionary.count, 1000)
    }

    func testDeletion() {
        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 7)] = "123"
        dictionary[Hash(value: "b", hashValue: 4)] = "abc"
        dictionary[Hash(value: "a", hashValue: 7)] = nil

        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 7)], nil)
        XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 4)], "abc")
        XCTAssertEqual(dictionary.count, 1)

    }

    func testDeletionWorksWithNeighboringElements() {

        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 6)] = "123"
        dictionary[Hash(value: "b", hashValue: 7)] = "abc"
        dictionary[Hash(value: "a", hashValue: 6)] = nil

        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 6)], nil)
        XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 7)], "abc")

        XCTAssertEqual(dictionary.count, 1)
    }

    func testDeletionWorksWithCollidingElements() {

        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 6)] = "123"
        dictionary[Hash(value: "b", hashValue: 6)] = "abc"
        dictionary[Hash(value: "c", hashValue: 6)] = "def"
        dictionary[Hash(value: "a", hashValue: 6)] = nil

        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 6)], nil)
        XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 6)], "abc")
        XCTAssertEqual(dictionary[Hash(value: "c", hashValue: 6)], "def")
        print(Array(dictionary.indices))

        XCTAssertEqual(dictionary.count, 2)

    }

    func testDeletionWorksWithCollidingAndNonCollidingElements() {

        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 6)] = "123"
        dictionary[Hash(value: "b", hashValue: 6)] = "abc"
        dictionary[Hash(value: "c", hashValue: 7)] = "def"
        dictionary[Hash(value: "a", hashValue: 6)] = nil

        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 6)], nil)
        XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 6)], "abc")
        XCTAssertEqual(dictionary[Hash(value: "c", hashValue: 7)], "def")
        XCTAssertEqual(dictionary.count, 2)

    }

    func testDeletionWorksAgainWithCollidingAndNonCollidingElements() {

        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 6)] = "123"
        dictionary[Hash(value: "b", hashValue: 6)] = "abc"
        dictionary[Hash(value: "c", hashValue: 0)] = "def"
        dictionary[Hash(value: "a", hashValue: 6)] = nil

        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 6)], nil)
        XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 6)], "abc")
        XCTAssertEqual(dictionary[Hash(value: "c", hashValue: 7)], "def")
        XCTAssertEqual(dictionary.count, 2)

    }

    func testDeletingAndReadding() {

        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 6)] = "123"
        dictionary[Hash(value: "a", hashValue: 6)] = nil
        dictionary[Hash(value: "a", hashValue: 6)] = "def"

        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 6)], "def")
        XCTAssertEqual(dictionary.count, 1)

    }

    func testTombstones() {

        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 6)] = "123"
        dictionary[Hash(value: "b", hashValue: 6)] = "abc"
        dictionary[Hash(value: "c", hashValue: 6)] = "def"

        dictionary[Hash(value: "b", hashValue: 6)] = nil

        XCTAssertEqual(dictionary[Hash(value: "c", hashValue: 6)], "def")
        XCTAssertEqual(dictionary.count, 2)
    }

    func testDeletingAnElementThatDoesntExist() {

        var dictionary = ProbingDictionary<Hash, String>()
        dictionary[Hash(value: "a", hashValue: 6)] = "123"
        dictionary[Hash(value: "b", hashValue: 6)] = nil

        XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 6)], "123")
        XCTAssertEqual(dictionary.count, 1)

    }



}