HashTable/HashMap/Map data structure

/
fundamentals

This tutorial is a part of the Data Structures and Algorithms class:

Map (HashTable/Hashmap) data structure:

  • non-ordered, key : value pairs.
  • key is a random string, can be created by you or a hash function.
  • value can contain any kind of data structure. Example: string, array, object, ...
  • usually used for caching, because of fast O(1) access with key.
  • in Javascript, an Object is also a Map data structure.

map

How data looks like (print it out!)

lecture-6/map-data-structure.js
// initialize

// object style
const map1 = { // map name to super heros
  'Tony Stark': 'Iron Man',
  'Clark Kent': 'Superman',
}

// Map class style
const map2 = new Map() // map name to super superheroines
map2.set('Diana Prince', 'Wonder Woman')
map2.set('Wanda Maximoff', 'Scarlet Witch')

// print out, see how data looks like
console.log(map1)
// { 'Tony Stark': 'Iron Man', 'Clark Kent': 'Superman' }

console.log(map2)
// Map {
//   'Diana Prince' => 'Wonder Woman',
//   'Wanda Maximoff' => 'Scarlet Witch'
// }
$ node map-data-structure.js
{ 'Tony Stark': 'Iron Man', 'Clark Kent': 'Superman' }
Map {
  'Diana Prince' => 'Wonder Woman',
  'Wanda Maximoff' => 'Scarlet Witch'
}

How to insert/delete/access/search data

lecture-6/map-data-structure.js
// insert
map1['Carol Danvers'] = 'Captain Marvel' // object style
map2.set('Bruce Banner', 'The Hulk') // Map class style

console.log(map1)
// {
//   'Tony Stark': 'Iron Man',
//   'Clark Kent': 'Superman',
//   'Carol Danvers': 'Captain Marvel'
// }

console.log(map2)
// Map {
//   'Diana Prince' => 'Wonder Woman',
//   'Wanda Maximoff' => 'Scarlet Witch',
//   'Bruce Banner' => 'The Hulk'
// }

// delete
delete map1['Tony Stark'] // object style
map2.delete('Diana Prince') // Map class style

console.log(map1)
// { 'Clark Kent': 'Superman', 'Carol Danvers': 'Captain Marvel' }

console.log(map2)
// Map {
//   'Wanda Maximoff' => 'Scarlet Witch',
//   'Bruce Banner' => 'The Hulk'
// }

// search
// object style
console.log(map1['Clark Kent']) // Superman

// Map class style
console.log(map2.get('Wanda Maximoff')) // Scarlet Witch
$ node map-data-structure.js
{
  'Tony Stark': 'Iron Man',
  'Clark Kent': 'Superman',
  'Carol Danvers': 'Captain Marvel'
}
Map {
  'Diana Prince' => 'Wonder Woman',
  'Wanda Maximoff' => 'Scarlet Witch',
  'Bruce Banner' => 'The Hulk'
}
{ 'Clark Kent': 'Superman', 'Carol Danvers': 'Captain Marvel' }
Map {
  'Wanda Maximoff' => 'Scarlet Witch',
  'Bruce Banner' => 'The Hulk'
}
Superman
Scarlet Witch

How fast to insert/delete/access/search data

Data Structure Insert Delete Access Search
Map
Object		 O(1): set
O(1): object.['key'] =		 O(1): delete
O(1): delete		 O(1) with key: get
O(1): object.['key']		 O(1) with key
O(n) no key

⬆️ Time complexity (worst case) per operation

Real life interview questions

  1. Do you know how your data looks like?
  2. What options do you have to use Map data structure in Javascript? Give 2 examples.
  3. What is Map usually used for?
  4. How do you insert/delete/access/search with Map data structure?
  5. What is the Time Complexity of Map data structure on insert/delete/access/search operation?
  6. Write a simple program to demonstrate the substantial difference of search speed of Array and Map data structure.
  7. Write a simple program to demonstrate the case where search speed of Array and Map data structure are roughly the same.
  8. You are tasked to write a simple phonebook application in a new operating system for smartphone. The application will take the first name and output the phone number of that person. What data structure can help to achieve the best performance. Explain why.