| Summary: |
Sets contain an unordered collection of elements modelling the mathematical set. Maps make it possible to associate a key to another set of values. Hash tables are implementations of map structure.
We have already seen search strategies for different data structures and the best ones with O(log2 n) are binary search (the data must be ordered) and a Binary search tree (the tree must be balanced). The question is can we do better than this?
Consider storing a value k at array location k. In such a case, searching for a value k could use the array index directly. Such an operation is O(1) irrespective of the size of the array. In hashing, we map a given key to its corresponding array index location enabling search for an item in O(1).
This week we will:
• Look at the Java Set and Map interfaces and how to use them
• Learn about hash coding and its use to facilitate efficient insertion, removal, and search
• Look at different forms of collision strategies for hash tables—open addressing and chaining—and to consider their relative benefits and performance trade-offs |
Loading previews...
