Implementing Hash Table Algorithms in Swift

Since the requirement to create a hashindex is specific to Keyable types, this action can be accessed through a protocol extension://note: an extension on a protocolextension Keyable {//compute table index func hashindex<T>(for key: String!, using buckets: Array<T>) -> Int { var remainder: Int = 0 var divisor: Int = 0 //trivial case guard key != nil else { return -1 } for item in key.unicodeScalars { divisor += Int(item.value) } remainder = divisor % buckets.count return remainder } }Effective hash tables rely on the performance of their hash algorithms..In this example, hashindex is a straightforward algorithm that employs modular math.ADDING ELEMENTSWith the components in place, we can define the method for adding items..The following snippet provides some important insights:….func append(_ element: T) -> Result { let result: Result //compute hash let hashIndex = element.hashindex(for: element.keystring, using: buckets) if hashIndex != -1 { let childToUse = Node<T>() childToUse.key = element //check existing list if buckets[hashIndex] == nil { buckets[hashIndex] = childToUse results = Results.Success } …With any hash algorithm, the goal is to create enough complexity to eliminate collisions..By producing unique indexes, our corresponding table can provide constant time — O(1) operations for insertion, modification and lookup..Hash Table collisions occur when different inputs compute to the same hash..Based on the relatively straightforward design of our hashindex() algorithm, the inputs of “Albert Einstein” and “Andrew Collins” always produce the same hash result of “8”.The creation of hash algorithms is considered more art than science..As a result, there are many techniques to help reduce the potential of collisions..Beyond using modular math to compute a hash, we’ve applied a technique called separate chaining..By applying a process similar to building a linked list, this will allow multiple table elements to share the same index value:….// table separate chaining processelse { var head = buckets[hashIndex] as Node<T>?.//append item childToUse.next = head head = childToUse //update chained list buckets[hashIndex] = head results = Results.Collision } …FINDING ELEMENTSThe process for finding elements is similar to the append() process.. More details

Leave a Reply