Skip to main content

Section D.11 Exercise Sheet 11

Collections

1. Collections.

Java has a big and well-documented standard library which also contains the so-called Collections.

  1. Read the explanantion for Java Collections.

  2. Figure out on your own which of these collections can be used to solve which task or problem.

  3. Try to implement some of the existing collections like ArrayList and LinkedList yourself.

202207281550

202206241400
Solution.

If you have questions regarding this exercise, please use the forum or ask your tutor directly.

2. Lottery.

On a convention, the organizer wants to arrange a prize lottery. To this end, he creates a .txt file in which he writes the name, address, phone number and the integer score of a competitor (in this order).

Data format:

  Examplename,Examplestreet 42 01337 Examplecity,01234/56789,10
      
  1. The organizer realizes that the evaluation will be difficult with a high number of participants and asks Konrad Klug - apparently an expert for Java Collections - to write a program for this. The program should read the .txt file and store each participant as an object of the class Person. Help Konrad to write the program.

    Hint: First figure out the appropriate collection to store the participants in, e.g. LinkedList and ArrayList could be possibilities.

    Hint 2: To read a file, the following code snippet could be useful:

      BufferedReader br = new BufferedReader(new FileReader("file.txt"));
                

    You can take a look at the various helpful methods a BufferedReader has at BufferedReader.

  2. Now determine the maximum and minimum number of points as well as the average of all participants.

  3. Now sort the items in your collections ascendingly according to the score. Additionally, write a method which prints all participants in this order.

    Hint: It may be helpful to inform yourself about Comparators in Java.

  4. When Konrad Klug shows his friend No Hau his program, she is not as amazed as Konrad had hoped. She points out to Konrad that he should use a PriorityQueue instead to avoid the explicit sorting of items! Adapt the program to use a priority queue instead.

    Hint: Comparators may again be useful.

202207281550

202206241400
Solution.
  1. package root;
    
    import java.io.BufferedReader;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.ArrayList;
    
    public class Main {
      private static ArrayList<Person> participants;
    
      public static void main(String[] args) {
        if (args.length == 1) {
          participants = new ArrayList<Person>();
    
          try {
            BufferedReader br = new BufferedReader(new FileReader(args[0]));
            String line = br.readLine();
    
            while(line != null) {
              parseLine(line);
              line = br.readLine();
            }
            br.close();
          } catch (IOException e) {
            System.out.println("File could not be read!");
          }
    
          // Spot 1
        } else {
          System.out.println("Please specify the file"
          + " to be read as a command-line argument!");
        }
      }
    
      public static void parseLine(String line) {
        String[] person = line.split(",");
        if (person.length < 4) {
          System.out.println("Wrong entry in file");
          return;
        }
        participants.add(new Person(person[0], person[1], person[2],
        Integer.parseInt(person[3])));
      }
    }
    
    package root;
    
    public class Person {
      private String name;
      private String address;
      private String phonenumber;
      private int points;
    
      public Person(String name, String address, String phonenumber, 
          int points) {
        this.name = name;
        this.address = address;
        this.phonenumber = phonenumber;
        this.points = points;
      }
    
      public String getName() {
        return name;
      }
    
      public String getAddress() {
        return address;
      }
    
      public String getPhonenumber() {
        return phonenumber;
      }
    
      public int getPoints() {
        return points;
      }
    
      public String toString() {
        return this.name + " living in " + address +
        " with phone number " + phonenumber + " has scored " + points + 
        " points!";
      }
    }
    
  2. Add the following method to Main.java and call it at spot 1.

    private static void calculateMinMaxAverage() {
      if (participants.size() > 0) {
        Person min = participants.get(0);
        Person max = participants.get(0);
        int totalPoints = 0;
    
        for(Person current : participants) {
          if (current.getPoints() < min.getPoints()) {
            min = current;
          }
          if (current.getPoints() > max.getPoints()) {
            max = current;
          }
          totalPoints += current.getPoints();
        }
    
        double average = (double)totalPoints / participants.size();
    
        System.out.println("Average: "+ average);
        System.out.println("Participant with maximal score: " + 
          max.toString());
        System.out.println("Participant with minimal score: " + 
          min.toString());
      }
    }
    

  3. package root;
    
    import java.util.Comparator;
    
    public class PersonComparator implements Comparator<Person> {
      @Override
      public int compare(Person o1, Person o2) {
        if (o1.getPoints() < o2.getPoints()) {
          return -1;
        }
        if (o1.getPoints() > o2.getPoints()) {
          return 1;
        }
        return 0;
      }
    }
    
    Add the following method to class Main.java and call it instead of the method from part b) at spot 1.
    private static void calculateRankingCollection() {
      Collections.sort(participants, new PersonComparator());
      for (Person current : participants) {
        System.out.println(current.toString());
      }
    }
    

  4. package root;
    
    import java.io.IOException;
    import java.nio.file.Files;
    import java.nio.file.Path;
    import java.nio.file.Paths;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    import java.util.stream.Stream;
    
    public class Main {
      private static PriorityQueue<Person> participants;
      private static Comparator<Person> compar;
    
      public static void main(String[] args) {
        if (args.length == 1) {
          compar = new PersonComparator();
          participants = new PriorityQueue<Person>(compar);
          Path input = Paths.get(args[0]);
    
          try (Stream<String> lines = Files.lines(input)) {
            lines.forEach(s -> parseLine(s));
          } catch (IOException e) {
            System.out.println("File could not be read!");
          }
          
          calculateResult();
        } else {
          System.out.println("Please specify the file"
          + " to be read as a command-line argument!");
        }
      }
    
      public static void parseLine(String line) {
        String[] person = line.split(",");
        if (person.length < 4) {
          System.out.println("Wrong entry in file");
          return;
        }
        participants.add(new Person(person[0], person[1], person[2], Integer.parseInt(person[3])));
      }
    
      private static void calculateResult() {
        while(!participants.isEmpty()) {
          System.out.println(participants.poll().toString());
        }
      }
    }
    
