Gfrktyl

I've stumbled upon this pretty old article about a hashing interview question, and here it is converted to Swift in a more generic way:

struct CustomHasher {



    /// An enum of the errors that may be thrown

    enum HashingError: Error {



        /// Thrown by the initializer

        /// when the alphabet contains repeating letters

        case invalidAlphabet



        /// Thrown by the initializer

        /// when the base is negative

        case invalidBase



        /// Thrown by the initializer

        /// when the offset is negative

        case invalidOffset



        /// Thrown by the hash(_:) function

        /// when the string provided uses illegal letters

        case outOfAlphabet(String)



        /// Thrown by the hash(_:) function

        /// when the string provided uses illegal letters

        case exceedsInt64



        /// Thrown by the reverseHash(_:) function

        /// when the string provided uses illegal letters

        case invalidHash

    }



    //Parameters

    private let base: Int64

    private let offset: Int64

    private let alphabet: String



    // An array that eases the access to the elements of the alphabet

    private let alphabetArray: [Character]



    private let stringLengthLimit: Int



    /// Convinience inializer

    /// - Parameters:

    ///     - alphabet: Must be a string of unique characters

    ///     - offset: A strictly positive Int64

    ///     - base: A strictly positive Int64

    /// - Throws:

    ///     - HashingError.outOfAlphabet(String)

    ///     - HashingError.invalidOffset

    init(alphabet: String, offset: Int64, base: Int64) throws {

        self.alphabet = alphabet

        self.alphabetArray = Array(alphabet)

        guard alphabetArray.count == Set(alphabet).count else {

            throw HashingError.invalidAlphabet

        }



        guard offset > 0 else {

            throw HashingError.invalidOffset

        }

        self.offset = offset



        guard base > 1 else {

            throw HashingError.invalidBase

        }

        self.base = base



        let b = Double(base)

        let c = Double(alphabetArray.count)

        let dOffset = Double(offset)

        let int64limit = Double(Int64.max)



        self.stringLengthLimit = ((0...).first {

            let power = pow(b, Double($0))

            let tail = $0 == 1 ? c * power : c * (power - 1) / (b - 1)

            let head = dOffset * power

            return head + tail > int64limit

            } ?? 0) - 1

    }



    /// Takes a string and converts it to a corresponding Int64

    /// - Parameters:

    ///     - str: The string to be hashed

    /// - Throws:

    ///     - HashingError.outOfAlphabet(String)

    ///     - HashingError.exceedsInt64

    func hash(_ str: String) throws -> Int64 {



        guard Array(str).count <= stringLengthLimit else {

            throw HashingError.exceedsInt64

        }

        var h: Int64  = offset

        for char in str {

            if let index: Int = alphabetArray.firstIndex(of: char) {

                h = h * base + Int64(index)

            } else {

                throw HashingError.outOfAlphabet(alphabet)

            }

        }

        return h

    }



    /// Reverses the hashing process

    /// - Parameters:

    ///     - str: The string to be hashed

    /// - Throws:

    ///     - HashingError.invalidHash

    func reverseHash(_ hash: Int64) throws -> String {



        guard hash >= offset else {

            throw HashingError.invalidHash

        }



        //Reached the end

        if hash == offset {

            return ""

        }



        let remainder: Int64 = hash % base

        let quotient: Int64 = (hash - remainder)/base



        let index: Int = Int(truncatingIfNeeded: remainder)

        guard index < alphabetArray.count else {

            throw HashingError.invalidHash

        }



        let char: Character = alphabetArray[index]

        return try reverseHash(quotient) + String(char)

    }

}

And here it is in use:

let base37 = try! CustomHasher(alphabet: "acdegilmnoprstuw",

                               offset: 7,

                               base: 37)



do {

    try base37.hash("leepadg")

} catch {

    print(error)

}



do {

    try base37.reverseHash(680131659347)

} catch {

    print(error)

}

