Java hashcode() and equals()

hashcode() and equals() occupies the first round of interviews in most firms. As the interview proceeds, so does the difficulty level.

Fun part is, if you understand the concept once, all the questions would seem easy.

To the uninitiated, hashcode() and equals() belong to java.lang.Object class. Since all classes extendsObject class, hence all classes inherit the default hashcode() and equals()

Equals

1. By default For not null Objects, equals() method return true if they occupy same place in memory, i.e if the Objects are same. else return false.

2. equals() perform for Object by default, what we call shallow comparison, i.e just that the object is same or not. Sometimes Object can be different but they might have the same data. In such a case, we need to do a deep copy, i.e. compare each member variable to come to a conclusion (by overriding equals)

3. However if equals() is overridden, so should be hashcode(). As two objects that are equal, must return the same hashcode (vice-versa not true). However more on this later.

Hashcode

1. By default, hashcode() varies from on Java implementation to another. Mostly it converts the memory address of the Object into and integer and that becomes the hashcode.

2. By default It is unique for two different Objects.

3. As two objects that are equal, must return the same hashcode. Two unequal objects need not have different hashcode. However it's better to have.

4. Hashcode need to consistent. i.e. no matter how many times we calculate hashcode of a give Object, we should get the same value.

We can override hashcode() and equals() implementation as per our requirement. They are used extensively to store values in HashMap and HashTables.

Memory Leak In Java

An advanced interview question is, "Can we have memory leaks in Java"? More often than not the interviewer wants to know how much you know Garbage Collector in Java.

What all objects are Garbage Collected and when. If we explain on the basis of this, the interviewer (who is just as human as you are) will be satisfied 9 times out of 10.

As to the answer to the question of Memory Leaks, it is a bit contentious issue with no concrete answer.

My take is a follows, Java as a language was designed to not let memory leaks of C creep in. Then daemon Garbage Collector, takes care of memory allocation and deallocation. Once the object is not referenced it will in time be Garbage collected and memory released. So on the face of it Java does not seem to have classic memory leaks of C.

To go deep into this, we first need to know what exactly is memory leak? Well memory leak occurs when some an application allocates (repeatedly) a piece of memory which is not acquired back after it is not longer referenced. Eventually program will throw OutOfMemory Exception.

Java Garbage Collector doe not let this happen. A case can be when memory is allocated faster than it is de-allocated. This is more of an programming issue.

How can we create memory leak in Java? By code bug so that either, memory fills faster than Garbage Collection or fooling Garbage Collection not to collect a piece of memory.

1. Static variable should not allowed to hold large data. They can cause memory leaks.

