Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

How to study your flashcards.

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key

image

Play button

image

Play button

image

Progress

1/5

Click to flip

5 Cards in this Set

  • Front
  • Back

What are hash tables?

Hash tables are a data structure that maps keys to values for highly efficient lookup.

How are hash tables typically implemented?

A hash table typically has an underlying array and a hash function.



When you want to insert an object and its key, the hash function maps the key to an integer which indicates the index in the array.


The object is then stored in that index.

What are "collisions" in hash tables? How do we deal with them?

Collisions are when two objects are stored in the same index: hash(key).



This typically occurs when we have space constraints for the arrays.



To handle this issue, you can instead store objects in a linked list at index hash(key) % array_length.



To get the object with a particular key, you must search the linked list for this key.

What is an ArrayList? (Java)

This is an array that resizes itself as needed (i.e. a dynamically resizing array) while still providing O(1) access.

How do you typically implement ArrayList?

When the array is full, double in size.



Each doubling takes O(n) time but happens so rarely that its amortized time is still O(1)