Attacking Problems with Java

Substitution ciphers are encryption systems that change each letter in a plaintext to a different one. The Caesar cipher, used by Julius Caesar himself, is perhaps the simplest possible substitution cipher. In it, the key is a number 1 through 25. This number says how many places later in the alphabet the encrypted version of a letter is than the unencrypted version. For example, if the key is 7, then each plaintext letter should be replaced with the letter that comes seven steps later in the alphabet, wrapping around as needed. In this case, the letter A is changed to H, the letter K is changed to R, and the letter V wraps around the end of the alphabet to change into C.

The Caesar cipher is also called a shift cipher since we’re shifting all the letters of the alphabet over by a fixed amount.

Here’s a table showing all the unencrypted alphabet with the encrypted versions of each letter in each row below, when the key is 7.

Thus, the message "CRY HAVOC AND LET SLIP THE DOGS OF WAR" would be encrypted to "JYF OHCVJ HUK SLA ZSPW AOL KVNZ VM DHY". To decrypt a message, we move each letter in the message back by the shift.

The affine cipher takes the Caesar cipher a step further. Instead of simply adding a value to each letter to encrypt it, we multiply each letter by a number and then add a value to it. Thus, the key has two parts, a scalar a and a shift b.

In order to make the math simpler, we first convert the letters A through Z into the numbers 0 through 25. That’s the number that we multiply by a before adding b. Finally, we take the result modulus 26 so that any value larger than 25 maps back to the range 0 to 25. Written in mathematical notation, the encrypted version of a letter whose value is x is (a · x + b) mod 26.

Note that the scalar a must be coprime with the size of your alphabet, in our case 26. Otherwise, different letters in the plaintext will map to the same letters in the ciphertext, making it impossible to decrypt the original message. Two numbers are coprime if they share none of the same prime factors. For an alphabet with length 26, that means that a can only have the values 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, or 25. When a = 1, the affine cipher is simply a Caesar cipher.

Here’s a table showing all the unencrypted alphabet in the first row and the encrypted versions of each letter in the second, with a value of 5 for a and 8 for b.

With this cipher, the message "CRY HAVOC AND LET SLIP THE DOGS OF WAR" would now be encrypted to "SPY RIJAS IVX LCZ ULWF ZRC XAMU AH OIP". To decrypt a message, we first subtract the value b from each letter and then multiply by the multiplicative inverse of a modulus 26. Finding the multiplicative inverse of a number can be done with brute force or some number theory, and we’ll discuss doing so in Section 13.5.

Both the Caesar cipher and the affine cipher are monoalphabetic substitution ciphers, which is a fancy way of saying that a given letter in the plaintext always maps to the same letter in the ciphertext. Although this property makes encryption and decryption simple, it also makes both ciphers susceptible to frequency attacks in which the high frequency of letters like E in English can be used to recover the plaintext from the ciphertext without knowing the key.

The Vigenère cipher is a polyalphabetic substitution cipher, meaning that each letter can be replaced with several different letters, depending on where in the message it occurs. Instead of using numbers, the Vigenère cipher uses a special word or phrase as the key. The values of the letters in this phrase are added to the values of the letters in the plaintext in order to find the ciphertext.

For example, the letter N has value 13 (starting with A = 0). The letter S has value 18. 13 + 18 = 31. As before, we take the result modulus 26 to make the number wrap around if it’s too large. 31 mod 26 = 5. Since the letter F has the value 5, adding the letter N from the plaintext to the letter S from the key yields the letter F for the ciphertext. The table below shows the message "CRY HAVOC AND LET SLIP THE DOGS OF WAR" encrypted with the Vigenère cipher, using a key of "SHAKESPEARE". Note that the key "SHAKESPEARE" is repeated as many times as necessary to provide a letter to add to each letter in the plaintext.

It turns out that repeating the key is what makes the Vigenère cipher vulnerable to attacks. If the key is as long as the message (and is a totally random sequence of letters), the Vigenère cipher becomes what’s called a one-time pad. It’s impossible to attack a one-time pad without knowing the key, but it’s also very inconvenient to use a key as long as the message, particularly when the message itself is long.