2. A cache (HashMap) with a badly written hascode() and equals(0 can lead to memory leaks. One can store the value to a Map but can't get it back.

3. Inner Classes referencing Outer class can lead to memory leak.

4. A long running Thread can cause memory leak in Java.

5. A simple code would be to keep on growing a Linked List in Java till OutOfMemory occurs.

Google Protobuf: proto3 enhancements

Proto3 is the new version of Google Protobuf with various enhancements and additions. Let's go over them one by one.

1. Since all fields are optional by default. Hence "optional" keyword has been done away with. If nothing is specified, it will be considered optional. (Protof files just became a tad smaller)

2. Support to group fields are not longer there. Group was just another way of nesting information in messages. But it was inefficient way to do (better way, Nested Messages). Hence is no longer supported.

3. Packed repeated fields were introduced in 2.1.0. Repeated fields needed to be explicitly set packed=true to use this encoding. In proto3, repeated primitive fields have been made packed by default. They have to be set false to be disabled. 

4. Common proto types (timestamp.proto etc) have been added. They can be used after importing. This takes a step towards usable library in protobuf. See below,



5. reserverd keyword introduced. By this, user has the control over reserved field_names and field_numbers. Once declared as reserved, these can't be used anywhere in the message.

Below, the field_numbers and names can't be used anywhere in the message again. Gives us more control.


6. Support for Objective-C and C# introduced in proto3. yay!

7. There are other language specific changes for various languages.

Google Protobuf: Introduction

Google Protobuf has simplified a historically cumbersome process of sending messages from one component of an application to another.

They have made the communication, data storage, platform independent. An object serialized in Java can easily be de-serialized in C++.

Google protobuf aids in managing structured data in a better way. Definitions are easily extensible and simple to use.

.Proto File
Data Definition is created once in a simple format. It is stored as .proto file. These proto files are much simpler to write and manage than xml files that we have been using till now.

This file is compiled and we get generated source code in whatever programming language we want. We can then populate the object using Builder/Getter-Setter, Serialize it and send/store. Later de-serialize it in a different language (or same) and retrieve the information.

 An example below



This .proto can now be compiled and language specific Data Access Classes are created. These classes have auto-generated getter/setter functions for members.

We can declare package name at the top of protofiles, dependency on other protofiles, just like any Java code. Compiler takes care of it all.

More about Google Protobuf below;

Google Protobuf: Historical Significance

With the advent of distributed applications, the messaging between one component to another has become all too prominent. There are a lot of middleware mechanisms to do so. Tibco EMS, ZMQ, etc. I have worked on projects involving a few of such mechanisms. All have their own positives and negatives depending on the problem at hand.

While communicating between components, we need data units to be sent to and fro. What those data units will be? You might have used xml units send across. Remember how cumbersome was to write parsing code at both places. And if the components are written in different languages (Java and C++ say), then it becomes all too messy. Writing receivers at both ends and parsing logic too. Handling exceptions and what not. 

Some might have used json. Programmers of the old might remember Serialization/De-serialization and sending Java as a whole. But what to do when other component is not in Java? Again it becomes messy.

Well Google Protobuf's is one such endeavour to put those issues to an end.

Google provides libraries for various programming languages. A .proto file is created (looks somewhat like json, but not all too much), in which we can define structured data structure of the Object to be move to and fro. The same proto file can be compiled in different languages into class objects. 

These classes can now be used simply, Call setters and populate the object. Send it across. Easy de-serialization at other end, and we get local language specific Object. Call getters and get the data.

Thus a Java Object created Serialized, Sent Across, Received, De-Serialized as C++ Object.

Thus from messy history, this seems like a fresh breeze. Doesn't it?

Multithreaded Quick Sort

Quick sort is a classic example where we can use multiple threads, since execution proceeds on separate paths on separate segments. You can read about classic Quick Sort here.

Quick Sort Steps

1. Select an element as pivot (preferable the last element).

2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)

3. Sort the two segments (Before Pivot and After Pivot) separately

Now check the last step, The two segments can be sorted and processes by 2 separate Threads easily as they don't depend on each other. In turn they can spawn more segments and more threads. For this we can use ThreadPool.

Multi-threaded Quick Sort Steps

1. Select an element as pivot (preferable the last element).

2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)

3. Sort the two segments (Before Pivot and After Pivot) separately via Two Threads

INPUT

2

6

7

5

3

1

8

4

PROCESSING

2

6

7

5

3

1

8

4

2

8

7

5

3

1

4

6

2

1

7

5

3

4

8

6

2

1

3

5

4

7

8

6

2

1

3

4

5

7

8

6

THREAD 1 2 1 3	THREAD 2 5 7 8 6
1 2 3	5 7 6 8 5 6 7 8

FINAL RESULT

1

2

3

4

5

6

7

8

Need for Immutable String in Java

While understanding String Immutability there were some answered questions as to why the designers of Java made String Immutable. We checked that String is immutable but Why so?

Well, it's difficult to go inside the brain of designers of java but based on the usage as of today we can speculate as to what would have been going on in their brain while making java immutable.

1. Easy storage and housekeeping

Strings are used a lot inside a program. A lot of Strings are repeated. For example in a College Database application, same names (Strings) are repeated again and again. Hence it makes better sense to keep a single copy of all strings at a single place (String Pool). Instead of creating new objects again and again. Garbage Collection and Storage of these high volume data becomes easy.

2. Hashcode does not change

Since Strings are immutable, their hascode won't change like other objects. Thus Strings do not calculate hashcode every time we call hashcode function, Hascode us kept cached. Since Strings are used a keys in HashMaps and other such Structures, we save a lot of time but not calculating hashcode every time we need to retrieve an Object.

