Mastering Algorithms With C - Kyle Loudon [80]
Q: What is the worst-case performance of searching for an element in a chained hash table? How do we ensure that this case will not occur?
A: A chained hash table performs the worst when all elements hash into a single bucket. In this case, searching for an element is O (n), where n is the number of elements in the table. A ridiculous hash function that would result in this performance is h (k) = c, where c is some constant within the bounds of the hash table. Selecting a good hash function ensures that this case will not occur. If the hash function approximates uniform hashing well, we can expect to locate an element in constant time.
Q: What is the worst-case performance of searching for an element in an open-addressed hash table? How do we ensure that this case will not occur?
A: The worst-case performance of searching for an element in an open-addressed hash table occurs once the hash table is completely full and the element we are searching for is not in the table. In this case, searching for an element is an O (m) operation, where m is the number of positions in the table. This case can occur with any hash function. To ensure reasonable performance in an open-addressed hash table, we should not let the table become more than 80% full. If we choose a hash function that approximates uniform hashing well, we can expect performance consistent with what is presented in Table 8.1.
Related Topics
Direct-address tables
A simple type of hash table in which there is a one-to-one mapping between all possible keys and positions in the table. Since no two keys map to the same position, there is no need for collision resolution. However, if there are many possible keys, the table will be large. Generally, direct addressing works well when the universe of possible keys is small.
Linear congruential generators
A common class of random number generators. Understanding the principles behind random number generators can help in devising good hash functions.
Quadratic probing
An alternative to linear probing and double hashing for probing an open-addressed hash table. In quadratic probing, the sequence of positions probed is determined using a quadratic-form hash function. In general, quadratic probing performs better than linear probing, but it does not perform as well as double hashing. Quadratic probing results in secondary clustering , a form of clustering that is less severe than the primary clustering of linear probing.
Universal hashing
A hashing method in which hashing functions are generated randomly at runtime so that no particular set of keys is likely to produce a bad distribution of elements in the hash table. Because the hash functions are generated randomly, even hashing the same set of keys during different executions may result in different measures of performance.
Chapter 9. Trees
Picture a family tree, the draw sheet of a tournament, or the roots of a plant; these are all good examples of a tree's organization as a data structure. In computing, a tree consists of elements called nodes organized in a hierarchical arrangement. The node at the top of the hierarchy is called the root . The nodes directly below the root are its children , which in turn usually have children of their own. With the exception of the root, each node in the hierarchy has exactly one parent, which is the node directly above it. The number of children a node may parent depends on the type of tree. This number is a tree's branching factor, which dictates how fast the tree will branch out as nodes are inserted. This chapter focuses on the binary tree, a relatively simple but powerful tree with a branching factor of 2. It also explores binary search trees, binary trees organized specifically for searching.
This chapter covers:
Binary trees
Trees containing nodes with up to two children. The binary tree is a very popular type of tree utilized in a wide variety of problems.