Code 401: Class 30 - Implementation: Hash Tables

Watch: What is a hash table?

Hash is the result of an algorithm taking in a string and returning a value for security or an index position
Bucket is an index position in an array, may contain multiple value pairs
Collisions are when two different strings are hashed to the same index
Every bucket or node has a key/value pair
Lookups using hashing can be done in O(1) time complexity
Standard methods:
- Add() Send the key to the GetHash method, go to that index, check for collision, if not place in index, if collision place in data structure in that bucket
- Find Takes in key and gets hash, goes to index, iterates through looking for a match, returns value
- Contains Accept key, returns boolean if the key exists in hash table, if found returns index
- GetHash Take in key, performs hash, returns index of where key/value should be placed

Real world examples: student numbers, book dewy decimal system
Hash function, any function that can map a data set of arbitrary size to a fixed size
- Ideal functions: easy to compute, evenly distributes results across the hash table