The Vigenère cipher dates back to the 16^th century and was believed to be unbreakable for hundreds of years. However, methods that look at the frequency of letters in sophisticated ways were developed in the 19^th century by Friedrich Kasiski and separately by Charles Babbage, a pioneer of computing.

In the previous paragraph, we used the word lambda, which is the letter λ from the Greek alphabet. Because of a theoretical model of computing called the lambda calculus and the Lisp programming language that was influenced by it, the word lambda has come to be associated with methods that are defined on the fly, inside other methods, using the values of local variables when appropriate.

If you recall, we already did something similar in Section 10.4. There, we created whole classes, both local and anonymous, in the middle of a method, even incorporating the values of local variables in one case. Lambda expressions do exactly the same thing, except that the syntax is simpler, and we’re only defining a single method instead of a whole class.

A related concept is a method reference. In functional programming, we often pass methods around as parameters. We can use lambda expressions to create a method on the fly, or we can pass in the method of an existing object. You should always pass in a method reference if the method you want already exists, but creating a lambda is fine if one doesn’t. On the other hand, if you’re writing many different lambda expressions that do essentially the same thing, you might want to create a method so that you can pass a reference to it.

No doubt you’re eager to learn the syntax for lambda expressions and method references that we discuss in the next section, but when is it a good idea to use these tools? A lambda expression is useful when all you require is a single method, not a whole new class with member variables and perhaps many other methods. These situations include:

Anywhere you can use a lambda expression, you can also use a method reference, provided that the method you want already exists.

To make it absolutely clear when we want to focus only on one particular method in an object, Java 8 introduced the idea of a functional interface. A functional interface is an interface that contains exactly one abstract method.

Below is the functional interface ArithmeticOperator, which contains the single method evaluate().

Note the text @FunctionalInterface that appears before the declaration of Operator. The use of the @ sign signals that @FunctionalInterface is an annotation. While we will not discuss annotations deeply in this book, the key idea behind them is that they provide extra information that’s usually not essential to the running of the program. In this case, the @FunctionalInterface annotation gives the extra information to someone reading the code that this interface is a functional interface, intended to be used in situations where we want to pass around an object as if it were only a single evaluate() method that takes two int values and returns a third. The @FunctionalInterface annotation has no effect on the compilation or running of the program except that an interface with this annotation will cause a compiler error if it doesn’t have exactly one abstract method.

The @FunctionalInterface annotation isn’t necessary for functional-style programming in Java. As long as an interface has exactly one abstract method, you can use it as a type for storing or passing lambda expressions and method references. However, it’s always a good idea to mark an interface you write with @FunctionalInterface if that’s how you intend it to be used, both to inform other programmers that it’s a functional interface and to get the extra protection from the compiler if you mistakenly add another abstract method to it.

You can use method reference anywhere with a matching functional interface type. In this case, we have the Operator functional interface that matches methods that take two int values as parameters and return another int value.

Consider the following class that contains a simple method that finds the maximum of two int values.

Since the max() method inside the Max class takes two int values and returns a third, we could store it into a variable with type Operator.

Note that we are using the :: operator here, which lets Java know that we want a reference to the max() method inside the Max class, instead of using . as we would to call the method. In this case, we’re supplying a reference to a static method, but we can use the :: operator to reference an instance method as well.

Consider the following class that allows us to create MaxWithMinimum objects. These objects have a max() method that finds the maximum of two int values, but it also has a minimum value that it will give back as a default if neither of the arguments are bigger than the minimum. A class like this might be useful for situations where a value must always be above a certain threshold.

As before, we can store the max() method into a variable of type Operator, but now we have to put the name of the object, instead of the name of the class, before the :: operator.

This syntax parallels the way that static methods are called with a class name while instance methods are called with an object name.

Like method references, lambda expressions can be used anywhere with a matching functional interface; however, a lambda expression defines a method right where you need it, without the requirement for an existing method in any class.

The syntax rules for lambda expressions are complicated, mostly because parts of them can sometimes be left off to make code shorter and easier to read. Note that lambda expressions always contain an arrow (->) between the parameters and the code that shows what computation the lambda does on the parameters.