3. Iterables.

Complete the class Range<T>, which represents an interval \([b, e[\) of whole numbers.

  public class Range implements Iterable<Integer> {
    private final int begin, end;

    public Range(int begin, int end) {
        assert begin <= end;
        this.begin = begin;
        this.end   = end;
    }

    @Override
    public Iterator<Integer> iterator() {
        // ...
    }
}
Also implement a remove() method for your iterator. First, look up the default implementation and find out which requirements are imposed on a custom implementation of remove().

202207281550

202206241400
Solution.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Range implements Iterable<Integer> {
    private final int begin, end;

    public Range(int begin, int end) {
        assert begin <= end;
        this.begin = begin;
        this.end = end;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new RangeIterator(begin, end);
    }

    private static final class RangeIterator implements Iterator<Integer> {
        private int position;
        private final int end;

        public RangeIterator(int begin, int end) {
            this.position = begin;
            this.end = end;
        }

        @Override
        public boolean hasNext() {
            return this.position < this.end;
        }

        @Override
        public Integer next() {
            if (!this.hasNext()) {
                throw new NoSuchElementException();
            }

            return this.position++;
        }
    }

    public static void main(String[] args) {
        Range range = new Range(1, 10);

        for (Integer current : range) {
            System.out.println(current);
        }
    }
}
The default implementation of remove() throws UnsupportedOperationException. The method shall only be called once after a call to next() and must otherwise throw an IllegalStateException.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Range implements Iterable<Integer> {
    private final int begin, end;
    private final ArrayList<Integer> removed = new ArrayList<>();

    public Range(int begin, int end) {
        assert begin <= end;
        this.begin = begin;
        this.end = end;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new RangeIterator(begin, end, removed);
    }

    private static final class RangeIterator implements Iterator<Integer> {
        private int position;
        private final int end;

        private boolean removable = false;
        private final ArrayList<Integer> removed;

        public RangeIterator(int begin, int end,
                            ArrayList<Integer> removed) {
            this.position = begin;
            this.end = end;
            this.removed = removed;
        }

        @Override
        public boolean hasNext() {
            if (this.position >= this.end)
                return false;
            int removedIndex = removed.indexOf(position);
            if (removedIndex == -1)
                return true;
            return removed.size() - removedIndex != end - position;
        }

        @Override
        public Integer next() {
            if (!this.hasNext()) {
                throw new NoSuchElementException();
            }
            removable = true;
            while (removed.contains(this.position))
                this.position++;
            return this.position++;
        }

      @Override
        public void remove() {
            if (!this.removable) {
                throw new IllegalStateException();
            }
            removable = false;
            removed.add(position - 1);
            removed.sort(Integer::compareTo);
      }
    }

    public static void main(String[] args) {
        Range range = new Range(1, 10);

        Iterator<Integer> iterator = range.iterator();
        Integer curr;
        while (iterator.hasNext()) {
            curr = iterator.next();
            if (curr % 2 == 0)
                iterator.remove();
        }

        for (Integer current : range) {
            System.out.println(current);
        }
    }
}

4. Farmer John and his Cows.

Konrad Klug was called by his friend Farmer John who needs his help. After his favorite cow Bessie has chewed on the electricity cable, the cow database (a list of all cows) is malfunctioning and a cow seems to be present twice. Konrad has started to solve this issue, but he is stuck. Complete his implementation and help farmer John.

  1. Konrag Klug's idea is to sort the list first and to check for duplicates afterwards. To this end, implement the following method using Collections.sort(). Think about what to change in the cow class to be able to use Collections.sort() correctly.

    public Cow duplicateCow(List<Cow> cows){}
    

  2. No Hau has heard that it is more efficient to use a HashSet and to check during insertion whether an element is already present. To this end, implement the following function by using a HashSet.

    public Cow efficientDuplicateCow(List<Cow> cows){}
    

public class Cow {
    private String name = "";
    private int numberSpots = 0;

    public Cow(String name, int numberSpots) {
        assert name != null;
        this.name = name;
        this.numberSpots = numberSpots;
    }
    
}

202207281550

202206241400
Solution.

public class Cow implements Comparable<Cow>{
    private String name = "";
    private int numberSpots = 0;

    public Cow(String name, int numberSpots) {
        assert name != null;
        this.name = name;
        this.numberSpots = numberSpots;
    }

    @Override
    public boolean equals(Object object) {
        if (this == object)
            return true;
        
        if (!(object instanceof Cow))
            return false;
        
        Cow cow = (Cow) object;
        return (this.name.equals(cow.name) 
            && this.numberSpots == cow.numberSpots );
    }

    @Override
    public int hashCode() {
        return 31 * name.hashCode() + numberSpots;
    }

    @Override
    public int compareTo(Cow cow) {
        if (numberSpots == cow.numberSpots){
            return name.compareTo(cow.name);
        }

        return numberSpots - cow.numberSpots;
    }
}

  1. public Cow duplicateCow(List<Cow> cows) {
        Collections.sort(cows);
        for (int i = 1; i < cows.size(); i++){
            if (cows.get(i).equals(cows.get(i-1))){
                return cows.get(i);
            }
        }
        return null;
    }
    
  2. public Cow efficientDuplicateCow(List<Cow> cows) {
        Set<Cow> set = new HashSet<>();
        for (Cow cow : cows){
            if (set.contains(cow)){
                return cow;
            }
            set.add(cow);
        }
        return null;
    }
    

Hashing

5. HashCode Consistency.

In the following, two classes Fraction and Str are given which are supposed to represent a fraction and a character string, respectively. Implement reasonable hashCode() and equals() methods which adhere to the corresponding Java conventions.

  1. public class Fraction {
        private final int numerator, denominator;
    
        public Fraction(int numerator, int denominator) {
            if (denominator == 0)
                throw new IllegalArgumentException();
            this.numerator = numerator;
            this.denominator = denominator;
        }
    
        public int getNumerator() {
            return numerator;
        }
    
        public int getDenominator() {
            return denominator;
        }
    }
    
  2. public class Str {
        private final byte[] values;
    
        public Str(byte[] values) {
            this.values = values;
        }
    
        @Override
        public String toString() {
            return String.valueOf(values);
        }
    }
    
202207281550

202206241400
Solution.

Please note that the following solutions presented here are only examples and many more correct solutions exist.

  1. public class Fraction {
        private final int numerator, denominator;
    
        public Fraction(int numerator, int denominator) {
            if (denominator == 0)
                throw new IllegalArgumentException();
            this.numerator = numerator;
            this.denominator = denominator;
        }
    
        public int getNumerator() {
            return numerator;
        }
    
        public int getDenominator() {
            return denominator;
        }
    
        @Override
        public int hashCode() {
            // make numerator and denominator unique by computing their
            // greatest common divisor and dividing by it
            int gcd = computeGcd(numerator, denominator);
            return numerator / gcd + (denominator / gcd) * 31;
    
            // Alternative way to do it:
            // It may suffer errors introduced by floating point arithmetic
            // return new Double((double) numerator / denominator).hashCode();
        }
    
        private static int computeGcd(int a, int b) {
            return b == 0 ? a : computeGcd(b, a % b);
        }
    
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Fraction))
                return false;
            Fraction other = (Fraction) obj;
            // this ensures that 3 / 4 and 6 / 8 are equal
            return this.numerator * other.denominator == 
            this.denominator * other.numerator;
        }
    }
    
  2. public final class Str {
        private final byte[] values;
    
        public Str(byte... values) {
            this.values = values;
        }
    
        @Override
        public int hashCode() {
            final int prime = 29;
            int hash = 1;
            // uses the Horner schema
            for (byte b : values) {
                hash = prime * hash + b;
            }
            return hash;
        }
    
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Str other = (Str) obj;
            if (values.length != other.values.length)
                return false;
            for (int i = 0; i < values.length; i++) {
                if (values[i] != other.values[i])
                    return false;
            }
            return true;
        }
    
        @Override
        public String toString() {
            return String.valueOf(values);
        }
    }
    

    The class java.lang.String is final, making it impossible to derive from it. This property was taken over here. Therefore, getClass is used in the equals method for efficiency reasons instead of instanceof, the latter is however not incorrect. Be aware that one has to check for null explicitly when using getClass.

