Data Structures and Algorithms: Week 10 - Sets, Maps and tables

LoadingLoading previews...
Sets, Maps and Tables
HTML Creative Commons: Attribution-Noncommercial-No Derivative Works 4.0
View
    Sets, Maps and Tables
    Sets, Maps and Tables
    1 file in this resource
    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
    Creators:
    Divisions: Academic > School of Computing, Engineering and Built Environment > Department of Computing > Computing
    Copyright holder: Copyright © Glasgow Caledonian University
    Viewing permissions: World
    Depositing User:
    Date Deposited: 19 Jul 2018 08:21
    Last Modified: 13 Feb 2020 10:03
    URI: https://edshare.gcu.ac.uk/id/eprint/3856

    Actions (login required)

    View Item View Item

    Toolbox

    There are no actions available for this resource.