A single-line lambda expression that adds two int values together, similar to the add() method in the Calculation class, might look like the following.

In almost all cases, the types for the parameters in lambda expressions can be omitted. The Java compiler uses a process called type inference to determine what the types should be. Thus, the code above could be written in a shorter way.

The parameters a and b still both have type int, but it’s unnecessary to state the type explicitly.

In the two code segments above, we’re storing a lambda expression into a variable with a functional interface type, namely Operation. While doing so is allowed, it’s much more common to use a lambda expression directly, right where we need it. For example, we can recreate the code from the end of the last section using lambda expressions.

Java 8 was released in 2014, and people were excited to use the new functional features it provided. As slick as these features are, they didn’t make it possible to do anything that was impossible before. Even though method references were new, it had already been possible to make interfaces with a single method and then store objects with a matching method into variables with that interface type. While lambda expressions are much less clunky, the same functionality could be achieved with anonymous inner classes.

Java 8 did make some fundamental changes to the JVM, but these changes mostly had to do with memory management. By contrast, the functional programming tools that we’re discussing in this chapter are what some people call syntactic sugar. Syntactic sugar refers to syntax that makes a language easier to program without making deep changes to how the language works. The language simply becomes sweeter to use.

To get a sense of the syntactic sugar that lambda expressions provide, let’s write code that defines a class that implements the Operator interface, creating an evaluate() method that performs multiplication on its two inputs. For the first version of the code, we’ll use an anonymous inner class.

This anonymous inner class approach works for pretty much every version of Java. However, note how much syntax is needed to wrap up the only code that matters, the code that specifies that evaluate() will multiply its two parameters.

From there, we can consider an equivalent version of the code that uses a lambda expression but doesn’t take advantage of all the shortcuts that could be used.

This code is functionally equivalent to the version using an anonymous inner class. Internally, the JVM almost certainly creates a new object with an evaluate() method that implements the Operator interface, but that tedious work is taken care of for you.

Finally, we can consider the slimmest version of the code, which uses all the syntax shortcuts that lambda expressions allow, sugaring the syntax even further.

As you’ve already seen in this chapter, we can usually leave off parameter types in lambda expressions. For single-line expressions, we can also leave off the braces and imply the return statement. Again, this code is functionally equivalent to the first version using an anonymous inner class, but syntactic sugar has allowed us to write it in a more concise, more readable way.

The enhanced for loops we discussed in Section 6.9.1 are also syntactic sugar since they allow a for loop to be written more compactly. Examples of syntactic sugar exist in almost every language. There are tasks that come up so frequently that the developers of the language decided to make a shortcut for those tasks, even though existing syntax could get the job done.

It pays to be aware of syntactic sugar for two reasons. First, you’ll understand a language more deeply when you realize that one piece of syntax is really just a shortcut for another. Second, programmers tend to prefer the sugared version of syntax. Using the syntax that the community prefers allows you to write more idiomatically, in the accepted style. Since programming is about clear communication with both computers and other programmers, adhering to a common style is valuable.

Streams are library code, not part of core Java. Most of the examples below will assume that everything in the java.util and the java.util.stream packages has been imported. To use streams, we first need to turn our list of data into a stream. Consider the following code in which we start with an array of String values.

In this code, words will now contain a stream of String values. The Stream.of() method can also take a comma-separated list of values with any length. Thus, if you didn’t already have an array you wanted to use, you could put a list of values directly into a stream as follows.

We’ll discuss a number of other data structures in Chapter 19. Most of the standard Java data structures in the Java Collections Framework (JCF) contain a stream() method that puts the contents of the data structure into a new stream. Although you might not yet be familiar with the List interface, it’s a useful tool you will use frequently as a Java programmer to store a list of data. The code below shows an example with a List that results in a stream identical to the array examples we’ve already given.

For now, it’s not terribly important to focus on the syntax for creating a stream. What is important is that Java provides a number of easy ways to create streams from existing collections of data.

