Quick Sort

Reading Time: 1 minute

Definition

Quick sort is a very efficient algorithm that leverages the divide-and-conquer principle to sort a data structure. The calculated performance complexity of Quick Sort  as follows;

  1. Best Case: O(n log n),
  2. Average Case: O(n log n),
  3. Worse Case: O(n2), reason: the algorithm will select only one element in each iteration
  4. Space Complexity: O(log n).

Terminology

Furthermore, for starters, it will be a good practice to apprehend the terms in this algorithm;

  • Pivot: A reference element that is used as a line whose left and rights elements are divided. There are a few Quick Sort implementations, whose suggestions vary from picking the Pivot from the beginning, middle, end or randomly,
  • Partition: It is a practice that swaps elements on the left and right ends, while using the Pivot as a reference. By the end of Partitioning, a partition point for the next divided subsets(those will be divided also) is returned,
  • Left Pointer: A pointer or an index value that traverses on the last/low/left subset of the designated array,
  • Right Pointer: A pointer or an index value that traverses on the last/low/right subset of the designated array,

Internal of the Algorithm

In every step, the Quick Sort divides the array to subsets and aims to collect the lower numbers on the left side, the greater numbers  on the right side of the pivot in an ascending format. Let’s look at a glance how the code performs the operation;

  1. Choosing a Pivot,
  2. Beginning the partitioning by swapping the lower elements on the left, greater elements on the right side of the pivot,
  3. Apply partitioning on the left side and later on the right side.

Code

you can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Selection Sort

Reading Time: 1 minute

Description

Selection Sort searches through the list of array to find the smallest item in the unsorted list.
Sorting starts from the left to the right, all the sorted elements reside on the left side of the array.
Selection sort is not a fast algorithm, because it uses nested loops to sort. It comes handy when we sort smaller data sets. It’s worse-case run time complexity is O(n2)

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Big O Notation

Reading Time: 4 minutes

Definition

The Big O Notation is simplified analysis of an algorithm’s efficiency. It is also known as Landau’s Symbol. Big O Notation is used in Computer Science and Mathematics to describe the Asymptotic behavior of functions. Let’s study some of the characteristics;

  1. Big O Notation enlightens about the complexity of a target algorithm for a given input considered as “N”,
  2. Big O Notation is the abstraction of the efficiency in terms of the machine independence. The Algorithm must perform the same way on every operation system and hardware.
  3. Big O Notation does not concern about how much of time that an algorithm takes but how it performs under certain situations.
  4. Big O Notation gives us the “Time” and the “Space” constraints.

In addition to the second characteristic; when we run a program, we will have performance that is how much of time or hardware resource is used, and complexity how the algorithm acts and grows. Note that the Complexity affects the performance, but the other way around is not possible.

Furthermore, there are three types of measurements that I’ll explain and demonstrate those measurements in a different chapter.

Rules

Drop the constants

If you have a function that has a running time of 5N, that is realized as O(n). Because n gets bigger and the 5 is not the consideration anymore,

Observe all inputs

Different inputs and variables have different weights on identifying the notation. If you iterate in two different arrays you get O(a*b). Study the following pseudo code;

method(int[] array1, int[] array2){

For(int a : array1){//O(a)

For(int b : arrayb){//O(b)

System.out.println("match");//O(1)

}

}

}

Drop the low order terms

Certain terms dominate the other terms, in this case we drop the lower term(s). Here is the sequence of the terms. From the right to the left domination gets lower:

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!)

Complexities

Big O Notation can be used to describe the Time Complexity and the Space Complexity of algorithms. Each of these subjects are different terms.

Time Complexity

The Time Complexity corresponds to the amount of time that an Algorithm takes to run. The Time Complexity has the following cases; Best, Average and Worst.

Space Complexity

The Space Complexity describes how much of a space the algorithm allocates in the memory according to the amount of given data.

Cases

In Big O Notation we have three cases:

  1. Best Case,
  2. Average Case,
  3. Worst Case

When algorithms are analyzed, generally “Worst Case is referred. It doesn’t mean that the rest of the cases are less important, but depending on the input, the Worst Case has a weight.

Notations

image courtesy www.bigocheatsheet.com

O(1) Constant

Constant time is a basic statement that has only Constants, in a different way the values that are solid and will not change. Regardless of amount of the data, the code executes the process in the time amount, this can be a variable definition, access in an array or a print out. The simplest examples would go for this:

Int x = (9/2)*12-1;

To find out the Big O Notation of such constants;

1.int a = (9/2)*12-1;//O(1)

2.int b = 100/2; //O(1)

3.int result a+b; //O(1)

System.out.println(result); //O(1)

Total time spent: O(1) + O(1) + O(1) + O(1) = O(1)

4*O(1)

(Constants are dropped)

O(n) Linear

linear time is known as the completion time grows for the given amount of data. A good example to it is the linear search in a loop that iterates through N amount of elements.

1.for(int i=0; i<N; i++){//O(n)

2.System.out.println(i)//O(1)

}