Feedback on all aspects of the code is welcome, such as (but not limited to):

• Should such a hasher throw? Or would it be more natural/idiomatic to return nil if it fails?


• Possible improvements (speed, clarity, especially the latter),


• Naming,


• Better comments.

General stuff

Several explicit type annotations are not needed, such as in

var h: Int64  = offset



if let index: Int = alphabetArray.firstIndex(of: char)



let remainder: Int64 = hash % base

let quotient: Int64 = (hash - remainder)/base

Error handling

• 
  

  In the initializer:

  
  
  

  Throwing an error for illegal parameters is fine, and allows to provide more details about the error than in a failable initializer. I only wonder why offset is required to be strictly positive. Is there any problem with allowing a zero offset?

  
  


• 
  

  In the hash method:

  
  
  

  Again, throwing an error for bad input seems fine to me. However: Most hashing method accept arbitrary long input strings. If “overflow” is an error for this very special hasher then I would call just it overflow error instead of exceedsInt64.

  
  


• 
  

  In the reverseHash method:

  
  
  

  This is again a special situation for this hasher, most hashing methods are designed in a way to make “dehashing” as computing intensive as possible. Here I would return nil instead of throwing an error if no matching source string is found, meaning “no result.”

  
  

The overflow checking

It is not immediately obvious how self.stringLengthLimit is calculated, this calls for an explaining comment. Also I am always a bit suspicious if integer and floating point arithmetic is mixed: A (64-bit) Double has a 53-bit significand precision and cannot store all 64-bit integers precisely.

Anyway: Detecting an overflow based on the string length alone cannot work in all cases. Here is an example: With

let base10 = CustomHasher(alphabet: "0123456789", offset: 9, base: 10)

the hash of "223372036854775807" fits into a 64-bit integer, but your program rejects that input string because its length exceeds stringLengthLimit = 17."223372036854775808" has the same length, but its hash calculation would overflow.

This shows that it is difficult to detect the overflow in advance. As an alternative, one could use the “overflow-reporting methods” for multiplication and addition. This is more code (and not nice to read) but detects overflow reliably:

guard let index = alphabetArray.firstIndex(of: char) else {

    throw HashingError.outOfAlphabet(alphabet)

}

guard

    case let r1 = h.multipliedReportingOverflow(by: base), !r1.overflow,

    case let r2 = r1.partialValue.addingReportingOverflow(Int64(index)), !r2.overflow

    else {

        throw HashingError.exceedsInt64

}

h = r2.partialValue

Of course these thoughts apply only to your special hasher. Usually one would accept arbitrary input, using (for example) &+ and &* for addition and multiplication with automatic “wrap around.”

Simplifications

There is not very much to say, the code is written clearly. You store the given alphabet both as the original string and as an array of characters, but later use only the array.

The second line in

let remainder = hash % base

let quotient = (hash - remainder)/base

can be simplified to

let quotient = hash/base

You can also compute both quotient and remainder with a call to the BSD library function lldiv

let remQuot = lldiv(hash, base)

but I doubt that it would be faster.

The recursion in the dehasher could be replaced by an iteration, that would allow to append to the result string, and only reverse once, instead of prepending characters to a string repeatedly:

var hash = hash

var result = ""

while hash > offset {

    let remainder = hash % base

    hash = hash / base

    let index = Int(truncatingIfNeeded: remainder)

    guard index < alphabetArray.count else {

        return nil

    }

    result.append(alphabetArray[index])

}

return hash < 0 ? nil : String(result.reversed())

But since the number of recursions/iterations is quite limited it probably won't make much of a difference, and you can choose what you find more natural.

Naming

CustomHasher does not tell anything about the type. I am not good in finding names, perhaps TrelloHasher if you want to emphasize where it comes from, or MultAddHasher ... naming is difficult (and subjective)!

Possible alternative method names would be

func hash(of s: String) {}

func string(for hash: Int64) {}