3. Network Security

All passwords we enter online are strings. Bank details are passed as Strings. If they are mutable, anyone could change them over the network, which would wreak havoc. Same goes with classnames while loading a Class. 

4. Prevents Concurrency Issues

Since Strings are immutable, hence no need to synchronize. Hence no concurrency issues while using Strings.

String immutable in Java: What does it really mean?

This is one of the favourite questions at the fresher level that interviewer asks. Most of the candidates tend to gloss over this. If interviewer tends to go into this deep, most of the candidates tend to falter. At least that if what I have observed having interviewed hundreds of candidates in the past.

We will try and make this article single point of reference for Strings in Java. Hopefully we cover something that might be helpful to you. Read here, for knowing Why It was made Immutable.

Let's try and go in depth on String immutability.

Let's start by Source Code of String.java. I always say that source code is the best resource to learn a language.

How String is Immutable?
This question is self answered by the above code snippet. Member variable data type is final. Hence String Object once created becomes immutable in Java.

How come then we are able to assign same variable, a different value?
Now we are talking. Valid question. Let's check it via code,




So the question stands. What does immutability means?

Well, it can be explained by what happens internally. Variable immutable refers to a memory space which is allocated to "javaonjava. This memory allocation is what we call immutable. Same variable can point to different memory spaces.

String literals are stored separately in a String Pool. Once a String is Created, say "javaonjava". Whenever a new variable needs "javaonjava" String, a new String is not created. The old one is referenced. This is what we mean by immutability. So String Object is not immutable, String itself is immutable.

Compare it with any User defined object. When that object is updated, content is re-written on the same memory space. Hope things are getting clear now.

How to check String is immutable in Java

1. == (equals operator), is the best check.
As we read above StringPool contains single copy of a given String. So if this operator returns true on two string variables, it means they are pointing to same memory and content inside the StringPool






Thus we see, they both point to the same content.

2. No operations modify String





Thus we see neither concat, nor substring modifies the String. They simply create a new String, which is returned as we see below.





In the last example, what happens to "javaonjava" String. Well it remains in the StringPool but unreferenced. If not reused for considerable time, it could be Garbage Collected.

See the diagram below for better understanding

What is a Thread?

Thread relates to running of a program. A Thread is a single chain of execution within a program.

This above start to end path within a program is called a Thread. These steps can do a number of operations. For example if we are adding two numbers input by the user. This thread execution will comprise of the below steps:

1. Asking user for the input 1

2. Asking user for the input 2

3. Adding the two inputs

4. Printing the final sum.

A single program can have multiple executions in parallel. As in multiple threads. For example finding the sum of 10 input numbers.

Two separate threads can take 5 inputs separately and add them up. At the end, the two results can be added together to get the final sum. It's not that work speed increases magically. It's just a illusion, a trick by a magician.

Salient Features of a Thread

1. Thread is like a sub-process. Multiple thread paths can exist within a single process.

2. All threads share the same resources (memory, variables) within a process. This can result into conflict, hence needs to be handles carefully.

3. Apart from shared resources, each thread has its own stack space where it stores variables local to it.

4. One can argue that we can create multiple processes, then why is the need for multiple threads. You can read about it here. Multiple threads v/s Multiple processes.

Quick Sort

QuickSort works on the concept of dividing and proceeding.

An array is divided into two segments, One containing all small elements, other containing all higher elements (from a pivot element). The two segments are in-turn QuickSorted to get the sorted output.

Quick Sort Steps

1. Select an element as pivot (preferable the last element).

2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)

3. Sort the two segments (Before Pivot and After Pivot) separately.

INPUT

2

6

7

5

3

1

8

4

PROCESSING (4 is the pivot)

2

6

7

5

3

1

8

4

2

8

7

5

3

1

4

6

2

1

7

5

3

4

8

6

2

1

3

5

4

7

8

6

2

1

3

4

5

7

8

6

Pivot (4) is in place now. Time to QuickSort separate segments

2 1 3	5 7 8 6
1 2 3	5 7 6 8 5 6 7 8

FINAL RESULT

1

2

3

4

5

6

7

8

Coming Soon: Quick Sort Java Code