6. Collsion Lists.

Konrad Klug wants to store his favorite scientists in a HashSet. To this end, he created the following class and implemented a hash function. Here, digitSum(int x) calculates the digit sum of x.

public class Scientist {
  private String name;
  private short day, month, year;

  public int hashCode() {
    return digitSum(day) + digitSum(month) + digitSum(year);
  }
}

Name Birthday
Alan Turing 23.6.1912
Gottfried Wilhelm Leibniz 21.6.1646
Harry Nyquist 07.2.1889
Leslie Lamport 07.2.1941
Stephen Cole Kleene 05.1.1909
Edsger Wybe Dijkstra 11.5.1930
Konrad Ernst Otto Zuse 22.6.1910
Carl Adam Petri 12.7.1926
Charles Antony Richard Hoare 11.1.1934

Hash the scientists of the above table into a HashSet of size 5. Use collision lists to resolve collisions.

202207281550

202206241400
Solution.

Name Birthday Hash Code Index
Alan Turing 23.6.1912 24 4
Gottfried Wilhelm Leibniz 21.6.1646 26 1
Harry Nyquist 07.2.1889 35 0
Leslie Lamport 07.2.1941 24 4
Stephen Cole Kleene 05.1.1909 25 0
Edsger Wybe Dijkstra 11.5.1930 20 0
Konrad Ernst Otto Zuse 22.6.1910 21 1
Carl Adam Petri 12.7.1926 28 3
Charles Antony Richard Hoare 11.1.1934 20 0