Streams have a forEach() method that takes a method reference or lambda expression saying what should be done with each element. Using forEach() processes the stream, performing the operation on each element. The forEach() method is a terminal operation, meaning that it’s the last thing that can be done to a stream. Once a terminal operation has been done, the stream can’t be used anymore.

The following code prints out every String in words.

The output for this code is below.

One can argue whether this stream-based approach to printing words is better than using a loop directly. Regardless, it is readable and likely to take a similar amount of time to execute.

There are many terminal operations in the Stream class that will, among other things, determine if one or all elements in the stream match a condition, collect the elements of a stream into another data structure, count the elements in a stream, find an element in the stream that matches a condition, find a maximum or minimum element, or reduce the elements in the stream to an aggregate value like a sum.

Using only a terminal operation doesn’t showcase the flexibility or power of streams. Before performing a single terminal operation, programmers will often apply one or more intermediate operations on a stream. These operations transform the stream by sorting it, removing values, or making a new stream by processing the members of the original stream in some way.

The filter() method is a common intermediate operation that will keep only the elements that meet a condition. In this case, the condition is given by a lambda expression or method reference that returns a boolean. For example, we can first filter our stream by keeping only those String values whose length is 8 or more and then print out whatever’s remaining.

As you can see in the updated output below, we now only print out two words.

We can also apply multiple intermediate operations at once. For example, we can sort the data after filtering it.

As expected, we get the same two words but now in sorted order.

Note the indentation of the code above. When multiple operations are done on a stream, many style guides encourage programmers to indent each operation on a separate line, in order to improve readability.

Intermediate operations can do more than remove or reorder elements from the stream. The map() method creates a new stream by applying a function to elements from the original stream. For example, the following code will transform the stream of words into a stream containing each word concatenated with itself, before printing out this new stream.

The output is each word doubled.

In Section 19.5, we’ll discuss generic types, a way to program data structures with a type variable, allowing, for example, a list class to be designed to hold a specific (but unknown) type that a user can later specify inside angle brackets (< >). For example, ArrayList<String> is a type for a list of String objects, but ArrayList<Wombat> is a type for a list of Wombat objects. Generic types allow a library designer to program a list class a single time that will work with any specific type, combining code reuse with type safety.

Generic types were introduced in Java 5, after the language had made many significant design choices. Unfortunately, some of these design choices meant that primitive types could never be supplied for a generic type variable. Thus, ArrayList<Integer> is allowed, but ArrayList<int> is not. Because the Java 8 Stream API builds heavily on generic types, they had to make specialized streams to accommodate primitive types.

Specifically, you may want (or need) to use IntStream, LongStream, or DoubleStream if you need streams of int, long, or double values. No specialized streams are available for boolean, byte, char, or short.

Instead of using the Stream type to create primitive streams, use the specific primitive stream type.

