---
marp: true
title: 06 April 2021
theme: default
paginate: true
---
# <!-- fit --> CS 199 EMP

### Hosted by Jackie Chan and Akhila Ashokan

**Topics:** MORE on Linked Lists, Hashing, and Maps 

---

# Resources

Write code on the homepage or any playground on the site!
https://cs125.cs.illinois.edu/

Slides are on the course site!
https://cs199emp.netlify.app/

---

# Review on Linked Lists 

---

![bg 80%](../../pics/linked_list.png)

---

# Review on Linked List Performance 

Remember that Linked List and Array Lists are different implementations of the list data structure. Each has their advantages and disadvantages. 

---

# What is the time complexity for each of the operations given below?

Add (at front)
* ArrayList: O(n)
* Linked List: O(1)

Get and Set
* ArrayList: O(1)
* Linked List: O(n)

Insert (anywhere)
* ArrayList: O(n)
* Linked List: O(n)

---

# Linked List Problem 1 (5 minutes)

Let's start with an easy problem with a simple traversal solution. 

Create a method called `getLength()` which will return the length of the Linked List. What is the time complexity for your solution? Explain why.

Use the Linked List implementation on the next slide.

---

# Linked List Problem 1 Starter Code

```java
public class LinkedList {

  private Item start;

  class Item {
    public int value;
    public Item next;
    
    Item(int setValue, Item setNext) {
      this.value = setValue;
      this.next = setNext;
    }
  }
  
  public void add(int s) {
    Item addition = new Item(s, this.start);
    this.start = addition;
  }
  
  @Override
  public String toString() {
    Item i = this.start;
    String output = "";
    
    while (i != null) {
      output += i.value + " -> ";
      i = i.next;
    }
  
    return output + "null";
  }

}

LinkedList ls = new LinkedList();
ls.add(1);
ls.add(3);
ls.add(4);
System.out.println(ls.toString()); // should print 4 -> 3 -> 1 -> null
System.out.println(ls.getLength()); // should return 3 once getLength() is done
```

---

# Linked List Problem 2 (5 minutes)

Cool. Let's try another one. Create a method called `findIndex()` that will take in an integer argument and return the index of that argument in the Linked List. 
If the item does not exist in the Linked List, you should return -1.

You may use the Linked List implementation given on the previous slide.


```java
LinkedList ls = new LinkedList();
ls.add(1);
ls.add(3);
ls.add(4);
System.out.println(ls.findIndex(1)); // should return 2 once findIndex() is done
System.out.println(ls.findIndex(3)); // should return 1 once findIndex() is done
System.out.println(ls.findIndex(4)); // should return 0 once findIndex() is done
System.out.println(ls.findIndex(5)); // should return -1 once findIndex() is done
```

---

# Hash values, Hash codes, and Digests 

Welcome to the awesome world of crypto! 

Hashing is used to map data into a fixed sized value. Hash code is so awesome that Java has a function that will translate a Java object to a hash code. We can also override the `hashCode()` method to create specific hash codes for classes. 

```java
System.out.println("I love cryptopgraphy!".hashCode());
```

Hash functions should be *uniform* and *deterministic*. 

---

# More on Hashing 

Hashes are used in SOOO many different places: verifying downloads, git, and even bitcoin mining. But hashing is a super tricky concept and it's very difficult to create your own hashing method (at least ones that work well anyway). 

As you can probably tell, I find this stuff fascinating. If you are interested in this area, I would recommend checking out CS461 to get a taste of what this stuff can do. 

---

# Hashing Problem (10 minutes)

Okay. Let's take a stab at this. 

Let's pretend you are a security engineer. Your job is to ensure  the data integrity of the messages sent between users on a email platform. Alice is sending a super secret message to Bob. Another user, Malicious Mallory, is trying to intercept and manipulate the message that's being sent between Alice and Bob. How can we help Bob detect whether the message he receives is legitimate? 

---

# Hashing Problem (5 minutes)

1) Create a class called Email that has these attributes: the sender email, the message, and the receiver email. 

2) Create a constructor for your class and create two identical instances  of Alice's email to Bob (the message can be anything you want). 

3) Use the generic `hashCode()` method to print the value of the hash for both instances of the email. Does it match? 

4) Override the `hashCode()` method using all three attributes of the message. Does the hash code of the two identical messages match?

---

# Jackie and Akhila's Favorite Data Structure: Maps

Maps are just mappings between keys and values. Each key maps to one value. You can think of them like a dictionary (they are called dictionaries in Python actually)

Analogy -  key:word::value:definition 

You might have already seen them in MP 2. If so, great! 

```java
import java.util.Map;
import java.util.HashMap;

Map<String, Integer> map = new HashMap<>();
map.put("here", 0);
System.out.println(map.getOrDefault("heret", 0));
```

---

# Maps Problem (5 minutes)

Create a method called `wordCount` that given an array of strings, returns a `Map<String, Integer>` with a key for each different string, with the value the number of times that string appears in the array.


wordCount(["a", "b", "a", "c", "b"]) → {"a": 2, "b": 2, "c": 1}
wordCount(["c", "b", "a"]) → {"a": 1, "b": 1, "c": 1}
wordCount(["c", "c", "c", "c"]) → {"c": 4}

---

# Yay! You reached the end! 

Today, we looked at more linked lists, learned about hashing, and introduced maps.

Next time, we'll do more with maps and look at exception handling. Good luck on the quiz today! 

---

# Solution Section


---

# Linked List 1 Solution 

```java
public int getLength() {
  int length = 0;
  Item i = this.start;
  while (i != null) {
    length++;
    i = i.next;
  }
  return length;
}
```

Time complexity for this solution: O(n)

---

# Linked List 2 Solution 

```java
public int findIndex(int num) {
  int index = -1;
  Item i = this.start;
  
  while (i != null) {
    index++;
    if (i.value == num) {
      return index;
    }
    i = i.next;
  }
  return -1; 
}
```

---

# Hashing Solution

```java
import java.util.Objects;
public class Email {
  private String senderEmail; 
  private String message; 
  private String receiverEmail; 
  
  public Email(String setSE, String setMessage, String setRE) {
    senderEmail = setSE;
    message = setMessage;
    receiverEmail = setRE;
  }
  
  @Override 
  public int hashCode() {
    return Objects.hash(senderEmail, message, receiverEmail);
  }
}

Email aliceToBob = new Email("alice@illinois.edu", "Hey there ;)", "bob@illinois.edu");
Email aliceToBob2 = new Email("alice@illinois.edu", "Hey there ;)", "bob@illinois.edu");
System.out.println(aliceToBob.hashCode());
System.out.println(aliceToBob2.hashCode());
```

---

# Maps Solution 

```java
public Map<String, Integer> wordCount(String[] strings) {
  HashMap<String, Integer> map = new HashMap<String, Integer>();
  for (String key : strings) {
    if (map.containsKey(key)) {
      int num = map.get(key);
      map.put(key, num + 1);
    } else {
      map.put(key, 1);
    }
  }
  
  return map;
}
```