In this chapter
- hash table is most basics data structure, its has many use cases
- implementation, collisions, and hash functions
suppose you work at grocery store when customer buy a product you have to look up price in a book. if book is unalphabetized it can take long time you have to look at every line means O(n) time
if book is alphabetized you can could run bianry search find the price. That would only take O(log n) time.
you already know binary search is fast, but as a cashier looking things up in book is pain.
You can feel the customer steaming up as you search for items in the book.
you need a buddy who has all the names & price memorized then you dont need to look up anything, you ask her, and she tells you the answer instantly.
Your buddy Maggie can give you the price in O(1) time for any item
| Itens | SIMPLE SEARCH | BINARY SEARCH | MAGGIE |
| O(n) | O(logn) | O(1) | |
|---|---|---|---|
| 100 | 10 sec | 1 sec | INSTANT |
| 1000 | 1.6 min | 1 sec | INSTANT |
| 00000 | 16.6 min | 2 sec | INSTANT |
You could implement this book as an array
|(APPLE, 2.49) |(MILK, 1.49)|(PEAR, 0.79)|
If you sort this array by name, you can run binary search on it to find the price of an item. So you can find items in O(log n) time
But you want to find items in O(1) time. That is, you want to make a “Maggie.” That’s where hash functions come in.
A hash function is a function where you put in a string and you get back a number.
"NAMASTE" <=> 7
"HOLA" <=> 4
"HELLO" <=> 2
^ hash function
-
It needs to be consistent. For example, suppose you put in “apple” and get back “4”. Every time you put in “apple”, you should get “4” back. Without this, your hash table won’t work.
-
It should map different words to different numbers. For example, a hash function is no good if it always returns “1” for any word you put in. In the best case, every different word should map to a different number.
-
The hash function consistently maps a name to the same index.
-
The hash function maps different strings to different indexes
-
The hash function knows how big your array is and only returns valid indexes a hash function and an array together, and you get a data structure called a hash table.
You’ll probably never have to implement hash tables yourself. Any good language will have an implementation for hash tables.
let book = {} // empty hash table
book[“apple”] = 0.67 // An apple costs 67 cents.
book[“milk”] = 1.49 // Milk costs $1.49.
book[“avocado”] = 1.49
console.log(book) //
- Using hash tables for lookups
- Preventing duplicate entries
- Using hash tables as a cache
hashes are good for
- Modeling relationships from one thing to another thing
- Filtering out duplicates
- Caching/memorizing data instead of making your server do work
when two distinct pieces of data in a hash table share the same hash value.
if multiple keys map to the same slot, start a linked list at that slot.
hash tables take O(1) for everything. O(1) is called constant time.
to make hash table faster you needto avoid collisions. To avoid collisions, you need
- A low load factor
- A good hash function
Load factor = Number of item in Hash table / Total number of slots
Hash tables use an array for storage, so you count the number of occupied slots in an array. For example, this hash table has a load factor of 2/5, or 0.4.
Once the load factor starts to grow, you need to add more slots to your hash table. This is called resizing.
resize when your load factor is greater than 0.7
A good hash function distributes values in the array evenly.
In this chapter
- how to model a network using a new, abstract data structure: graph
- breadth-first search -> “What’s the shortest path to go to X?”
- You learn topological sort, algorithm that exposes dependencies between nodes
Breadth-first search allows you to find the shortest distance between two things.
- Write a checkers AI that calculates the fewest moves to victory
- Write a spell checker (fewest edits from your misspelling to a real word—for example, READED -> READER is one edit)
- Find the doctor closest to you in your network
The algorithm to solve a shortest-path problem is called breadth-first search.
A graph models a set of connections
Graphs are made up of nodes and edges
A node can be directly connected to many other nodes. Those nodes are called its neighbors
Node: An individual part of a graph Edges: represent relationships between nodes.
/*
EDGE +------+
+---------------------> B |
| | |
| +--->---^--+
+--+----+ | |
| | | |
| A | | |
+-------+ | | +------+
NODE | +--------+-- C |
| | |
++----+ +------+
| D |
| |
+-----+
*/It can help answer two types of questions:
- Question type 1: Is there a path from node A to node B?
- Question type 2: What is the shortest path from node A to node B?
IN BFS you need to search item in the order that they’re added.
There’s a data structure for this: it’s called a queue.
-
First in first out
-
A queue works the same way. Queues are similar to stacks.
-
Cant access random element
-
There are two only operations, enqueue and dequeue.
If you enqueue two items to the list, the first item you added will be dequeued before the second item.
A graph consists of several nodes. each node is connected to neighboring nodes
How do you express a relationship like “you -> bob”? Luckily, you know a data structure that lets you express relationships: a hash table!
graph = {};
graph["you"] = ["alice", "bob", "claire"];Directed graph
┌───┐ ┌───┐
│ ─┼────────────────┼─► │
│A ◄┼────────────────┼─B │
└───┘ └───┘
Undirected graph
┌───┐ ┌───┐
│ ┼────────────────┼ │
│ A │ │ B │
└───┘ └───┘
let people = ["alice", "bob", "claire"];-
keep a queue containing the people to check
-
pop the person off the queue
-
check the person is a we looking for 4a. if yes DONE 4b. if not add all neighbors to the queue
-
Loop
-
if queue is empty there is no person we looking for
function bfs(graph) {
let searchQueue = [];
searchQueue.push(...graph["you"]);
while (searchQueue.length > 0) {
let person = searchQueue.shift();
if (personIsSeller(person)) {
console.log(`${person} is a mango seller!`);
return true;
} else {
searchQueue.push(...graph[person]);
}
}
return false;
}
function personIsSeller(name) {
return name[name.length - 1] == "m";
}
let graph = {};
graph["you"] = ["alice", "bob", "claire"];
graph["bob"] = ["anuj", "peggy"];
graph["alice"] = ["peggy"];
graph["claire"] = ["thom", "jonny"];
graph["anuj"] = [];
graph["peggy"] = [];
graph["thom"] = [];
graph["jonny"] = [];
console.log("bfs", bfs(graph));Adding one person to the queue takes constant time: O(1).
Doing this for every person will take O(number of people) total.
Breadth-first search takes O(number of people + number of edges), O(V+E) (V for number of vertices, E for number of edges).
a tree. A tree is a special type of graph, where no edges
ever point back.
e.g
/*
┌───┐
│ │
┌───┴───┴┐
│ │
┌──▼┐ ┌─▼─┐
│ │ │ │
└───┘ ┌──┴───┘
│
│
┌──▼┐
│ │
└───┘
*/
In this chapter
- a way to assign more or less weight to some esges
- you learn Dijkstra’s algorithm, answer What’s the shortest path to X? for weighted graph
- cycles in graphs
/*
6 ┌────┐ 1
┌─────────► A ┼─────────┐
│ └──▲─┘ │
│ │ │
┌┼───┐ │ ┌─▼──┐
START │ │ │ │ │ FINISH
└──┬─┘ │ └──▲─┘
│ ┌┴───┐ │
│ │ B │ │
└─────────► ┼────────┘5
2 └────┘
*/- each segment has travel time in minute, we will use Dijkstra’s algorithm to go from start to finish in the shortest possible time 2.If you ran breadth-first search on this graph, you’d get this shortest path.
┌─────────────────────────────────┐
│ 7 MINUTES │
│ │
│ 6 ┌────┐ 1 │
│ ┌─────────► A ┼─────────┐ │
│ └──▲─┘ │
│ │ │
┌┼───┐ │ ┌─▼──┐
START │ │ │ │ │ FINISH
└──┬─┘ │ └──▲─┘
│ ┌┴───┐ │
│ │ B │ │
└─────────► ┼────────┘5
2 └────┘
Bothe takes 7 minutes
Lets see if you can find shortest path using Dijkstra’s algorithm
- find a cheapest node, node that least amount of time
- update the costs of the neighbours of the node
- repeat until you have done this for every node in a graph
- calculte the final cost
STEP 1
find a cheapest node You’re standing at the start, wondering if you should go to node A or node B. How long does it take to get to each node?
It takes 6 minutes to get to node A and 2 minutes to get to nodeB.
The rest of the nodes, you don’t know yet
Node B is the closest node … it’s 2 minutes away
STEP 2 Calculate how long it takes to get to all of node B’s neighbors by
following an edge from B.
- A shorter path to A (down from 6 minutes to 5 minutes)
- A shorter path to the finish (down from infinity to 7 minutes)
Step 3: Repeat!
You’ve run Dijkstra’s algorithm for every node (you don’t need to run it for the finish node). At this point, you know
Step 1 again: Find the node that takes the least amount of time to get to. You’re done with node B, so node A has the next smallest time estimate
Step 2 again: Update the costs for node A’s neighbors
it takes 6 minutes to get to the finish now!
- It takes 2 minutes to get to node B.
- It takes 5 minutes to get to node A.
- It takes 6 minutes to get to the finish.
A B
┬──────┬──────┬
│ NODE │ TIME │
├──────┼──────┼
│ A │ 5 │
├──────┼──────┼
│ B │ 2 │
├──────┼──────┼
│FINISH│ 6 │
└──────┴──────┴
Dijkstra’s algorithm, each edge in the graph has a number associated with it. These are called weights.
A graph with weights is called a weighted graph. A graph without weights is called an unweighted graph.
To calculate the shortest path in
an unweighted graph, use breadth-first search.
a weighted graph, use Dijkstra’s algorithm.
Graphs can also have cycles. A cycle looks like this
/*
┌───────────┐
│ │
│ │
┌────────┼──► │
│ │ │
│ │ ──┼────────┐
│ └───────────┘ │
│ │
│ │
│ │
│ │
│ │
│ │
│ │
┌──┼────────┐ ┌────┼────┐
│ │ │ │ ▼ │
│ │ │ │
│ ◄─┼───────────────┼──── │
│ │ │ │
└───────────┘ │ │
└─────────┘
*/
Dijkstra’s algorithm only works with directed acyclic graphs, called DAGs for short.
You can’t use Dijkstra’s algorithm if you have negative-weight edges.
Negative-weight edges break the algorithm.
Bellman-Ford algorithm
If you want to find the shortest path in a graph that has negative-weight edges, there’s an algorithm for that! It’s called the Bellman-Ford algorithm.
let graph = {};
graph["start"] = {};
graph["start"]["a"] = 6;
graph["start"]["b"] = 2;
graph["a"] = {};
graph["a"]["fin"] = 1;
graph["b"] = {};
graph["b"]["a"] = 3;
graph["b"]["fin"] = 5;
graph["fin"] = {};
// graph for updating costs
let infinity = Infinity;
let costs = {};
costs["a"] = 6;
costs["b"] = 2;
costs["fin"] = infinity;
parents = {};
parents["a"] = "start";
parents["b"] = "start";
parents["fin"] = null;
let processed = [];
function findLowestCostNode(costs) {
let lowestCost = Infinity;
let lowestCostNode = null;
// Go through each node.
for (const node in costs) {
const cost = costs[node];
// If it’s the lowest cost so far and hasn’t been processed
if (cost < lowestCost && !processed.includes(node)) {
// set it as the new lowest-cost node.
lowestCost = cost;
lowestCostNode = node;
}
}
return lowestCostNode;
}
let node = findLowestCostNode(costs);
while (node !== null) {
let cost = costs[node];
let neighbors = graph[node];
for (let n in neighbors) {
let newCost = cost + neighbors[n];
if (costs[n] > newCost) {
costs[n] = newCost;
parents[n] = node;
}
}
processed.push(node);
node = findLowestCostNode(costs);
}
console.log("processed", processed);