I was curious about some data structures, and the hash table is one of them. I was wondering how I could implement one of these guys using Swift.
They're really powerful data structures when well implemented. Basically their insertion and fetch are made in constant time — O(1) if well implemented. The worst case scenario is O(n) for both actions.
I will imagine that you know more or less what is a hash table. If you don't know I recommend you check Wikipedia or any other website. Here I will focus more on the implementation itself. Let's go?
First of all, I created a node for that hash table. Each node contains a value, a key associated with that value and also a reference for a next node. This value will be of a generic type.
Also, I wanted to have an operation status for the insertion in the hashtable, just to inform the user of what happened. This step is usually not necessary, but I still wanted to implement it. The insertion could have a success status, which means that the value was successfully added to the bucket, this is the best-case scenario. The other case is a collision, when the value was added to the bucket, but there was a collision, which means we had to go find a spot for that new node in the linked list of nodes. Finally, I imagined another case would be to experience a replacement of a key/value.
Now we’re ready to implement the Hash Table itself. Basically it will have a bucket, which in our case will be a list of nodes. These nodes basically are going to be the first nodes of a possible sequence of nodes occupying the same index pointed by the hash function. Here we have a generic type as well. And it’s pretty much it. The only exceptional thing done here would be to fill that array with empty references of nodes. We do it in the init of the Hash Table, as can be seen below.
The important now are the operations. Let’s begin with the most basic operation, the add. Basically what this function will do is check the index pointed by the hash function. If that index is empty, good, it’s the optimal case, we just create a new node and assign it to that index. Otherwise, we’ll have to go through the node’s nextNode till we find a nil spot and assign it to our new node, as we can read in the implementation below. Also, it’s important to note how the insertion operation status is implemented here.
Now the fetch operation. The user will try to fetch an object by a specific key. What I do here is, I get this key, check what’s the index provided by the hash function to that given key and then I check in the nodes of that index if there’s any matching to that key. If yes we return the value, otherwise we just return nil.
Delete will work in a very similar way. We receive a key, get that associated index for that key and then we check in all nodes of that index if there’s any of them matching the given key. Let’s see some code.
The big deal of this type of structure is the hash function. It has to calculate the index based on the key in constant time to worth all the hard work we have done so far. I made a lazy implementation of it, using just the values of the string. It’s not actually constant because it will get each character of the string key and make math using the unicode int value of that character. But there’s no much secret here, just make a code that’s constant and you’ll be fine.
This is enough to consider we have a hashtable implemented. To check all this code running you can pull some code from my GitHub. I plan to put there some other data structures in a close future.
Thanks for stopping by! Leave a like if you enjoyed this post. Connect with me on LinkedIn. Also, comment if there's any question.