#3 Remove some dirt from hashing

Hashing 

First of all, we'll figure out what hashing is. Hashing comes out of a word i.e HASH. which means in English chop up, we can imply that change in state 

That's exactly what a hash function do. It takes some value and converts into some other value.

In more specific terms "A hash function is a function which when given a key, generates an address in the table or the map".

To generate an address from a key we need a function i.e Hash Function.

A hash function is used to convert a key into an index. Ideally, a hash function should map each key to a specific and unique index. But in reality that is not possible.

So, we need to be selective in terms of hash function. A hash function  should :

• distribute the index values of inserted objects uniquely.
• calculate the index quickly.
• have minimum collisions.

Collisions 

What collision is ?

In simple terms, a collision is when two things strike together on the same target.

Similarly in programming it means the same with including some technical terms.
In hashing collision means when at particular index we are saving more than one value.
How to deal with that so their are two ways of solving every problem either stop the problem to occur or resolve the problem after it comes
First we try to avoid collisions. This is known as Collision resolution technique
It is the process to find a new location for the same value that a hash function generates

Here are the two most powerful Collision resolution technique:

1. Direct Chaining
2. Open addressing 

Direct Chaining 

If a hash function returns same indexs for two keys than we combine the concept of link list with hash.

We create a lilnk list for every index where hash function retruns the same value for two keys.

for ex: 

hash function is hash(<key>%2)

if key is 1 hash(<key>%2) will return 1

if key is 3 hash(<key>%2) will return 1

Open Addressing 

It is also known as closed hashing. Open Addressing is based on probing 

It can be of two types 

Linear Probing 

Suppose using 'x' key we will get 'p' as the result when 'x' is processed by the hash function. And also after processing 'y' also we will get 'p'. Then for the second key that produces 'p' we will find new index by using Linear Probing.
If we encounter a any value at the same index than we rehash the key to find new index and save the value to the new location.
In linear probing we can use the rehash function to be increased by 1 or 2 any constant. Like if some value exists on index '2' and when we hash another key it will produce as index '2' than we increase the index by 1 and save the value to index 3.

*We can also use a function like if index is occupied we will save at  n*n (where n is the index).This phenomenon is known as quadratic probing.

That finishes up this time next time we will catch up with the Almighty Hash Table.
See yaa pals..

#2 Iterator in JAVA (Classified on Concurrent Modification)

Hello everyone, we are back again with something cool.

Now the moment you read iterators, you say what is so different about that? We know most of you have read about iterators and what they do, how they work and other information

But wait! there's a catch!

As the title itself says 'Classified on basis of Concurrent Modification'. So wasting no more time lets look into iterators on a very different note.

Starting with the very first question "What is Concurrent Modification ?"

1. Concurrent Modification :

As the word describes itself, concurrent modification means performing two different operations on a structure at the same time. Say you have a collection that you want to iterate on but you perform some other operation on the collection while iterating which changed the structure of the collection then we call it concurrent modification. For example while iterating on a array list you add a value (or it can be a remove operation or a update operation) than this would refer to as concurrent modification of the collection.

In a more formal way, If one or more threads are performing operations on a collection such that the structure of the collection is changed by the other thread ( or the same thread) results in concurrent modification.

So we have discussed about concurrent modification and what it means. 

Now this brings to our next question on what is its importance in java ?

2. Effect of Concurrent Modification on Iterators :

This is the most important part of the entire discussion. As we know, we have iterators which are used to iterate over a collection of elements. One specific thing about iterators is that they have two special types ( or properties to be specific). Iterators in java can follow two different patters.

1. Fail Fast

2. Fail Safe (Weekly Consistent)

1. Fail Fast :

By fail fast we mean that the iterator may fail while iterating through the elements.Lets take and example: We are iterating over an arraylist of integer values.Now if we try to modify the contents of the array list using collection methods (say by ArrayList.remove()) then the iterator throws ConcurrentModificationException. Thus as a result of concurrent modification, the iterator fails quickly instead of risking the changes in the structure of the collection which would result in undetermined changes in the future, the iterator throws an exception instantly.

To be very specific about what we are dealing with, here is what Oracle docs say :

  "The fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs."

Thus the fail fast behavior cannot be relied on completely as for example if we are iterating on an array list with improper synchronization methods, we could end up with an corrupted list. The fail fast mechanism will detect the concurrent modification (though it is not guaranteed!) but wont detect the underlying corruption.

2. Fail Safe (Weekly Consistent) :

