Linsy's 2-ng blog

EECS281 Notes

Last update:
Publish date:
Reading time: 2 minutes

Tip

This is a final review note for EECS281 final exam.

β†’ Hash

std::hash hashes a data structure to size_t.

Usage:

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);

Think

How to dedfine hash for a custom struct?

Solution

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 https://stackoverflow.com/a/76722434.

β†’ 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:

#[derive(Hash)]
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

Self-balancing.

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