These streams can be created from existing lists or generated with the iterate() method (and additionally with the range() and rangeClosed() methods for IntStream and LongStream. The following code generates five identical streams.

These streams of primitive values behave exactly like general streams, but they can be more efficient and add a few useful methods like max(), min(), and sum(), which find the maximum value, the minimum value, and the sum of all the elements in the stream, respectively. Note that these methods are terminal operations and so can only be called once per stream. Also, max() and min() return a special optional type that requires a getAsInt() (or similar), since the result could be null if the stream is empty.

In the example above where we create an IntStream with the iterate() method, we give the starting point of 3 followed by a lambda expression to add 1 to the current value in order to get the next value. Without the limit() method, we would have defined an infinite stream, which is allowed.

In fact, infinite streams aren’t necessarily a problem since all streams use lazy evaluation. Laziness is generally considered negative, but it can be an admirable quality in computer science. Lazy evaluation means that a stream doesn’t do computation on an element in the stream until it’s needed. Adding a long sequence of intermediate operations doesn’t mean that those operations will get performed on everything in stream. For example, the findFirst() and findAny() methods are terminal operations that will return only a single element from the stream. When using findFirst(), it will transform the first element of the stream based on intermediate operations, and if the first element matches, it will return that element, without processing others in the stream.

Because of lazy evaluation, no work on an element in a stream is triggered until a terminal operation requires that element. This design means that programmers don’t need to worry too much about efficiency when planning the order of intermediate operations. Consider the following code that generates 100 elements, waits 1,000 milliseconds (one second) for each one, limits the size of the stream to 5 elements, and then prints out each remaining element.

The peek() method is an intermediate operation that allows the programmer to use each element of the stream before the terminal operation, “peeking” at its value. In this case, we’re only using the peek() method to call the Thread.sleep() method to wait for a second, ignoring the value of the element. A quick reading of this code segment might suggest that the program would wait a total of 100 seconds. Instead, it only waits 5, since only the elements that are processed by the terminal operation are processed by peek(). Because the limit() step comes after the peek() step that does the waiting, it seems like all 100 elements should incur a wait of one second, but the order of intermediate operations doesn’t matter in this case.

Lazy evaluation means that programmers can focus on what the intermediate operations should be, instead of their order. The biggest performance gains from lazy evaluation happen when the stream processing stops after finding a single element or when processing only a fraction of the total elements in the stream. Lazy evaluation won’t give any speed improvement when every element in a stream is processed, but it won’t cause any problems, either.

If a programmer is concerned about squeezing every ounce of performance out of a repetitive task, loops will provide more control. Thus, loops could be a better solution when performance really matters. However, lazy evaluation makes streams competitive with loops, without requiring much analysis about the most efficient way to process intermediate operations.

Chapter 14 is where we’ll finally introduce the Java syntax for concurrency using threading, and we don’t want to get ahead of ourselves.

That said, a key problem when creating a thread is specifying what code will be executed. Runnable is a functional interface that contains the abstract method void run(). Because it’s a functional interface, you can create a lambda expression that matches it. Below, the code will do just that, printing out "Threaded world!" when executed.

If you’re hungry for more details about how to use threads to solve problems, head over to the next chapter.

Just as you can use streams to process data sequentially with a single core, you can also use them to process data in parallel with multiple cores. In general, sequential streams can be converted into parallel ones and vice versa.

Consider the following code that creates a parallel stream instead of a sequential one, by calling the parallelStream() method on a list instead of the stream() method.

Just like the sequential stream, this code will print out each word. However, there’s no guarantee when each thread will execute the code that prints out. Thus, a parallel stream might print the words in an unpredictable order. On one execution, the code above might have the following output.

On others, it could be different, even matching the sequential output.

A parallel stream can also process data beyond doing simple output. For example, the following code finds the longest String in the stream, "understand" in this case.

This code works provided that the operation being done in the reduce() call is associative, meaning that it doesn’t matter how the data is divided up before performing the operation. The operations will still be applied in order, but the left half and the right half of the list of numbers might be processed at the same time before the left result is combined with the right result.

This idea mirrors associative operations in math, which can arbitrarily add or remove parentheses without affecting the results. For example, addition is associative, as demonstrated by the equation (5 + 3) + 7 = 15 = 5 + (3 + 7). However, subtraction is not associative, since (5 - 3) - 7 = -5 ≠ 5 - (3 - 7) = 9.

Of course, comparing the lengths of two String values is not very computationally intensive, so using parallel streams here is unlikely to be faster than using sequential streams (or for loops). Nevertheless, there may be some cases where the operations done on each element of data are time-consuming enough that using a parallel stream will be faster. For that to be true, the processor must have multiple cores, and the work that the Stream API is doing behind the scenes to create threads and coordinate them must not take up more time than the savings gained through parallel computation.

Consider the following code that finds the sum of the sines of the numbers from 0 up to (but not including) 1,000,000, using both parallel and sequential streams.

On our test system, the output is as follows.

There’s a small difference between the results because the order in which the numbers were added was different. Consequently, there can be differences in floating-point rounding. These differences will depend on the number of threads created by the system, which is automatically determined by the number of cores.

Depending on a number of different properties of a given system, the parallel stream in this example might take more or less time than the sequential one.

We’ll return to a similar problem in Example 14.10, where we’ll handle the details of thread creation directly instead of using streams. Although parallel streams are a useful, readable tool that can solve this particular problem, they’re not flexible enough to perform all parallel processing tasks.