Swift: my hash table works with a magic number, but not with a dynamic number

Question

i am learning about creating my own hash table for my own knowledge (and interview prep, let's face it).

i am working in swift, and i am running into a hangup that i can't seem to solve particularly well.

the goal is to create a simple but effective hash that upon resizing still returns the appropriate value when typing in a key as a subscript. it works if i use the same value across the hash table regardless of its size.

for example, if i set a % (modulo) divisor as 3, then everything is great. the hash table works as expected.

but...

if i set a % (modulo) divisor as a 'buckets'.count Int value, upon resizing, my keys no longer map to anything relevant and my return value is 'nil' which is correct because the key is mapping to the original hash value which does not exist in the newly resized 'buckets'.

(i think i am correctly saying that. forgive me if it's backwards.)

---

here is my attempts at the hash function:

// function to find a safe prime number -> a nice implementation i found here on stack overflow
func isPrime(_ n: Int) -> Bool {
    guard n >= 2     else { return false }
    guard n != 2     else { return true  }
    guard n % 2 != 0 else { return false }
    return !stride(from: 3, through: Int(sqrt(Double(n))), by: 2).contains { n % $0 == 0 }
}

private func index(forKey key: Key) -> Int {

    // set primeNumber to a value that is the largest Int value in range of buckets.count...0

    var primeNumber: Int = 3

    for n in 0...buckets.count {

        let validPrime = isPrime(n)

        if validPrime {

            primeNumber = n
        }
    }

    return abs(key.hashValue % primeNumber)
}  

and here is my attempt at the resize function:

mutating func resize(newCapacity: Int) -> [Bucket] {

    var temporaryBuckets: [Bucket] = []

    for bucket in buckets {

        temporaryBuckets.append(bucket)
    }

    self.capacity = newCapacity

    assert(capacity > 0)

    // need to find another way to re-insert the elements

    buckets = Array<Bucket>(repeatElement([], count: capacity))

    var index = 0
    for bucket in temporaryBuckets {

        buckets[index] = bucket

        index += 1
    }

    return buckets
}

any help is greatly appreciated. if there is a more efficient way without getting too crazy, then i am all ears!

if curious, i am trying to finish up the hash table tutorial from Ray Wenderlich's Swift Algorithm Club entry:

Swift Algorithm Club: Hash Tables by Kelvin Lau. https://www.raywenderlich.com/206-swift-algorithm-club-hash-tables

thanks in advance!

Answer 1

You need to compute the index again for the new hash table. Right now you're assigning the buckets to index 0, 1, 2, and so on. Instead, you should call index(forKey:) again for every element and insert it at the new index. Note that you cannot use the same Bucket objects now. Can you think of the reason why that is?