Linsy's 2-ng blog

EECS281 Notes

Last update:
Reading time: 3 minutes


This is a final review note for EECS281 final exam.

β†’ Hash

std::hash hashes a data structure to size_t.


std::string str = "Hello";
std::size_t str_hash = std::hash<std::string>{}(str);
// Or
std::hash<std::string> str_hasher;
std::size_t str_hash str_hash = str_hasher(str);


How to dedfine hash for a custom struct?


Easy way:

struct CustomType {
    int field1;
    short field2;
    std::string field3;
    // ...

    std::string toString() const {
        return std::to_string(field1) + std::to_string(field2) + field3; // + ...

    size_t hash() const {
        return std::hash<std::string>()(toString());


Cited from

β†’ What do you need to do Hashing?

Let use our favorite Rust as example:

Let’s say we define a custom struct (or enum):

struct Person {
    id: u32,
    name: String,
    phone: u64,

However, to use hashing, you need to implement Hash trait for this struct.

Again, you may want to directly use derive macro:

struct Person {
    id: u32,
    name: String,
    phone: u64,

However, this derivation needs you to have Eq and PartialEq traits.

This is because you need to compare two elements when hashing.

β†’ Collision resolution

Load factor Ξ± = N / M where N are all the keys placed and M is the size of the table.

The last three methods are similar, they are called open addressing. Ξ± < 1 .

β†’ Trees, BST

I believe most students who took ENGR1510J learned this well.

β†’ Structural properties

β†’ BST Property

β†’ AVL


Worst-case search/insert is O ( log ⁑ N ) .