Posts

Introduction Let’s take a closer look at a HashMap implementation by building it without using the built-in dictionary in Swift. The HashMap will use a fixed-size array underneath the hash function that will transform the key into an index. In this example, the hash function is based on taking the modulo of the sum of all key.unicodeScalars integer values with the size of the array. Code Example final class HashMap<Key: StringProtocol, Value> { private var hashMap: [(key: Key, value: Value)?] init(size: Int) { self.hashMap = Array(repeating: nil, count: size) } private func hashFunction(key: Key) -> Int { var count = 0 for element in key.unicodeScalars { count += Int(element.value) } return count % self.hashMap.count } } Insert The insert operation uses the index provided by the hashFunction and sets the value at this index. ...

What is Hashmap (aka Hash Table)? A hashmap is a data structure that implements an associative array, also called a dictionary. An associative array maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During a lookup, the key is hashed, and the resulting hash indicates where the corresponding value is stored. ...

What is a Red-Black Tree? A Red-Black tree is a self-balancing binary search tree data structure. When the tree is modified, the new tree is rearranged and “repainted” to restore the coloring properties that constrain how unbalanced the tree can become in the worst case. source Properties A Red-Black tree has all binary search tree properties, with some additional properties: Every node is either red or black. All nil nodes are considered black. A red node does not have a red child. If a node is red, then both its children are black. Every path from a given node to any of its descendant nil nodes goes through the same number of black nodes. Time Complexity The (re-)balancing is not perfect, but guarantees searching in O(log n) time, where n is the number of entries in the tree. The insert and delete operations, along with tree rearrangement and recoloring, also execute in O(log n) time. ...

What is the BST inorder algorithm? The inorder algorithm returns values in ascending order (sorted from smallest to the largest value). Code example final class BSTNode<Value: Comparable> { var val: Value? var left: BSTNode? var right: BSTNode? init(val: Value? = nil) { self.val = val } func inorder(_ visited: inout [Value]) -> [Value] { if self.left != nil { self.left!.inorder(&visited) } if self.val != nil { visited.append(self.val!) } if self.right != nil { self.right!.inorder(&visited) } return visited } } Implementation The inorder algorithm: Recursively traverse the left subtree. Visit the current node. Recursively traverse the right subtree. Time/Space complexity The time complexity of the inorder algorithm is O(N), where N is the total number of nodes. The space complexity: ...

Code Example final class BSTNode<Value: Comparable> { var val: Value? var left: BSTNode? var right: BSTNode? init(val: Value? = nil) { self.val = val } func exists(_ val: Value) -> Bool { // 1 guard let selfVal = self.val else { return false } // 2 if self.val == val { return true } // 3 if val < self.val! { if self.left == nil { return false } return self.left!.exists(val) } // 4 if self.right == nil { return false } // 5 return self.right!.exists(val) } } Implementation The exists algorithm: Check if self.val exists. If it does not exist, return false. If it does, move to the next step. Compare self.val with the input value. If the values are equal, return true. If they are not equal, move to the next step. If the input val is less than self.val, and the left node exists, return a recursive call of the exists method on the left node; otherwise, return false. If the input val is greater than self.val, move to the next step. Check if the right node exists. If it does not exist, return false. If it does exist, move to the next step. Return a recursive call of the exists method on the right node. Time/Space Complexity Time complexity: The time complexity of the exists algorithm is O(N), where N is the total number of nodes. Space complexity: O(1) if recursion stack space is not considered. Otherwise, O(H), where H is the height of the tree. In the worst case, H can be the same as N (when the tree is skewed). In the best case, H can be the same as log N (when the tree is complete). Thank you for reading! 😊