Gain insights into implementing array-based and linked list data structures, explore advanced structures like skiplists, hashing, and graphs, and learn reusable, template-based collections for efficient data analysis.

java.tar.gz

Java

Java-1

Data structures and algorithms are essential in computer science since they play a crucial role in efficient information retrieval and processing, dealing with files, storing contacts on phones, social networks and web searches.

In this course, you’ll learn about the array-based implementation of various linear data structures, stack, and queues. You’ll also learn about linked list-based implementation. Next, you’ll explore advanced data structures like skiplists and hashing. You’ll learn how to implement a variety of trees and graphs, and data structures related to bits of an integer. Toward the end of the course, you’ll learn the implementation of structures based on external storage.

After completing this course, you’ll be able to create reusable programs with template-based collections that can efficiently analyze how to optimize the storage and retrieval of very large amounts of data. Overall, this course will enhance your productivity and performance as a software developer.

Data Structures with Generic Types in Java

# Task

Here is the code that implements the `addSlow()` method for adding an element `x` to a `LinearHashTable`, which simply stores `x` in the first `null` array entry it finds.

# Solution

The `addSlow()` method uses linear probing to handle collisions by sequentially checking the next available slot until an empty slot is found.

public class Factory < T > {
  Class < T > t;

  public Class < T > type() { // Return the type associated with this factory
    return t;
  }

  // Constructor - creates a factory for creating objects and 
  // arrays of type t(=T)
  // t0
  public Factory(Class < T > t0) {
    t = t0;
  }

  // Allocate a new array of objects of type T.
  // n the size of the array to allocate
  // @return the array allocated
  @SuppressWarnings({
    "unchecked"
  })
  protected T[] newArray(int n) {
    return (T[]) Array.newInstance(t, n);
  }

  public T newInstance() {
    T x;
    try {
      x = t.getDeclaredConstructor().newInstance();
    } catch (Exception e) {
      x = null;
    }
    return x;
  }
}

interface USet < T > extends Iterable < T > {
  public int size();
  public boolean add(T x);
  public T remove(T x);
  public T find(T x);
  public void clear();
}

import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;
import java.lang.reflect.Array;

// An implementation of linear probing.  The hash method used is tabulation hashing.
public class LinearHashTable < T > implements USet < T > {

  protected static final int w = 32;
  protected static final int r = 8;
  Factory < T > f;
  T[] t; // The table
  T del; // Special marker - used to show deleted nodes
  int n; // the size
  int d; // t.length = 2^d
  int q; // number of non-null entries in t

  // nil an object of class T that will never be
  // stored in the table
  @SuppressWarnings("unchecked")
  public LinearHashTable(T nil) {
    this.del = nil;
    f = new Factory < T > ((Class < T > ) nil.getClass());
    d = 10;
    t = f.newArray(1 << d);
  }

  // Resize the backing array to have size 2^d
  // Warning: 2^d should be much bigger than n
  // d
  protected void resize() {
    d = 1;
    while ((1 << d) < 3 * n) d++;
    T[] told = t;
    t = f.newArray(1 << d);
    q = n;
    // insert everything from told
    for (int k = 0; k < told.length; k++) {
      if (told[k] != null && told[k] != del) {
        int i = hash(told[k]);
        while (t[i] != null)
          i = (i == t.length - 1) ? 0 : i + 1;
        t[i] = told[k];
      }
    }
  }
  // Compute and return the hash code of an object x of type T
  protected int hash(T x) {
    int h = x.hashCode();
    return h;
  }
  // Adds an element to the hash table
  public boolean add(T x) {
    if (find(x) != null) return false;
    if (2 * (q + 1) > t.length) resize(); // max 50% occupancy
    int i = hash(x);
    while (t[i] != null && t[i] != del)
      i = (i == t.length - 1) ? 0 : i + 1; // increment i
    if (t[i] == null) q++;
    n++;
    t[i] = x;
    return true;
  }
  // Adds an element to the hash table in a slower but different way
  public boolean addSlow(T x) {
    if (2 * (q + 1) > t.length) resize(); // max 50% occupancy
    int i = hash(x);
    while (t[i] != null) {
        if (t[i] != del && x.equals(t[i])) return false;
        i = (i == t.length - 1) ? 0 : i + 1; // increment i
    }
    t[i] = x;
    n++;
    q++;
    return true;
  }
  // Finds an element in the hash table
  public T find(T x) {
    int i = hash(x);
    while (t[i] != null) {
      if (t[i] != del && x.equals(t[i])) return t[i];
      i = (i == t.length - 1) ? 0 : i + 1; // increment i
    }
    return null;
  }
  // Removes an element from the hash table
  public T remove(T x) {
    int i = hash(x);
    while (t[i] != null) {
      T y = t[i];
      if (y != del && x.equals(y)) {
        t[i] = del;
        n--;
        if (8 * n < t.length) resize(); // min 12.5% occupancy
        return y;
      }
      i = (i == t.length - 1) ? 0 : i + 1; // increment i
    }
    return null;
  }
  // Returns the number of elements in the hash table
  public int size() {
    return n;
  }
  // Clears the hash table
  public void clear() {
    n = 0;
    q = 0;
    d = 1;
    t = f.newArray(1 << d);
  }
  // Returns an iterator over the elements in the hash table
  public Iterator < T > iterator() {
    class IT implements Iterator < T > {
      int i,
      iprev;
      public IT() {
        iprev = -1;
        i = 0;
        while (i < t.length && (t[i] == null || t[i] == del)) i++;
      }
      public boolean hasNext() {
        return i < t.length;
      }
      public T next() {
        T x = t[i];
        iprev = i;
        while (i < t.length && (t[i] == null || t[i] == del)) i++;
        return x;
      }
      public void remove() {
        t[iprev] = del;
        n--;
      }
    };
    return new IT();
  }

