This week's class was primarily about the concept, implementation, and the performance advantage of the sorted binary tree data structure when it comes to searching. But while the worst case O(logn) runtime is impressive, there is actually another search method that eclipses the search power of the sorted binary tree - searching by means of a hash table.
First, a hash table is a array-like data structure that has a key and an associated value (similar to the dict type in Python). the nature of the value varies depends on the usage of the hash table. In the case of storage of raw data, the value is the memory address of the file/data. For the purpose of, say storing a list of numbers, the value *can* be the numbers themselves. So what are the keys? To obtain a key, a hash function is used to designate each value a unique number. So, when a user is searching for a particular number, the search engine only has to use the hash function to get a key, which can then be used to get the value directly from the table.
With hash tables, the worst case runtime is in the O(1) - constant time. Of course, the implementation is not easy and I would not be surprised if I only get to learn them in my third year.
No comments:
Post a Comment