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

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

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.

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.

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!

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

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

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

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

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