B-Trees, LLRBs, Hashing
Exam Prep 07
CS61B Fall 2024
Announcements
Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday |
| 10/14 Weekly Survey 8 Due | | | | 10/18 Lab 7 Due Project 2A Due Midterm 2 Review | |
| 10/21 Homework 3 Due | | | 10/24 Midterm 2 (7-9 PM) | | |
CS61B Fall 2024
Content Review
CS61B Fall 2024
B-Trees
B-Trees are trees that serve a similar function to binary trees while ensuring a bushy structure (check: why don’t BSTs/binary trees generally?). In this class, we’ll often use B-Tree interchangeably with 2-3 Trees.
Each node can have up to 2 items and 3 children. There are variations where these values are higher, known as 2-3-4 trees (nodes can have up to 3 items and 4 children).
All leaves are the same distance from the root, which makes getting take Θ(log N) time.
3
7
4
6
9
1
2
CS61B Fall 2024
B-Trees
When adding to a B-Tree, you first start by adding to a leaf node, and then pushing the excess items (typically the middle element) up the tree until it follows the rules (max 2 elements per node, max 3 children per node).
3
5
7
4
3
7
4
5
9
1
2
9
1
2
1
2
6
6
4
9
6
3
7
5
CS61B Fall 2024
Left Leaning Red Black Trees
LLRBs are a representation of B-trees that we use because it is easier to work with in code. In an LLRB, each multi-node in a 2-3 tree is represented using a red connection on the left side.
3
7
4
6
9
1
2
7
3
9
6
2
4
1
CS61B Fall 2024
LLRB Rules
Each 2-3 tree corresponds to a (unique) LLRB*. This implies that:
All these invariants mean that sometimes our LLRB becomes unbalanced (ie. it violates a rule), so we need some way to fix that.
*2-3-4 trees correspond more generally to regular Red Black Trees, but our focus in 61B is on LLRBs.
CS61B Fall 2024
Why root to null?
Consider the left image below: each leaf is 1 black link away from the root, but it’s not a valid LLRB!
This is because when we convert it to a B-tree, the [3, 7] node will only have 2 children, not 3!
If we check for root-to-null: the right of 3 is 0 black link away, but the other nulls are 1 black link away.
7
3
9
2
3
7
9
2
null
null
null
null
null
CS61B Fall 2024
LLRB Balancing Operations
rotateLeft(A);
A
B
D
C
B
D
A
C
rotateRight(A);
A
B
D
C
B
A
D
C
colorFlip(A);
B
A
D
C
B
A
D
C
we can’t have a right red link
we can’t have 2+ consecutive (left) red links
we can’t have both child links of a node be red
CS61B Fall 2024
Hashing
Hash functions are functions that represent objects as integers so we can efficiently use data structures like HashSet and HashMap for fast operations (ie. get, put/add).
Once we have a hash for our object, we use modulo to find out which “bucket” it goes into. For example, we can create a hash function for the Dog class by overriding Object’s hashCode():
@Override
public int hashCode() {
return 37 * this.size + 42;
}
Then, when we try to put the dog into a HashSet, the HashSet code might look something like this:
int targetBucket = dog.hashCode() % numBuckets;
addToTargetBucket(dog, targetBucket);
CS61B Fall 2024
CS61B Fall 2024
Hashing
In each bucket, we deal with having lots of items by chaining the items and using .equals to find what we are looking for. In a HashMap, we’re specifically concerned with equality of keys in key-value pairs (in HashSet, we only have a value to compare to).
0
1
2
3
<Astro, Jedi>
<Opal, Ali>
<Luna, Elana>
<Fancy, Crystal>
<Tofu, Alexander>
<Artoo, Ali>
**Therefore, it is important that your .equals() function matches the result of comparing hashcodes - if two items are equal, they must also have the same hashcode**
<Mercan, Ergun>
CS61B Fall 2024
Hashing
The load factor tells us when we should resize. We calculate it by dividing the total number of elements added by the number of buckets we currently have. When resizing up, if the load factor exceeds some threshold, we increase the number of buckets we use in the data structure.
Because all elements were initially placed into buckets based on how many buckets were previously available, we also need to rehash all elements into a potentially new destination bucket when resizing, or else subsequent calls to get() may fail.*
* Resizing sounds like a linear-time operation…how does that affect the runtimes of our operations?
CS61B Fall 2024
Valid vs. Good Hashcodes
Properties of a valid hashcode:
Properties of a good hashcode:
CS61B Fall 2024
Worksheet
CS61B Fall 2024
1A LLRB Insertions
5
3
1
4
9
Insert 7
CS61B Fall 2024
1A LLRB Insertions
5
3
1
4
9
Insert 7
7
CS61B Fall 2024
1A LLRB Insertions
5
3
1
4
9
Insert 6
7
CS61B Fall 2024
1A LLRB Insertions
5
3
1
4
9
Insert 6
7
6
CS61B Fall 2024
1A LLRB Insertions
5
3
1
4
7
Insert 6
6
9
CS61B Fall 2024
1A LLRB Insertions
5
3
1
4
7
Insert 6
6
9
CS61B Fall 2024
1A LLRB Insertions
5
3
1
4
7
Insert 6
6
9
CS61B Fall 2024
1A LLRB Insertions
5
3
1
4
7
Insert 2
6
9
CS61B Fall 2024
1A LLRB Insertions
5
3
1
4
7
Insert 2
6
9
2
CS61B Fall 2024
1A LLRB Insertions
Insert 2
5
3
2
4
7
6
9
1
CS61B Fall 2024
1A LLRB Insertions
Insert 8
5
3
2
4
7
6
9
1
CS61B Fall 2024
1A LLRB Insertions
5
3
2
4
7
Insert 8
6
9
1
8
CS61B Fall 2024
1A LLRB Insertions
5
3
2
4
7
Insert 8.5
6
9
1
8
8.5
CS61B Fall 2024
1A LLRB Insertions
5
3
2
4
7
Insert 8.5
6
9
1
8.5
8
CS61B Fall 2024
1A LLRB Insertions
5
3
2
4
7
Insert 8.5
6
8.5
1
9
8
CS61B Fall 2024
1A LLRB Insertions
5
3
2
4
7
Insert 8.5
6
8.5
1
9
8
CS61B Fall 2024
1A LLRB Insertions
5
3
2
4
8.5
Insert 8.5
7
1
9
8
6
CS61B Fall 2024
1B LLRB Insertions
5
3
2
4
8.5
7
1
9
8
6
CS61B Fall 2024
1B LLRB Insertions
5
3
2
4
8.5
7
1
9
8
6
5
CS61B Fall 2024
1B LLRB Insertions
5
3
2
4
8.5
7
1
9
8
6
5
3
4
CS61B Fall 2024
1B LLRB Insertions
5
3
2
4
8.5
7
1
9
8
6
5
3
4
8.5
7
CS61B Fall 2024
1B LLRB Insertions
5
3
2
4
8.5
7
1
9
8
6
5
3
1
4
2
8.5
7
CS61B Fall 2024
1B LLRB Insertions
5
3
2
4
8.5
7
1
9
8
6
5
3
1
4
9
2
8.5
7
6
8
CS61B Fall 2024
1B LLRB Insertions
5
3
2
4
8.5
7
1
9
8
6
5
3
1
4
9
2
8.5
7
6
8
CS61B Fall 2024
2 Hashing Gone Crazy
ECHashMap<TA, Integer> map = new ECHashMap<>();
TA jasmine = new TA("Jasmine the GOAT", 10);
TA noah = new TA("Noah", 20);
map.put(jasmine, 1);
map.put(noah, 2);
noah.semester += 2;
map.put(noah, 3);
jasmine.name = "Nasmine";
map.put(noah, 4);
jasmine.semester += 2;
map.put(jasmine, 5);
jasmine.name = "Jasmine";
TA cheeseGuy = new TA("Sam", 24);
map.put(cheeseGuy, 6);
0
1
2
3
CS61B Fall 2024
2 Hashing Gone Crazy
ECHashMap<TA, Integer> map = new ECHashMap<>();
TA jasmine = new TA("Jasmine the GOAT", 10);
TA noah = new TA("Noah", 20);
map.put(jasmine, 1);
map.put(noah, 2);
noah.semester += 2;
map.put(noah, 3);
jasmine.name = "Nasmine";
map.put(noah, 4);
jasmine.semester += 2;
map.put(jasmine, 5);
jasmine.name = "Jasmine";
TA cheeseGuy = new TA("Sam", 24);
map.put(cheeseGuy, 6);
0
1
2
3
jasmine
Jasmine the GOAT, 10
noah
Noah, 20
CS61B Fall 2024
2 Hashing Gone Crazy
ECHashMap<TA, Integer> map = new ECHashMap<>();
TA jasmine = new TA("Jasmine the GOAT", 10);
TA noah = new TA("Noah", 20);
map.put(jasmine, 1);
map.put(noah, 2);
noah.semester += 2;
map.put(noah, 3);
jasmine.name = "Nasmine";
map.put(noah, 4);
jasmine.semester += 2;
map.put(jasmine, 5);
jasmine.name = "Jasmine";
TA cheeseGuy = new TA("Sam", 24);
map.put(cheeseGuy, 6);
0
1
2
3
jasmine
Jasmine the GOAT, 10
noah
Noah, 20
1
2
CS61B Fall 2024
2 Hashing Gone Crazy
ECHashMap<TA, Integer> map = new ECHashMap<>();
TA jasmine = new TA("Jasmine the GOAT", 10);
TA noah = new TA("Noah", 20);
map.put(jasmine, 1);
map.put(noah, 2);
noah.semester += 2;
map.put(noah, 3);
jasmine.name = "Nasmine";
map.put(noah, 4);
jasmine.semester += 2;
map.put(jasmine, 5);
jasmine.name = "Jasmine";
TA cheeseGuy = new TA("Sam", 24);
map.put(cheeseGuy, 6);
0
1
2
3
jasmine
Jasmine the GOAT, 10
noah
Noah, 22
1
2
3
CS61B Fall 2024
2 Hashing Gone Crazy
ECHashMap<TA, Integer> map = new ECHashMap<>();
TA jasmine = new TA("Jasmine the GOAT", 10);
TA noah = new TA("Noah", 20);
map.put(jasmine, 1);
map.put(noah, 2);
noah.semester += 2;
map.put(noah, 3);
jasmine.name = "Nasmine";
map.put(noah, 4);
jasmine.semester += 2;
map.put(jasmine, 5);
jasmine.name = "Jasmine";
TA cheeseGuy = new TA("Sam", 24);
map.put(cheeseGuy, 6);
0
1
2
3
jasmine
Nasmine, 10
noah
Noah, 22
4
2
3
CS61B Fall 2024
2 Hashing Gone Crazy
ECHashMap<TA, Integer> map = new ECHashMap<>();
TA jasmine = new TA("Jasmine the GOAT", 10);
TA noah = new TA("Noah", 20);
map.put(jasmine, 1);
map.put(noah, 2);
noah.semester += 2;
map.put(noah, 3);
jasmine.name = "Nasmine";
map.put(noah, 4);
jasmine.semester += 2;
map.put(jasmine, 5);
jasmine.name = "Jasmine";
TA cheeseGuy = new TA("Sam", 24);
map.put(cheeseGuy, 6);
0
1
2
3
jasmine
Nasmine, 12
noah
Noah, 22
4
5
3
CS61B Fall 2024
2 Hashing Gone Crazy
ECHashMap<TA, Integer> map = new ECHashMap<>();
TA jasmine = new TA("Jasmine the GOAT", 10);
TA noah = new TA("Noah", 20);
map.put(jasmine, 1);
map.put(noah, 2);
noah.semester += 2;
map.put(noah, 3);
jasmine.name = "Nasmine";
map.put(noah, 4);
jasmine.semester += 2;
map.put(jasmine, 5);
jasmine.name = "Jasmine";
TA cheeseGuy = new TA("Sam", 24);
map.put(cheeseGuy, 6);
0
1
2
3
jasmine
Jasmine, 12
noah
Noah, 22
4
5
3
cheeseGuy
Sam, 24
6
CS61B Fall 2024
2 Hashing Gone Crazy - Resizing!
ECHashMap<TA, Integer> map = new ECHashMap<>();
TA jasmine = new TA("Jasmine the GOAT", 10);
TA noah = new TA("Noah", 20);
map.put(jasmine, 1);
map.put(noah, 2);
noah.semester += 2;
map.put(noah, 3);
jasmine.name = "Nasmine";
map.put(noah, 4);
jasmine.semester += 2;
map.put(jasmine, 5);
jasmine.name = "Jasmine";
TA cheeseGuy = new TA("Sam", 24);
map.put(cheeseGuy, 6);
0
1
2
3
jasmine
Jasmine, 12
noah
Noah, 22
4
5
3
cheeseGuy
Sam, 24
6
4
5
6
7
CS61B Fall 2024
3 Buggy Hash
class Timezone {
String timeZone; // "PST", "EST" etc.
boolean dayLight;
String location;
public int currentTime() {
// return current time in time zone
}
public int hashCode() {
return currentTime();
}
public boolean equals(Object o) {
Timezone tz = (Timezone) o;
return tz.timeZone.equals(timeZone);
}
}
class Course {
int courseCode;
int yearOffered;
String[] staff;
public int hashCode() {
return yearOffered + courseCode;
}
public boolean equals(Object o) {
Course c = (Course) o;
return c.courseCode == courseCode;
}
}
CS61B Fall 2024
3 Buggy Hash
class Timezone {
String timeZone; // "PST", "EST" etc.
boolean dayLight;
String location;
public int currentTime() {
// return current time in time zone
}
public int hashCode() {
return currentTime();
}
public boolean equals(Object o) {
Timezone tz = (Timezone) o;
return tz.timeZone.equals(timeZone);
}
}
Rule: the same object must return the same hashcode every time.
CS61B Fall 2024
3 Buggy Hash
class Timezone {
String timeZone; // "PST", "EST" etc.
boolean dayLight;
String location;
public int currentTime() {
// return current time in time zone
}
public int hashCode() {
return currentTime();
}
public boolean equals(Object o) {
Timezone tz = (Timezone) o;
return tz.timeZone.equals(timeZone);
}
}
Rule: the same object must return the same hashcode every time.
Violation: hashcode() calls currentTime(), which changes depending on the current time.
CS61B Fall 2024
3 Buggy Hash
class Course {
int courseCode;
int yearOffered;
String[] staff;
public int hashCode() {
return yearOffered + courseCode;
}
public boolean equals(Object o) {
Course c = (Course) o;
return c.courseCode == courseCode;
}
}
Rule: two objects that are equal by .equals() must have the same hashcode.
CS61B Fall 2024
3 Buggy Hash
class Course {
int courseCode;
int yearOffered;
String[] staff;
public int hashCode() {
return yearOffered + courseCode;
}
public boolean equals(Object o) {
Course c = (Course) o;
return c.courseCode == courseCode;
}
}
Rule: two objects that are equal by .equals() must have the same hashcode.
Violation: two objects with the same courseCode are equal by .equals(), but might have different hashcodes based on their yearOffered.
CS61B Fall 2024