CMPS 260: Data Structures
Introduction
Until now, we have been able to store and retrieve individual elements in different ways. But what would we have to do if we need to store key-value pairs? The idea of using key-value pair is to allow one to store and retrieve a value given the key, just like you would look up a definition of a word in the dictionary. The dictionary data structure achieves exactly that. One way to implement dictionaries is to use the implementation we used for a set and modify it slightly. However, commonly dictionaries are implemented with hashes and this results in hash tables. The idea is to map each key onto an index with a hash function and then store all the elements in an array. One of the challenges is that the hash function should prevent or resolve collisions, which are two keys that map to the same index. We will look at separate chaining and linear probing to deal with collisions.
Module Objectives
- Describe dictionaries
- Implement and use dictionaries
- Describe hash tables
- Implement and use hash tables
- Explain hash table collisions
Learning Resources
- Module 8 Readings: Chapter 7 (skip ECMAScript sections)
- Module 8 Slides: Chapter 7
Learning Activities
- Module 8 Assignment
For Further Study
- Read more about dictionaries on Wikipedia
- Read more about hash tables on Wikipedia