Total time spent: O(n)*O(1)=O(n)

1.int x = 55*3+(10-9); //O(1)

for(int i=0; i<N; i++){//O(n){
3.System.out.println(i)//O(1)

}

Total time spent: O(1) + O(n)*O(1)=O(n)

(Drop low order terms)

O(n2) Quadratic

the time completion of quadratic algorithms is proportional to the square of the given amount of data. Commonly we spot these sorts of algorithms in nested loops. In addition, the more nested loops exist, the square will become cubic O(n3) or more. The good example is the Bubble Sort. Furthermore, such algorithms dramatically hamper the performance if the amount of data increases.

O(2NExponential

Exponential algorithms are those whose performance doubles for every given input. We can basically spot such algorithms in recursive methods of calculations. For the sake of simplicity, I’ll give an example of Fibonacci numbers. As you will see, the method will call itself twice for the given input.

public int fibonacciNumbers(int number) {

  if (number <= 1) {

    return number;

  } else {

    return fibonacciNumbers(number - 1) + fibonacciNumbers(number - 2);

  }

}

O(n!) Factorial

Factorial algorithm that calculates all permutation of a given array is considered as O(n!). The most suitable example of this is the travelling sales man problem with the brute-force search.

O(log n) Logarithmic

The best way to explain logarithmic algorithms is to search in chunks of data by quadratic them and the rest will be assumed as O(n). Since we split it we will gain some time while looking up. The good world example would be the Binary Search Tree for these types of algorithms and they are very efficient, because increasing the amount of data has a minor effect at some point, because the amount of data is halved each time as it is seen with the Binary Search Tree.

O(n log n) Quasi Linear

Quasi linear algorithms are the ones hard to spot. The given values will be compared once. Essentially each comparison will reduce the possible final sorted data structure in half like in O(log n). Furthermore, the number of comparisons that will be performed is equal to log in the factorial of “n”. The comparisons are also equal to n log n this is how O(n log n) algorithms are formed. The mathematical representation as follows;

Sum of comparisons are equal to log n!

Divided comparisons are equal to log n + log(n-1) + … +log(1)//End of comparisons

The outcome is equal to n log n

Examples of Quasi linear complexities are Merge and Heap Sorts.

Further Reading

  1. Big O Cheat Sheet: A great web site that points out the Time and Space complexities of Data Structures and Algorithms.
  2. Stackoverflow Post: While making my research, I found an explanation of John very easy to explain Notations by using the same example.

Binary Tree

Reading Time: 6 minutes

Definition

Binary tree is a non-linear data structure that is composed of two nodes at most. This is how the name “Binary” is formed. However, it is not necessary for the Child Nodes that they have to have two nodes, in fact they can have even zero, we will observe such types in the following chapters.

Furthermore, there is also a Binary Tree implementation called “Binary Search Tree(a.k.a ordered binary tree)” that preserves data in a sorted fashion. From this point on, we will be talking and focusing on Binary Search Tree. Let’s apprehend the characteristics of Binary Search Tree:

  • Given key is compared to the root key, the lower placed on the left and the greater placed on the right,
  • There are two ways of traversals; breadth first and depth first (will be detailed in a sub chapter) compared to one-dimensional arrays and linked lists,
  • Average cases of Positional Access, Search, Insertion and Deletion operations are far faster in tree that is denoted as O(log n) in the Big O time complexity.

Additionally, during my research, I have found a very useful resource that exposes a visualized Binary Search Tree and its operations; https://www.cs.usfca.edu/~galles/visualization/BST.html

Let’s look into the source code how we can create a Binary Tree.

Node.java

public class Node {
    Node leftNode;
    Node rightNode;
    int key;

    Node(int key) {
        this.key = key;
    }
}

BinaryTree.java

public class BinaryTree {

    private Node rootNode;
    private final static int DATA_NOT_AVAILABLE = -1;

//The rest of the code can be obtained on GitHub
}

Glossary and Properties

Before diving into Binary Search Tree, we will need to have a ubiquitous language to apprehend all the terms used in this data structure.

Binary Tree Glossary

Root: The only top most element that has no other nodes above it,

Node: Every member in the tree is known as Node including the root as well,

Parent Node: The node that has two children,

Child Node: A node that is associated with a parent node

Leaf: A leaf is a node that DOES NOT have any children,

Path/Edge: The lines that connect all available nodes,

Sub tree: It is a triangle shape in a tree. Essentially a parent with its two child nodes,

Height: The height of a tree is the number of the edges from the Root node to its deepest leaf.

Some Binary Tree Height Samples as follow:

Binary Tree Glossary Height is three

Binary Tree Glossary height is four

Time and Space Complexities of Binary Tree

Binary Tree Big O Notation Image courtesy: www.bigocheatsheet.com

Types of Binary Trees

Balanced Binary Tree

Balanced and Unbalanced Trees

A Balanced Tree is composed of a balance between the left and the right nodes, but at most one side differs only by one, otherwise it will be considered as an Unbalanced Tree. The operations in a balanced tree are performed in O(log n) notation where n is the node number.
In Addition, Balanced Tree Type has other implementations such as AVL, Red-Black, Weight and Height Balanced Trees etc. It is a good practice to apprehend the definition of the balanced tree.

Unbalanced Binary Tree

Unbalanced Tree

Ordered data sets make up the unbalanced tree. In this type, most of the nodes are located on one side of the tree. In Unbalanced Trees, we cannot favor of fast operations denoted as O(log n), whereas it is actually O(n).

Full Binary Tree

Full Binary Tree

Full Binary Tree is a tree type that consists of a rule that indicates that leaves can have zero or nodes have two children.

L + I + 1

L: Number of leaf nodes,

I: Number of internal nodes

Complete Binary Tree

Complete Binary Tree

Complete Tree is a type of a Binary Tree in which;

  1. Every level must be completely filled,
  2. All leaf elements must lean towards left direction,
  3. Exceptionally the last leaf might have a right child node

Furthermore, Complete Binary Tree is also a Heap

Perfect Binary Tree

Perfect Binary Tree consists of Full and Complete Binary Trees with two conditions of :

  • all nodes have two children,
  • all leaves are on the same level.

In addition, the height of tree is 2h – 1

Tree Traversal

Tree Traversal is the acronym that is known as Tree Search is a type of an action that leads to visiting every single node in the tree and performing selection, insertion, updating and deletion. While going/traversing through there are number of ways to do so namely; Breadth First and Depth First traversals.

Tree Traversal

Breadth First Traversal

Breadth First Tree Traversal

Breadth First Traversal traverses the tree in a level fashion. It internally utilizes a Queue Data Structure, to visit nodes in layers as you can see the illustration. The algorithm of Breadth First Traversal goes;

public void breadthFirstTraversal() {
        if (rootNode == null)
            return;
        System.out.printf("***Breadth First Traversal***\n");
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(rootNode);
        while (!queue.isEmpty()) {
            rootNode = queue.remove();
            System.out.println(rootNode.key);
            if (rootNode.leftNode != null)
                queue.add(rootNode.leftNode);
            if (rootNode.rightNode != null)
                queue.add(rootNode.rightNode);
        }
}

Console Output:

***Breadth First Traversal***
60
55
67
50
57
61
77
45
53

Depth First Traversal

Deep First travel is slightly different and more complicated compared to the Breadth first traversal. Basically, Depth first traversal, the actual focus is not the levels and layers but the Depth itself. Depth first algorithms will visit each node.

In Order Traversal

In Order Traversal

In Order Traversal has the following sequence:

  1. Left Node,
  2. Root Node,
  3. Right Node

Having said that when the traversal begins from the deepest left node. As the second item goes to the root, it is not the top root but the parent root. Then it follows the right node. As you see the above illustration, the algorithm starts in “45” the deepest left node and ends in “77” the highest right node in the tree. Observe the code for traversal:

private void inOrderTraversal(Node node) {

        if (node != null) {

            inOrderTraversal(node.leftNode);

            System.out.println(node.key);

            inOrderTraversal(node.rightNode);

        }

    }

Console Output:

***In Order Traversal***
45
50
53
55
57
60
61
67
77

Pre Order Traversal

Pre Order Traversal

Pre Order Traversal has the following sequence:

  1. Root Node,
  2. Left Node,
  3. Right Node

Having said that when the traversal begins from the root node. As the second item goes to the next left root. Then here the algorithm starts to visit the left and accordingly the right node. As you see the above illustration, the algorithm starts in “60” the root node and ends in “77” the highest right node in the tree. Observe the code for traversal:

private void preOrderTraversal(Node node) {

        if (node != null) {

            System.out.println(node.key);

            preOrderTraversal(node.leftNode);

            preOrderTraversal(node.rightNode);

        }

    }

Console Output:

***Pre Order Traversal***
60
55
50
45
53
57
67
61
77

Post Order Traversal

Post Order Traversal

Post Order Traversal has the following sequence:

  1. Left Node,
  2. Right Node,
  3. Root Node

Having said that when the traversal begins from the deepest left node. As the second item goes to the next right node. Last of all it visits the root node of the children. As you see the above illustration, the algorithm starts in “45” the deepest left node and ends in “60” the root node. Observe the code for traversal:

private void postOrderTraversal(Node node) {

        if (node != null) {

            postOrderTraversal(node.leftNode);

            postOrderTraversal(node.rightNode);

            System.out.println(node.key);

        }

    }

Console Output:

***Post Order Traversal***
45
53
50
57
55
61
77
67
60

Code

The full source code of the Binary Tree and the test cases can be obtained from my public GitHub repository. There will be more utility methods and test cases covering the chapter.

https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures

Creating a Java keystore

Reading Time: 1 minute

create a keystore file

$JAVA_HOME/bin/keytool -genkey -alias tugrulaslan.net -keyalg
RSA -keystore keystore.jks -keysize 2048

keystore1

Generate a certificate signing request (CSR) for an existing Java keystore

$JAVA_HOME/bin/keytool -certreq -alias tugrulaslan.net -keysto
re keystore.jks -file tugrulaslan.net.csr

Import a root or intermediate CA certificate to an existing Java keystore

$JAVA_HOME/bin/keytool -import -trustcacerts -alias root -file
 intermediate.crt -keystore keystore.jks

check certificates in keystore

$JAVA_HOME/bin/keytool -list -v -keystore keystore.jks

Check specific keystore entry using an alias

$JAVA_HOME/bin/keytool -list -v -keystore keystore.jks -alias mydomain

f

Bootstrap a sample blog post details/read more page

Reading Time: 2 minutes

[code]

<!DOCTYPE html>
<html lang=”en”>
<head>
<meta charset=”utf-8″>
<meta http-equiv=”X-UA-Compatible” content=”IE=edge”>
<meta name=”viewport” content=”width=device-width, initial-scale=1″>

<link rel=”stylesheet” href=”https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap-theme.min.css” integrity=”sha384-rHyoN1iRsVXV4nD0JutlnGaslCJuC7uwjduW9SVrLvRYooPp2bWYgmgJQIXwl/Sp” crossorigin=”anonymous”>
<link rel=”stylesheet” href=”https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css” integrity=”sha384-BVYiiSIFeK1dGmJRAkycuHAHRg32OmUcww7on3RYdg4Va+PmSTsz/K68vbdEjh4u” crossorigin=”anonymous”>

<style type=”text/css”>
body {
background: #eee !important;

}
.page-header{
margin-top: 0 !important;
}
.panel-body{
padding-top: 0;
}
.featuredImg{
margin-bottom: 15px;
}
</style>
<!– HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries –>
<!– WARNING: Respond.js doesn’t work if you view the page via file:// –>
<!–[if lt IE 9]>
<script src=”https://oss.maxcdn.com/html5shiv/3.7.3/html5shiv.min.js”></script>
<script src=”https://oss.maxcdn.com/respond/1.4.2/respond.min.js”></script>
<![endif]–>
</head>
<body>

<div class=”container”>
<div class=”row”>
<div class=”col-lg-9″>
<div class=”panel panel-default”>
<div class=”panel-body”>
<div class=”page-header”>
<h3>Page Header Section</h3>
</div>
<img class=”featuredImg” src=”https://cnet3.cbsistatic.com/img/syklRsrXJcU4HS4I9FxtIikHa-k=/770×433/2014/10/13/0ea985b4-9f3a-43d0-9a47-21154c864996/samsung-galaxy-note-4-9024.jpg” width=”100%”>
<p>Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum</p>

<h4>Another heading</h4>

<p>Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum</p>
</div>
</div>
</div>
</div>
</div>

<script src=”https://ajax.googleapis.com/ajax/libs/jquery/1.12.4/jquery.min.js”></script>
<script src=”https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js” integrity=”sha384-Tc5IQib027qvyjSMfHjOMaLkfuWVxZxUPnCJA7l2mCWNIpG9mGCD8wGNIcPD7Txa” crossorigin=”anonymous”></script>
</body>
</html>

[/code]

Bubble Sort

Reading Time: 1 minute

Description

Bubble sort will repeatedly compare and swap adjacent items. If the item on the left is greater, it swaps it with the right item. Basically the greater items are shifted towards the right direction.
Furthermore, the second iteration is stopped because the last items are sorted already we wont go though them again. Furthermore, Bubble Sort is not an efficient sorting algorithm because it uses nested loops. It is only useful for small data sets. It’s worse-case run time complexity is O(n2)

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Adapter Design Pattern in Java

Reading Time: 4 minutes

Description

Adapter Design pattern is listed underneath the Structural patterns. As you understand from the name it is designated to act like an adapter. When you look for this pattern there are different descriptions and examples, however I find the below illustration very clear what the pattern stands for;

Adapter Pattern Illustration

As you study the illustration we see three elements here;

  • Client: Expects to work with the Adaptee, however it is not compatible with the client,
  • Adapter: Wraps the Adaptee’s logic and provides a way to utilize adaptee,
  • Adaptee: An interface or an abstract class that has legacy methods which are not compatible with the client.

The stand point of the pattern is to work the clients with the incompatible interfaces by not chancing or enhancing the methods of the adaptee via the Adapter classes/interfaces. On the other hand also Adapters known as a Wrapper classes. Furthermore, the adapter pattern also practices the Open Close principle in the S.O.L.I.D. in a way that we will not change the existing code unit that will be closed, however we will wrap it by using an adapter. In the real world examples you will see US/Europe electricity socket voltage adapters and all in one memory card, card reader a computer and so on.

Last of all the Adapter Pattern may have some similarities to;

  • Façade Pattern: It provides a simple interface and methods for complex structure,
  • Decorator Pattern: Enhances an interface and adds more functionalities

However, the Adapter pattern does neither of those, but provides a way to the client to work with an incompatible interface by either encapsulating the logic or delegating it. Observe the following to apprehend the topic.

Forming the Pattern

The adapter pattern can be form in two different ways;

Class Adapter

Adapter pattern class adapter uml diagram

The adapter class utilizes Inheritance. The Adapter implement/extends the Adaptee interface/abstract class and overrides the methods,

Object Adapter

adapter pattern object adapter uml diagram

The adapter class utilizes Composition. The adapter has an instance of the Adaptee interface/abstract class and delegates the request to it.

 

Example

For the sake of the simplicity, I’ll emphasis on an old main frame that needs an adapter for classes that work on the Strings with tabs after each enter.

The objects and the roles we have:

  • MainFrameSender: it is the main interface that has we will wrap, it only accepts a String as a parameter
  • MainFrameSenderImpl: it is the implementation of the Main Frame interface,
  • ClassMainFrameSenderAdapter: The adapter class that is formed with the Class Adapter format.The Adapter will convert the Content object into the String that the interface accepts,
  • ObjectMainFrameSenderAdapter: The adapter class that is formed with the ObjectAdapter format. The Adapter will convert the Content object into the String that the interface accepts,
  • Content: This is the Pojo class that will be used to carry the data by the clients,
  • Main: It is used as a client and expose the capabilities of the each adapter implementation.

MainFrameSender.java

public interface MainFrameSender {
    void sendToMainFrame(String content);
}

MainFrameSenderImpl.java

public class MainFrameSenderImpl implements MainFrameSender {
    @Override
    public void sendToMainFrame(String content) {
        System.out.println("sending the content to the mainframe: " + content);
    }
}

ClassMainFrameSenderAdapter.java

public class ClassMainFrameSenderAdapter implements MainFrameSender {

    @Override
    public void sendToMainFrame(String content) {
        System.out.println("sending the content to the mainframe: " + content);
    }

    public void sendToMainFrame(Content content) {
        final StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(content.getMessageId());
        stringBuilder.append("\t");
        stringBuilder.append(content.getHeader());
        stringBuilder.append("\t");
        stringBuilder.append(content.getContent());
        sendToMainFrame(stringBuilder.toString());
    }
}

ObjectMainFrameSenderAdapter.java

public class ObjectMainFrameSenderAdapter {

    private MainFrameSender mainFrameSender = new MainFrameSenderImpl();

    public void sendToMainFrame(Content content) {
        final StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(content.getMessageId());
        stringBuilder.append("\t");
        stringBuilder.append(content.getHeader());
        stringBuilder.append("\t");
        stringBuilder.append(content.getContent());
        mainFrameSender.sendToMainFrame(stringBuilder.toString());
    }
}

Content.java

public final class Content {
    private int messageId;
    private String header;
    private String content;

    public Content(int messageId, String header, String content){
        this.messageId=messageId;
        this.header=header;
        this.content=content;
    }

    public int getMessageId(){
        return messageId;
    }

    public String getHeader(){
        return header;
    }

    public String getContent(){
        return content;
    }

    @Override
    public String toString() {
        return "Content{" +
                "messageId=" + messageId +
                ", header='" + header + '\'' +
                ", content='" + content + '\'' +
                '}';
    }
}

Main.java

public class Main {
    public static void main(String[] args) {
        Content content = new Content((int)Math.random(), "Message 1","this message sent via Class Adapter");
        MainFrameSender classMainFrameSenderAdapter = new ClassMainFrameSenderAdapter();
        ((ClassMainFrameSenderAdapter) classMainFrameSenderAdapter).sendToMainFrame(content);

        Content content2 = new Content((int)Math.random(), "Message 2","this message sent via Object Adapter");
        ObjectMainFrameSenderAdapter objectMainFrameSenderAdapter = new ObjectMainFrameSenderAdapter();
        objectMainFrameSenderAdapter.sendToMainFrame(content2);
    }
}

Console Output

sending the content to the mainframe: 0	Message 1	this message sent via Class Adapter
sending the content to the mainframe: 0	Message 2	this message sent via Object Adapter

Mediator Design Patter in Java

Reading Time: 4 minutes

Definition

The Mediator Pattern falls into the Behavioral Pattern. In simple terms, there is centrally a mediator that handles communication between object in a loosely coupled way, thus objects shall not talk to each other directly. Furthermore, often developers get confused with the Observer pattern, and they seem pretty similar. However, we can break the ultimate difference down like this:

  • Observer Pattern: The objects are not interested in each other, so the relationship is one-to-many, many objects are interested in the state change of one object,
  • Mediator Pattern: The objects are interested to interact with many other objects, so the relation is many to many.

To better understand the deal in the Mediator pattern please study the below illustration;

Before The Mediator Pattern Applied

After The Mediator Pattern Applied

Rules of the Pattern

In this pattern there are two components that we need to create and mind;

Colleagues: These objects are primarily the targets that will not talk to each other directly and have the same base type abstract class or interface that will inherit the same attributes. Furthermore, they will have have the knowledge of the mediator component, which means that each of them will have access an instance to the mediator pattern, rather than having instances to other colleague objects.

Mediator: The centralized component that manages the communication between colleague components.

Example Code Snippet

To better understand the concept, I have developed a simple HR Organization suite. Here the HR is the mediator that knows all the participant Organization units and handles the communication between the Organization components. Then last of all we have the Organization base type that has all the common attributes, Manager and Employee objects are the child classes for the organization, they are separated and have their own functions. The communication is eliminated.

You will see some actions;

  • Registration: A new organization type is created, then it is instantly registered in the HR list,
  • Announcement: HR makes the announcement to all the whole organization regardless of the Organization instance is Manager or Employee,
  • Initiation of the Resignation: Here when an employee resigns, the employee will not talk to the Manager directly, but HR that initiates the process and talks to the Manager,
  • Surprise Party Preparation: After the resignation process is approved by the manager, the HR throws a surprise party without notifying the resigning employee and makes an announcement to the whole Organization.

HR.java

public interface HR {
    void registerOrganization(Organization organization);
    void makeAnnouncementToOrganization(final String message);
    void initiateResignationProcess(Organization employee, Organization manager);
}

HRImplementation.java

import java.util.HashSet;
import java.util.Set;

public class HRImplementation implements HR {
    private final Set<Organization> listOfOrganization = new HashSet<Organization>();

    @Override
    public void registerOrganization(Organization organization) {
        listOfOrganization.add(organization);
    }

    @Override
    public void makeAnnouncementToOrganization(String message) {
        System.out.println("Making announcement to the whole organization");
        for (Organization organization : listOfOrganization) {
            organization.receiveAnnouncement(message);
        }
    }

    @Override
    public void initiateResignationProcess(Organization employee, Organization manager) {
        System.out.println("Employee " + employee.getName() + " would like to resign from the company");
        System.out.println("HR is notifying the manager");
        boolean managerResponse = ((Manager) manager).decideAndFinalizeResignation(employee);
        if (managerResponse) {
            System.out.println(manager.getName() + " has approved " + employee.getName() + "\'s resignation") ;
            prepareSurpriseParty(employee);
        }
    }

    private void prepareSurpriseParty(Organization resigningEmployee) {
        System.out.println("Preparing the surprise party for " + resigningEmployee.getName());
        for (Organization organization : listOfOrganization) {
            if (organization != resigningEmployee)
                organization.receiveAnnouncement("Guys " + resigningEmployee.getName() + " is resigning his position, and you " + organization.getName() + " are invited to his surprise party");
        }
    }
}

Organization.java

public abstract class Organization {
    private final HR hr;
    private final String name;

    public Organization(HR hr, String name) {
        this.hr = hr;
        this.name = name;
        this.hr.registerOrganization(this);
    }

    public void receiveAnnouncement(final String message) {
        System.out.println(this.getClass().getSimpleName() + " " + name + " received the announcement " + message);
    }

    public String getName() {
        return name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Organization that = (Organization) o;

        return name.equals(that.name);
    }

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

Manager.java

public class Manager extends Organization {
    private HR hr;
    private String managerName;

    public Manager(HR hr, String name) {
        super(hr, name);
        this.hr = hr;
        this.managerName = name;
    }

    public boolean decideAndFinalizeResignation(Organization employee) {
        System.out.println("Manager " + managerName + " is considering " + employee.getName() + "\'s resignation");
        return true;
    }
}

Employee.java

public class Employee extends Organization {
    private HR hr;
    private String employeeName;

    public Employee(HR hr, String name) {
        super(hr, name);
        this.hr = hr;
        this.employeeName = name;
    }

    public void giveResignation(Organization manager){
        System.out.println("Employee " + employeeName + " would like to resign");
        hr.initiateResignationProcess(this, manager);
    }
}

Test.java

public class Test {
    public static void main(String[] args) {
        HR hr = new HRImplementation();
        Organization konrad = new Manager(hr, "Konrad");
        Organization tugrul = new Employee(hr, "Tugrul");
        Organization oguz = new Employee(hr, "Oguz");
        Organization altan = new Employee(hr, "Altan");

        hr.makeAnnouncementToOrganization("Welcome guys :)");
        ((Employee) tugrul).giveResignation(konrad);
    }
}

Console Output

Making announcement to the whole organization
Manager Konrad received the announcement Welcome guys 🙂
Employee Altan received the announcement Welcome guys 🙂
Employee Oguz received the announcement Welcome guys 🙂
Employee Tugrul received the announcement Welcome guys 🙂
Employee Tugrul would like to resign
Employee Tugrul would like to resign from the company
HR is notifying the manager
Manager Konrad is considering Tugrul’s resignation
Konrad has approved Tugrul’s resignation
Preparing the surprise party for Tugrul
Manager Konrad received the announcement Guys Tugrul is resigning his position, and you Konrad are invited to his surprise party
Employee Altan received the announcement Guys Tugrul is resigning his position, and you Altan are invited to his surprise party
Employee Oguz received the announcement Guys Tugrul is resigning his position, and you Oguz are invited to his surprise party

In Contemporary Examples

  • java.util.Timer class schedule methods,
  • Java Executor executor method,
  • java.lang.reflect.Method invoke method,
  • JMS and Message Brokers heavily utilizes this pattern along with the Observer Pattern,
  • Spring’s MVC Pattern makes use in the Dispatcher Servlet where mediator handles all the web requests as well as the controller objects.

Java Object equals, hashCode, Hashing Collections and Hash Code Collision

Reading Time: 7 minutes

Introduction

In this blog post I’ll be focusing on something very fundamental and assumed as easy in the concept, but fairly the subject requires more focus and better apprehending. Besides that I am quite sure you’ll learn many interesting related to this topic.

Object equals and hashCode Methods

equals and hashCode methods are shipped with the java.lang.Object class as all the objects in Java extend this class even if you don’t implicitly extend it, the JVM will explicitly do favor for you. So what are these methods and the contracts we need to follow up.

The equals() Method

The method is a Boolean type that in the signature accepts another object that is used to compare the given object with the current object. The equals method can be called by collections explicitly or you ca use to compare two given objects. It is that simple. so after this point we need to follow the contacts while filling in our methodology. Before digging into that, I’d to highlight what happens if we don’t override the method.

The original method relies in the Object class checks only the are equal to each other this mainly falls into similarity of the same memory location.

public boolean equals(Object obj) {
        return (this == obj);
    }

The importance comes in handy when we really need to check “equality”. For instance for a given Person object, the equality means when the names and last names are important. So in this matter we need to override and provide our own implementation of the equals method. Before that we need to meet some contacts;

1. Check whether the given object is null,

2.Check whether the given object is the type of the actual object,

3.Check whether the objects are the same,

4.Then last of all check the attributes whether they are the same or not

Here is a proper way of overriding the method to meet the contract criteria;

@Override
        public boolean equals(Object o) {
            if(o == null) return false;
            if (!(o instanceof Person)) return false;
            if (this == o) return true;
            Person person = (Person) o;

            return getName().equals(person.getName());
        }

The hashCode() Method

The default implementation of the hashCode methods returns the memory location of the object, thus if we are going to work on the hashing collections, we need to provide a proper way of working hash code method. In the below “Hash Code Collision” chapter you will study more of this topic for proper implementations and other options. Furthermore in the “Hashing Collection” chapter you’ll also see why the hashCode method is vital to override.

Here is a proper way of overriding the method to meet the contract criteria;

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

Now I’d like to give out some examples to see in each situation how the code behaves;

1. Proper equals and hash code methods applied:

public class ProperImplementations {
    private static class Person {
        public Person(String name) {
            this.name = name;
        }

        private String name;

        public String getName() {
            return name;
        }

        @Override
        public boolean equals(Object o) {
            if(o == null) return false;
            if (!(o instanceof Person)) return false;
            if (this == o) return true;
            Person person = (Person) o;

            return getName().equals(person.getName());
        }

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

    public static void main(String[] args) {
        Person person = new Person("Tugrul");
        Person person2 = new Person("Oguz");
        Person person3 = new Person("Oguz");
        System.out.println("Person is equal to Person 2: " + person.equals(person2));
        System.out.println("Person 2 is equal to Person 3: " + person2.equals(person3));
        System.out.println("Person hashcode: " + person.hashCode());
        System.out.println("Person 2 hashcode: " + person2.hashCode());
        System.out.println("Person 3 hashcode: " + person3.hashCode());
    }
}

Console Output:

Person is equal to Person 2: false
Person 2 is equal to Person 3: true
Person hashcode: -1778884893
Person 2 hashcode: 2456221
Person 3 hashcode: 2456221

2. Methods are not overridden;

public class NoImplementation {
    private static class Person {
        public Person(String name) {
            this.name = name;
        }

        private String name;
    }

    public static void main(String[] args) {
        Person person = new Person("Tugrul");
        Person person2 = new Person("Oguz");
        Person person3 = new Person("Oguz");
        System.out.println("Person is equal to Person 2: " + person.equals(person2));
        System.out.println("Person 2 is equal to Person 3: " + person2.equals(person3));
        System.out.println("Person is hashcode: " + person.hashCode());
        System.out.println("Person 2 is hashcode: " + person2.hashCode());
        System.out.println("Person 3 is hashcode: " + person3.hashCode());
    }
}

Console Output:

Person is equal to Person 2: false
Person 2 is equal to Person 3: false
Person is hashcode: 1735600054
Person 2 is hashcode: 21685669
Person 3 is hashcode: 2133927002

Hashing Collections

So now let’s dive into one of the Hashing collection to see how we integrate the equals and hashCode methods with a real-life example. In this chapter I’ll be focusing on HashMap and its internals from Java Version 7, because some of hashing collections including HashMap have been enhanced by Oracle since the version 8. You can read this detailed technical article to see the improvements.

So the HashMap works on an Entry object of arrays not as key and value if you decompile it you will see this entry;

transient Entry[] table;

After this point we will need to dig into the Entry object and how the rest of the operations are handled;

static class Entry<K,V> implements Map.Entry<K,V> {
         final K key;
         V value;
         Entry<K,V> next;
         final int hash;
         // the rest is omitted
}

We know now the era of this data structure. Sometimes in the terminology, to make the understanding of the entry easier, the term “bucket” is used. The term corresponds to the Entry itself in this concept. Now it is time to see the mostly used methods to perform insertion and retrieval of objects in HashMap.

The internals of the put operation

public V put(K key, V value) {
       if (key == null)
           return putForNullKey(value);
       int hash = hash(key.hashCode());
       int i = indexFor(hash, table.length);
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }

       modCount++;
       addEntry(hash, key, value, i);
       return null;
   }

Steps:

1.First checked if the key is null
1.1.For the null key: it’s placed in the 0 index,
1.2.If not then the hashCode() method of the Key which is the given object is called to retrieve the hash code,

2.the indexFor() method is then performed to identify the location of the object. It is calculated by the hashCode and the hash table length which is default 16,

3.If the index is empty then the object is inserted at this point. What if the index has another entry? this is the situation called “hash collision”. Then the equals() method is called to check whether the given objects are the same;
3.1. equals() returns true: the old value is replaced by the new value,
3.2. equals() returns false: the new object is linked to the existing object where you see the attribute “next” in the Entry object and the size of the HashMap is increased

The internals of the get operation

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

Steps:

1.First the hash code of the key is calculated and the index is identified,
2.Then we are navigated to the index,
3.If no entry found in the index, the null value is returned,
4.if the entry exists;
4.1.The hashcode is copared,
4.2.1.Hash code matches: the equal methods is called for equality check, if returns true then the value is returned,
4.2.2.Hash code does not match: it will navigate to the next attribute and apply the same pattern in 4.2.1 step recursively, until the hashcode and equal methods return positive values.

Hash Code Collision

A collision happens when distinct keys produce the same hashCode() value that is not unique. In this case, typically the entries will be attached next to each other. Similar to hash code collision, you can also read about this SHA-1 collision security vulnerability found out by professionals. Furthermore, even String class survives with the same situation and will return the same hashCode for the given String values. Observe the below example for the prove;

import java.util.HashMap;

public class HashCodeCollisionExample {
    private static class Person {
        public Person(String name) {
            this.name = name;
        }

        private String name;

        public String getName() {
            return name;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Person)) return false;

            Person person = (Person) o;

            return getName().equals(person.getName());
        }

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

    public static void main(String[] args) {
        Person person = new Person("Aa");
        Person person2 = new Person("BB");
        Person person3 = new Person("BB");
        System.out.println("Person is equal to Person 2: " + person.equals(person2));
        System.out.println("Person 2 is equal to Person 3: " + person2.equals(person3));
        System.out.println("Person hashcode: " + person.hashCode());
        System.out.println("Person 2 hashcode: " + person2.hashCode());
        System.out.println("Person 3 hashcode: " + person3.hashCode());
        HashMap<Person, Person> hashMap = new HashMap<>();
        hashMap.put(person, person);
        hashMap.put(person2, person2);
        hashMap.put(person3, person3);
        hashMap.keySet().stream().forEach(p -> System.out.println(p.getName()));
    }
}

Console Output:

Person is equal to Person 2: false
Person 2 is equal to Person 3: true
Person hashcode: 2112
Person 2 hashcode: 2112
Person 3 hashcode: 2112
Aa
BB

Here come some trivial questions in the sense of Hash Collision;

What do we want with uniqueness? Can we not produce random keys?

By using random keys we will never find the inserted values in the HashMap. We shall mind the fact that, the given hash must be re-calculable  at a later to be found at the given index unlike to Encryption mechanisms e.g. hashing passwords that is one way and we just check the hash for the correction in the simple username and password security mechanisms.

What if we get rid of uniqueness and return the same hash, wouldn’t it work that way?

This approach also meets the contact well, however, first we’ll have benefited from the nature of the Hashing collection, which is we can use a simple List collection and give it a go. Other than that, traversing a LinkedList node each time and having all the expensive operations are also another considerations. HashMap is fast when we have the unique numbers and less linked nodes attached to each other.

If you are stuck with the hash code generation here I listed some options you can benefit of;

  • Objects.hash shipped with Java 7 and can be used even higher versions,
  • Apache Commons Hashcode builder, it also does good job but
  • Google Guava Oracle’s new implementation has also inspired from this library as well,
  • Josh Bloch’s Effective Java in Item 9, he emphasizes on using prime numbers, generally Eclipse and Intellij creates hash code by following Josh’s contract.