7. Linear Probing.

Konrad Klug has changed his mind. He now wants to resolve collisions by linear probing.

  1. Hash the scientists from table from the previous into a HashSet of size 9. Use linear probing to resolve collisions.

  2. Erase Leibniz from the HashSet. Afterwards, Konrad wants to check whether Nyquist is contained in the HashSet. What problem occurs and can you solve it?

202207281550

202206241400
Solution.
  1. 0 Nyquist
    1 Kleene
    2 Dijkstra
    3 Zuse
    4 Petri
    5 Hoare
    6 Turing
    7 Lamport
    8 Leibniz
    Name Birthday Digit Sum Index
    Alan Turing 23.6.1912 24 6
    Gottfried Wilhelm Leibniz 21.6.1646 26 8
    Harry Nyquist 07.2.1889 35 8
    Leslie Lamport 07.2.1941 24 6
    Stephen Cole Kleene 05.1.1909 25 7
    Edsger Wybe Dijkstra 11.5.1930 20 2
    Konrad Ernst Otto Zuse 22.6.1910 21 3
    Carl Adam Petri 12.7.1926 28 1
    Charles Antony Richard Hoare 11.1.1934 20 2
  2. If it is only checked whether there is an element at position 8, Nyquist will not be found. The position must be marked in order to know whether there was an element previously. In that case, the search must continue.

8. Quadratic Probing.