  public static void main(String[] args) {
    Random rand = new Random(1);
    LinearHashTable < Integer > lht = new LinearHashTable < Integer > (-1);
    int n = 100;

    System.out.println("Added 100 elements");
    for (int i = 0; i < n; i++) {
        Integer x = rand.nextInt(n);
        boolean rlht = lht.addSlow(x);
    }
    
    System.out.println("Searching");
    for (int i = 0; i < 10; i++) {
        Integer x = rand.nextInt(n);
        boolean rlht = lht.find(x) != null;
        if (rlht == true)
            System.out.println("The value " + x + " is found");
        else
            System.out.println("The value " + x + " is not found");
    }
  }
}

import React from 'react';
import { shallow, configure } from 'enzyme';
import Adapter from 'enzyme-adapter-react-16';

configure({ adapter: new Adapter() });

import HelloWorld from './app';

var TestResult = function() {
    this.succeeded = false;
    this.reason = "";
    this.input = "";
    this.expected_output = "";
    this.actual_output = "";
}

export const executeTests = function() {

  var results = [];

  result = new TestResult();
  result.input = 'HelloWorld Component';
  result.expected_output = "span containing text 'Hello World'"

  let wrapper = shallow(<HelloWorld />);

  // Call your Challenge function here.

  let type = wrapper.type();
  let testSuccessful = true;
  let failureReason;

  if (type !== 'span') {
    testSuccessful = false;
    failureReason = "You need to render exactly one span HTML element";
  } else if (wrapper.props().children != "Hello World") {
     testSuccessful = false;
     failureReason = "You have rendered wrong message in your span element";
  }

  result.actual_output = wrapper.html();

  if (testSuccessful) {
    result.succeeded = true;
    result.reason = "Succeeded"
  } else {
    result.succeeded = false;
    result.reason = failureReason;
  }

  results.push(result);

  return results;
}


React

Dart

GoJS React

Typescript React

Vue.js

# Explanation

Let’s focus on the detailed explanation for the `addSlow()` method:

- **Line 67:** It checks if the current occupancy of the hash table is more than 50% (i.e., if adding a new element would exceed the maximum occupancy). If so, the `resize()` method is called to resize the hash table to accommodate more elements.
- **Line 68:** It computes the hash code for the element `x` using the hash method.
- **Line 69:** It enters a loop that continues as long as there is a non-`null` element at the calculated hash index `i`.
- **Line 70:** It checks if the element at index `i` is not a deleted marker (`del`) and if it is equal to the element being added (`x`). If so, it means that the element already exists in the hash table, and the method returns `false` to indicate that the addition failed.
- **Line 71:** It increments the index `i` by 1, wrapping around to the beginning of the hash table if `i` reaches the end. This handles collision resolution by probing linearly through the hash table to find an empty slot.
- **Line 73:** It assigns the element `x` to the empty slot at index `i` in the hash table.
- **Line 74:** It increments the total number of elements (`n`) in the hash table.
- **Line 75:** It increments the number of non-`null` entries (`q`) in the hash table.
- **Line 76:** It returns `true` to indicate that the addition of the element was successful.

Review the solution that implements the addSlow() method in LinearHashTable.

Overview

Array-Based Lists

Linked Lists

Skiplists

Hash Tables

Binary Trees

Random Binary Search Trees

Scapegoat Trees

Red-Black Trees

Heaps

Sorting Algorithms

Graphs

Data Structures for Integers

External Memory Searching

Wrap Up

Solution: Hash Tables

Task