Weekly consistent simply means that the iterator wont fail while iterating. Strictly speaking the fail safe behavior is exhibited by concurrent Collections implementations i.e. Collections from the java.util.concurrent package implement weekly consistent iterators. Now how do these work ?

Basically a fail safe iterator works by making an copy of the internal data structure (for example the array of the ArrayList) and operates over the copied data structure.Hence the original data structure remains consistent without any changes and this explains why the fail safe iterator doesn't throw a ConcurrentModificationException. Any changes made during the iteration are performed on the copied data structure and hence the original structure remains unaltered.

Though the fail safe iterator does not guarantee that the data being read is the data that is currently present in the original collection.

Oracle docs :

"The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove(), set(), and add()) are not supported. These methods throw UnsupportedOperationException."

That makes it clear that any changes wont be reflected because the iterator doesn't support any element changing operations at the first place.

Fail safe iterators examples are : Implementation in ConcurrentHashMap, CopyOnWriteArrayList etc.

You can read about iterators on the official oracle javadoc.

3. Conclusion:

So finally we can conclude that iterators in java can have two properties. They can fail fast or they can be fail safe.The implementation of the two differ based on weather they allow concurrent modification or not. One can easily test these concepts with simple java programs using a ArrayList for fail fast iterator and ConcurrentHashMap for fail safe iterator.We will provide the code in next revision.

So friends that was our discussion on the types of iterators based on the concurrent modification. Hope you enjoyed reading the post. And yes we will be back again with some really cool stuff.

For any queries please leave a comment below.

Stay Tuned and Keep Learning :)

#1 Difference between JDK,JVM and JRE

What is JDK, JVM and JRE ?

In the world of java everything starts from this one word "The JDK". The power of java platform can be easily explained by the fact that almost 3 billion devices run on java platform. Java has been around for a very long time now and is virtually into everything from computers to ovens which explains why it is the first choice for a developer and also the fact that it has such a huge community support.

Every beginner that aspires to learn java development goes through the very first step of "Installing the Java Development Kit (JDK)".

This brings us to our very first questions  "What is JDK ? "

1 . JAVA DEVELOPMENT KIT (JDK)

The java development kit as it says is a "kit". pretty lame han! 😑

Yes, it is a set of utilities and components that can be used to perform java development.It has all the tools and libraries one would require to develop,test and execute java programs.

Jdk bundles tons of useful stuff and the the most important part is "The runtime environment"(we will come to that later though)

It has utilities ranging from compiler to applet tools. Every java based program or application requires you to install a JDK to function in first place. All you need is to set up a class path to the bin directory of the jdk so that other programs could reference the location of the jdk utilities.

There have been many jdk implementations around from different organizations such as the most popular one called the Oracle JDK or the one on linux called OpenJDK etc. They are pretty much the same and provide set of components which are good enough to run java programs.

If you want to read more about JDK click here.

Now the main catch here is JDK contains an implementation of JVM .

And here comes our next question : "What is a JVM ?"

2 . Java Virtual Machine (JVM)

The Java Virtual Machine is a "specification". Yes you read it correct. There is nothing like JVM as a program that exists physically in form of code. It is an abstract concept and a specification that describes the design of a machine that could run java programs. It is not a physical entity like a software program on a computer.

 The main takeaway here is that java virtual machine is just a specification that tells how to write a software program that could run java programs on a computer. It is written by a community of developers that specify the details about the design of the runtime environment.The vendors can then look into this specification and develop an implementation in the form of code that can run on an actual computer.

Now you must be thinking if JVM is just a specification and not a program then what actually runs a java code on a computer ?

Yes you guessed it right! the JRE 

3 . Java Runtime Environment (JRE)

Jre is the program that is bundled with the java development kit and is the one that provides a runtime environment for the java code (byte code).

The JRE can be defined as an implementation of a JVM and exists physically on a system. It is a software program that follows the entire JVM specification and additionally provides the java libraries.Oracle currently holds the java trademark and provides the java runtime environment with the name HotSpot.

Conclusion

So guys summarizing everything. The jdk is the set of tools that you require on your computer to begin java development. 

This package contains all the utilities and libraries along with the runtime environment. The jvm defines the specifications of this runtime environment on terms of what should be the design and functionalities of the system to run java byte code and finally the jre is the implementation of the jvm specification that is present in the jdk and runs the java byte code.

Hope now you know the difference between the three basic terms about java. So the next you see someone describing jvm and jre as same thing. You can explain them better.😄

Cheers