Konrad Klug has changed his mind again. He now wants to resolve collisions by quadratic probing after all.

  1. Hash the scientists from the previous exercises into a HashSet of size 9 in the following order:

    Turing Kleene Lamport Nyquist Dijkstra Leibniz Petri Zuse Hoare

    Use quadratic probing to resolve collisions with the function

    \begin{equation*} h'(x,i)= \left( h(x)+\dfrac{i(i+1)}{2} \right) ~{\operatorname{mod}}~ 9\text{.} \end{equation*}
  2. What do you notice?

202207281550

202206241400
Solution.
  1. 0 Lamport
    1 Petri
    2 Dijkstra
    3 Zuse
    4
    5 Leibniz
    6 Turing
    7 Kleene
    8 Nyquist
  2. Hoare cannot be inserted into the free space with index 4 since there is no \(i\) such that \(h'(\texttt{Hoare}, i) = 4\text{.}\)

9. Cuckoo Hashing.

Konrad Klug is amazed by hashing and wants to find more practically relevant hashing methods apart from hashing with linear and quadratic probing. During his research, Konrad learns about Cuckoo Hashing and Robin Hood Hashing, which he tries to apply to self-made examples. Unfortunately, he realizes that he has not understood the theory behind both methods completely. Help him to do so! Look up Cuckoo Hashing and Robin Hood Hashing and make yourself familiar with the concepts.

Consider the following hash table:

  1. Let the following hash functions be given:

    \begin{gather*} h_{1}(x)={(x+1)}^{2}-3\\ h_{2}(x)=2 * x \end{gather*}

    Insert \(2, 7, 11, 1, 8, 15\) in the hash table in this order using cuckoo hashing.

  2. Let the following hash function be given:

    \begin{equation*} h_{1}(x)=2x-1 \end{equation*}

    Insert \(2,7,11,1,8,15\) into the hash table in this order using Robin Hood hashing.

202207281550

202206241400
Solution.
  1. For this solution, we use a variant of cuckoo hashing with two hash tables, one for each hash function. After inserting everything up to 8, the tables look like this:

    If one wants to insert 15, another collision occurs and one attempts to hash 8 into the second array. Here, a collision occurs again which causes 8 to be inserted into the second array and 1 to be inserted in the first array respectively. Since we now have to remove 15 from the first array and insert it into the second array, we try to hash 8 into the first array. Now, 1 must be inserted into the second array again and replaces 15. We have now found a cycle, since we are trying to hash the number we tried to hash originally into the first array. We now double the array size. Afterwards, all values must be hashed again:

  2. After hashing all values and resolving all collisions, the hash table looks as follows:

    The top row shows the entry, the bottom row shows its hash value.

10. Modified Content.

Take a look at the following program:

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<Lorex> watches = new HashSet<Lorex>();
        Lorex r1 = new Lorex("Explorer", 5600, 500);
        Lorex r2 = new Lorex("Pre-Daytona", 12050, 700);

        watches.add(r1);
        watches.add(r2);
        System.out.println(watches.contains(r1));
        System.out.println(watches.contains(r2));

        r1.setPrice(4643);
        r2.setPrice(19040);
        System.out.println(watches.contains(r1));
        System.out.println(watches.contains(r2));
    }
}
public class Lorex {
    String name;
    int price;
    int goldportion;

    public Lorex(String name, int price, int goldportion) {
        this.goldportion = goldportion;
        this.price = preis;
        this.name = name;
     }

     public void setPrice(int price) {
        this.price = price;
     }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Lorex other = (Lorex) obj;
        if (!name.equals(other.name))
            return false;
        return true;
    }
 
    @Override
    public int hashCode() {
        return (goldportion + price) % 10;
    }
}

  1. What is the output of the main method?

  2. Are you surprised by this? What is the problem here?

202207281550

202206241400
Solution.
  1.     System.out.println(watches.contains(r1)); // =>  true
        System.out.println(watches.contains(r2)); // =>  true
    
        System.out.println(watches.contains(r1)); // =>  false
        System.out.println(watches.contains(r2)); // =>  true
    
  2. We know that two objects which are equal according to equals must have the same hash value. However, this is not the case here. By overwriting equals, we define two Lorex objects as equal if they have the same name. Our hash function however only considers the fields goldportion and price which have nothing to do with equals. Therefore, in line 17 of the main method false is printed, although only the price of r1 has changed. A better hash function also considering name looks as follows:

    @Override
    public int hashCode() {
        return name.hashCode();
    }