Join Simon Allardice for an in-depth discussion in this video Using hash tables, part of Foundations of Programming: Data Structures.
- View Offline
This idea of hashing is fundamental to…understanding the data structure called a hash table.…A hash table is the typical way to implement an associative array.…In your language, these might be called dictionaries, or…maps, or hashes, or even just called hash tables.…The big benefit of hash tables over arrays and…over linked lists is they're very fast, both for looking…at whether an item exists or finding a specific item…in a hash table, and for inserting and deleting items.…Let's take a look at why.…
When a hash table is created, it's…really internally a very undramatic array-based data…structure, but it's adding extra functionality to…get us past the limitations of an array.…Now, hash tables can usually be created with an initial capacity, and if you know…how large it's going to be, it is better to do that for memory management.…But even if it has to be a flexible number of elements, the idea is the same.…That a hash table begins with multiple…placeholders, multiple buckets, all just waiting for content.…
Starting with simple ways of grouping data like arrays and structs, together you'll explore gradually more complex data structures, like dictionaries, sets, hash tables, queues and stacks, links and linked lists, and trees and graphs. Simon keeps the lessons grounded in the real world and answers the "why" behind many data-structuring decisions: Why use a hash table? Why is a set useful? Why avoid arrays? When you're finished with the course, you'll have a clear understanding of data structures and understand how to use them in whatever language you're programming in, today or 5 years from now.
- What is a data structure?
- Using C-style structs and arrays
- Sorting and searching arrays
- Working with singly and doubly linked lists
- Using stacks for last-in, first-out (LIFO) structures
- Using queues for first-in, first-out (FIFO) structures
- Working with hash tables
- Understanding binary search trees (BSTs)
- Learning about graphs