Archive for the ‘Java’ Category:

How Does HashMap Work in Java?

Java is one of the most commonly used programming languages worldwide.

With the Java Virtual Machine (JVM) incorporated on an impressive array of platforms from enterprise mainframes to smartphones, compiled Java applications can run on nearly any device imaginable.

Java developers remain in high demand. Although estimates vary among sources, there is a population of between 9 and 10 million Java developers in the global application development community.

To fellow Java developers, this means there is essentially an unlimited resource of forums, technical expertise, and experience available to answer questions, share code examples, and discuss challenges and solutions related to coding Java applications.

One subject that generates considerable mention among developers is – how does HashMap work in Java?

Quick Navigation
What Is HashMap?
How Does HashMap Work in Java?
Comparison Table
HashMap Storage and Collisions
HashMap Variations
When to Use HashMap in Java
Reasons Not to Use HashMap
Continuing Enhancements for HashMap in Java
Putting Your Knowledge of How HashMap Works in Java to Use

What Is HashMap?

hashmap in java

First, you need a good understanding of what HashMap is in Java.

HashMap is a data structure that allows programs to store and retrieve an object in constant time, assuming you have the key available.

Hash functions come into play in linking the value to th associated key in HashMap. Java’s implementation of HashMap stores data with keys such that each object is stored utilizing a pair that includes the key and value.

How Does HashMap Work in Java?

Comparison Table

[amazon box=”0134685997,0596009208,1260440214,1517671272,0596005687,1985003805″ template=”table”]

Java Logo

Utilizing HashMap in Java is a fairly simple concept, at least at a high level:

Objects are stored utilizing a HashMap method call: put (key,value). The object can subsequently be retrieved with another method call: get(key)

Calling the put hashcode() method of a key object generates the hash function so that the hash map can assign a location in the hash table for the object, which will then store that value with a corresponding key.

Internally, HashMap retains the mapping in a Map.Entry form, as an object that contains both the key and the accompanying value of the object. Using a hashing algorithm, the key/value combination is assigned a “bucket” location in the hash table, which is actually an internal array with the bucket location being an index into the array.

By calling the get() method with the key, HashMap is then able to return the value stored in that location of the table, again using hashing process to locate the key’s location in the array.

HashMap internally calls hashcode() with the key object to determine the actual hash value that is used to locate a bucket for the object. The hash value will also be utilized to locate the bucket for that key when it is retrieved through a get() method.

[amazon link=”0134685997″ title=”Effective Java” /]

[amazon box=”0134685997″]

[amazon link=”0596009208″ title=”Head First Java” /]

[amazon box=”0596009208″]

 

 

 

 

HashMap Storage and Collisions

The issue with the HashMap array is that its size is fixed, so there are only so many buckets available in the table. This makes it conceivable that two objects (pairs of key,value) could have the same hashcode value. This is known as a collision. When this occurs, HashMap will generate a linked list, retaining the original bucket location and creating a “next” node for storing the new entry.

HashMap keys are immutable, so updating the bucket assignment is not an option, which is why linked lists are the solution to collisions.

When a get is used that equates to a bucket that includes a linked list, the method can include the equal() operand, which instructs the method to return the object where the key is equal to the requested key. HashMap will follow the linked list and return the correct value (the object in the list where the key matches).

Coding to allow for a linked list is relatively simple, when you’re aware of this phenomenon:

call keys.equals() method will return the correct node using the linked list to find the key that matches the request.

Since linked lists may result in performance issues due to proceeding through the list, Java 8 included an enhancement that replaces linked lists with a balanced tree structure, once the linked list exceeds a certain defined threshold. This improves worst-case performance problems related to HashMap collisions.

HashMap Variations

HashMap in Java includes a number of methods and subclasses that may be useful in certain applications:

ConcurrentHashMap differs from HashMap in several ways:

  • ConcurrentHashMap is thread-safe, where HashMap is not
  • HashMap is a better performer, partly because it is not thread-safe, allowing multiple uses simultaneously. ConcurrentHashMap can require threads to wait, slowing performance
  • ConcurrentHashMap does not allow nulls for key and values, where HashMap does

LinkedHashMap is a subclass of HashMap that provides a method of maintaining insertion-order. This technique utilizes a doubly-linked list to retain sequence of the objects in the data structure.

When to Use HashMap in Java

There are many good reasons to utilize HashMap in Java applications:

  • It is fast – hash methods for put and gets results in high performance
  • Storage and retrieval by key is required
  • Entry sequence is not an issue – this is not retained with a HashMap data structure
  • Reference by index is not needed

When key reference is needed for your application, HashMap is a great solution.

Reasons Not to Use HashMap

There are a variety of storage or application reasons not to utilize HashMap in Java:

  • When keys are not required or present in a data structure, such as sequential data objects that will not incorporate random (key) retrieval, arrays or linked lists would be more appropriate for your application.
  • If values can change after saving, HashMap is not a reasonable choice, since hash values are immutable.
  • Hash table storage can be costly strictly from a size viewpoint.
  • If you’re only storing a list of objects, an ArrayList or array would be a better choice.
  • Where order is critical, HashMap will simply not meet your requirements.
  • Since HashMap is not synchronous, it is not a good choice when there will be multiple concurrent threads reading and writing to the same map.

As a rule, HashMap in Java is not a good choice when sequence is important or keys are not needed.

[amazon link=”1260440214″ title=”Java: A Beginner’s Guide” /]

[amazon box=”1260440214″]

[amazon link=”1517671272″ title=”The Insiders’ Guide” /]

[amazon box=”1517671272″]

 

 

 

 

Continuing Enhancements for HashMap in Java

Developers can benefit from the continuous improvements in how HashMap works in Java, including updates made in Java Development Kit (JDK) versions 1.7 and 1.8:

Reduction in memory allocation requirements – empty maps formerly consumed memory that was not needed, so improvements have been implemented to limit the unnecessary demands for memory.

Collision handling – to avoid excessive linked lists caused by poor hashing that previously resulted in a performance impact, Java replaced that functionality with a true binary balanced tree that can be interpreted much more efficiently.

Overall performance of HashMap functions has improved on average by 20% in Java 8 as compared with Java 7. Even with poorly-derived hash map keys, HashMap returns the objects for the key specified much more quickly with the most current versions of Java, largely due to the elimination of the adoption of lengthy linked lists (again, where a threshold has been reached for use of a linked list).

Putting Your Knowledge of How HashMap Works in Java to Use

Java Logo

From a practical viewpoint, knowledge of how HashMap works, when to use it in applications, and when it makes more sense to avoid this data structure can play a contributing role in landing a career position as a Java developer. In fact, some of the most frequently asked questions are covered in the preceding material, so use this information to your advantage in responding to interview questions such as:

Q: How does the put() method work with HashMap in Java?

A: Hashcode() is called to generate a location/bucket to store the object, which is a paired value that includes the key and data

Q: What happens when you attempt to store (put) a key that already exists in HashMap?

A: The old value is overridden with the new value – no exception is returned for this condition.

Q: What happens when HashMap creates a second entry in the same bucket?

A: This is a HashMap collision. When it is encountered, HashMap will create a linked list for the duplicate entries, so that subsequent gets with equals() specified will follow the link to return the correct object from the linked list, that matches the key requested. When the linked list exceeds a set threshold, the linked list is converted to a binary balanced tree structure, for better performance.

Q: Does HashMap support duplicate keys?

A: No – duplicate keys are not allowed. If the same key is put() to the table, the value will be replaced.


[amazon link=”0596005687″ title=”Hardcore Java 1st Edition” /]

[amazon box=”0596005687″]

[amazon link=”1985003805″ title=”Java for Beginners 2018″ /]

[amazon box=”1985003805″]

 

 

 

 

With a good grasp of how HashMap works in Java, you’re equipped to make an informed decision on the use of this data structure for your Java application development.

Filed under: Java by admin
No Comments »

Generating Random Numbers with Java Random

Java has a number of functions that can be leveraged by the programmer to create desirable effects. One function, in particular, helps with procedural generation, game development, and a variety of other applications.

Random number generation in Java is a powerful feature that lets the programmer generate random numbers. Objects of the Random Class come with a variety of additional methods that can return a variety of output.

There are many reasons a developer would want to use random number generation in Java. Game development, dice rolling, and procedural generation are all practical applications of the java random number generation.

We will walk you through how to generate random numbers with java random, practical applications of the Random class, technical info, and some common mistakes programmers run into when using this class.

How to Generate Random Numbers with Java Random

To better explain how to generate random numbers in Java, we will break up the information into the following 6 sections:

  • Overview
  • Import
  • Instantiation
  • Constructor
  • Methods
  • Example

OVERVIEW

The Java Random class is a powerful tool that allows Java developers to generate random numbers. These numbers can be returned as regular integers, floats, or doubles. The output that a programmer desires will be based on their specific needs.

It is important to know that Java Random is primarily a class. To use this class, the programmer must create an object to represent an instance of the Java Random class. This created object will have access to the constructor and various methods provided by the Java Random class.

It is also important to note that the Java Random class does not provide true random numbers, but it provides pseudorandom numbers. For example, if two Java Random classes are instantiated with the same seed, then they will both produce the same pseudorandom number.

Because these numbers are produced based on an algorithm, and can be replicated, they are not truly random.

IMPORT

In order to generate random numbers with Java, you must first import the Random class from the package java.util. The code for importing the Random class is as follows:

  • import java.util.Random

This will import the Random class and make it available for use.

Instantiation

After you import the Random class, you must then instantiate the class with a valid constructor. In order to instantiate the Random class, you must create a Random object.

To do this, you can write the following code under your public static void main method:

  • Random randomNum = new Random();

This code will instantiate an instance of the Random class in the Java Object randomNum. Any time you want to use the Random class, you can call its methods through randomNum.

CONSTRUCTOR

There are two different formats in which the Java Random class can be instantiated. These formats are defined by the constructor, the code that goes into the parenthesis when we instantiate the Random class.

  • Random randomNum = new Random(constructor)

There two constructors that exist for the Random class are as follows:

  • Random()
  • Random(long seed)

The first constructor, Random() simply creates a new random number generator.

On the other hand, the second constructor, Random(long seed), generates a new random number generator based on a long seed. A long seed is a number with the datatype long. When you seed a random number generator, you should receive the same random numbers.

This may sound confusing, but the same numbers are generated because seeded random numbers are generated by a pseudorandom number generator. These generators use algorithms to generate sequences of numbers. If you use the same seed in two different Random classes, you should receive the same random numbers.

METHODS

The methods provided by the Random class is where the random number generation actually happens. We will cover the following common number generation methods:

  • nextInt()
  • nextFloat()
  • nextDouble()

The nextInt() function returns a pseudorandom number that will exist as an integer object type. Integer values are common, making this function particularly useful if you are primarily dealing with integer values.

The method nextInt() can also take a parameter that limits how high the value of the integer returned can be. For example, say you have a Random class instantiated as randomNumGen. The method call randomNumGen.nextInt(10) would return an int value in-between the value of 0 and 9.

The value you set is exclusive, meaning it won’t actually be a number included in potential integers returned. If you wanted a random int generated between 1 and 10, you would have to write randomNumGen.nextInt(11).

The nextFloat() method returns a float value between 0.0 and 1.0. This method is useful for generating precise numbers that can be manipulated in a variety of fashions.

The nextDouble() method returns a double value between 0.0 and 1.0. This method is useful if you want to generate a decimal value of up to 15 to 16 points. Double values are more precise than float values.

Example

two women looking at the code at laptop

Image via Pexels

Now that you understand how the Random class works, is instantiated, constructed, and how its methods are called, you should be able to follow how the random number generation works in application.

In the following code, we detail a simple program that uses the Random class and the nextInt() method.

import java.util.Scanner;

import java.util.Random;

class RandomNumberGenerator

{

public static void main(String[] args){

int maxRange;

//create a scanner to output print

Scanner sc = new Scanner(system.in);

//create a random number generator

Random randNumGen = new Random();

System.out.printlin(“Enter a maximum range: ”);

maxRange = sc.nextInt();

for(int i = 0; i < 9; i++ ){

System.out.println(randNumGen.nextInt(maxRange));

}

}

}

When you run this code, you will be prompted to enter a random number with a maximum range. After entering the number, you will receive 10 outputted numbers from the random number generator.

Practical Applications of the Random Number Generator

gray laptop computer showing html codes

Image via Pexels

The Java random function has a number of useful practical applications. The following applications of the explode function help make it a powerful tool for programmers:

  • Simple RPG Critical Hit Mechanic
  • Dice Rolling
  • Procedural Generation

Simple RPG Critical Hit Mechanic

The Java random number generator is an excellent tool to use for creating simple RPG combat. RPG combat is heavily based on chance influenced by numbers. One specific RPG modifier, critical hit chance, is the chance that a player has to do critical damage.

You can use the random number generator to generate a number in a range from 0 – 100. If your character has a 50% critical chance on their attacks, then you can use the random number generator to simulate this.

If you roll a number that is between the values of 0 and 50, then you score the critical hit, if your number is between 51 and 100 then you don’t score the critical hit. You can practice different critical hit thresholds, and use the random number generator to model.

Dice Rolling

You could use the random number generator to simulate a dice roll. You could simulate a simple 6 sided die for simple games. You could also simulate a d20 die which you could use to simulate dice roles for roleplaying games.

Procedural Generation

Procedural Generation is a technique in which portions of a world are generated based on a set of specifications. This technique relies heavily on algorithms and random number generation. For example, you could use a random number generator to load in different gameplay levels for a player.

You could also use Procedural Generation to create different item names, stats, and locations. Items are procedurally generated in this fashion in games like Diablo III and Destiny 2.

Technical Information

One of the most important elements to remember about random number generation with Java is that the random number generator is not truly random. It is based on a linear congruential formula that relies on a 48-bit seed to generate random values.

Common Mistakes

There are a few key mistakes that programmers tend to make when using the random numbers class in Java. One of the first mistakes is believing that the numbers generated by Java random are truly random.

One of the most common mistakes programmers have is that they simply cannot use the Random class. You must remember to import the Random class when you want to use it in an instance. If you don’t include the Random class in your java file, then you won’t have access to it.

Generating Random Numbers with Java Is Easy

Generating random numbers with Java is a relatively straightforward process. The Java Random class is powerful and has a number of real-world practical applications.

If you have an interest in roleplaying games, we recommend you create your own dice rolling program to use with a role-playing board game. You could even create new types of dice simulations with the Java Random class.

 

 

Featured image source: Pexels

 

Filed under: Java, Programming by admin
No Comments »

Simple Guide to Understanding the Java Queue Interface

Has Java taken over the world of technology for applications?

Perhaps not, but with a population of between 8-10 million Java developers worldwide, the language certainly owns more than a fair share of the market.

Portability is a major factor in Java’s popularity. You can develop powerful applications with the Java Development Kit (JDK) for any device that supports the Java Virtual Machine (JVM) environment – which includes a population of devices now numbering in the billions.

In fact, Java applications are running on everything from enterprise mainframes to laptop computers. They are abundant on smartphones and tablets, and even found powering smart devices such as televisions and home appliances.

With all the functionality Java offers developers, one function that is commonly utilized is the Java Queue Interface. It’s important to understand the purpose and proper use of Java’s queueing process, to use it effectively in your applications.

What Is the Java Queue Interface?


A queue is a collection of data elements that are waiting to be processed. You experience this phenomenon almost daily:

  • Waiting in line at the supermarket
  • Lining up at a fast-food drive-thru window
  • Waiting for your turn to ride at an amusement park

Queues are essentially a first-in, first-out (FIFO) method of handling data and transactions. You process the next element in line and remove it, while adding new elements at the end of the queue.

Java implements this same concept in the creation and processing of data with a FIFO methodology in managing data through the Java queue interface.

This simple guide to understanding the Java Queue Interface will provide insight into how the queues are created and used in application design and execution.

Types of Java Queues

 

The Java.util package provides multiple types (or classes) of queues for use in your applications, each with its own set of characteristics and functionality. The most commonly-used classes are:

PriorityQueue – based on the heap data structure, priority queue elements are ordered depending on the order that you specified when the queue is constructed.

You can explicitly define ordering, or utilize the natural ordering of the elements.

With the Priority Queue, the queue can be ordered as you define in its construction, but the queue will still be accessed front to back with respect to its ordering.

LinkedList Queue – utilizes typical FIFO ordering for queue operations

ArrayBlockingQueue – this is an array where the first and last elements in the queue or array are considered to be adjacent, making the structure logically circular. Indexes are incremented for the head and tail of the array as elements are added or removed. 

As a queue, elements do not need to be shifted when the head of the queue is removed, making this queue class a better choice than an array.

ArrayBlockingQueue has a predefined capacity that you specify when constructing this class of queue.

Neither Priority or Linked List queues provide a thread-safe implementation, such that use of Java queue interfaces must take this attribute into account when utilizing these classes in applications.

Java supports the use of a data structure by multiple concurrent programs, known as multi-threaded applications. This can present challenges for data integrity, where multiple threads access, insert, or remove data at the same time.

Applications are referred to as thread-safe when multiple threads can safely access the data structures at the same time without risk of data corruption, such as one thread removing data as another thread attempts to update the same element.

Queue types that fit the requirement for thread-safe operation of Java queue implementation are blocking queues such as PriorityBlockingQueue and ArrayBlockingQueue.  

Java Queue Characteristics


Using the Java queue interface in your applications, you should understand the basic rules and characteristics of queue data structures:

  • Queues are generally utilized to insert elements at the end of the queue and remove from the head of the structure (FIFO – remember your supermarket line).
  • Queues in the java.utl.concurrent package are bounded queues
  • Java queues support all Collection interface methods (more on that later)
  • Blocking queues provide thread-safe implementations
  • Queues in the java.utl package are unbounded queues
  • Queues only support insert at the tail and removal at the head (exception is Deques, which support removal and insert at both ends)

Adding an element to the end of a queue is referred to as an Enqueue operation. Removing an element is termed a Dequeue.

Java Methods for Processing Queues

Since Java queue implementations are a Collection subtype, they support a full scope of methods for processing queue elements:

  • add() – insert elements at the end of the queue (or in the order specified, in the case of priority queue)
  • offer() – adds an element to the end of the queue, returning a Boolean value to verify whether or not the insert was successful
  • peek() – allows you to view the head element in the queue. The element is not removed. If the queue is empty, a null value is returned
  • push() – adds an element to the head of the queue
  • pop() – returns the first element from the head and removes it
  • element() – very similar to the action of the peek method, except when the queue is empty, the NoSuchElementException is thrown.
  • poll() – returns the head element in the queue, removing it. An empty queue results in a null value
  • remove() – returns and removes the head element as poll does, but returns the NoSuchElementException for an empty queue

When implementing a Deque interface, methods available include:

  • addFirst – insert an element at the head of the queue
  • removeFirst – return and remove the head of the queue
  • addLast – insert an element at the end of the queue
  • removeLast – return and remove the last element in the queue
  • getFirst – retrieve the first element in the queue
  • getLast – retrieve the last element in the queue
  • offerFirst – adds an element to the front of the queue with Boolean response
  • offerLast – adds an element to the tail of the queue with Boolean response

It’s important to note the difference in the use of the peek method which will retrieve the next element in the queue, without removing the element, as opposed to the poll method, which retrieves the same element, but also removes it.

Other significant differences between methods are simply the exception conditions that are returned from the method, such as:

add() and offer() – both add or enqueue the element to the queue, but where an unsuccessful operation will return an exception from add, the same result from offer will return Boolean false.

Similar differences exist between other methods, as with remove and poll, or peek and element.

You can utilize iteration to process all elements in a Java queue easily and efficiently. There are several options for using iteration with a Java queue:

  • Iterate the queue utilizing iterator()
  • Utilize the Java8 forEach() method
  • Iterate over the queue combining the use of iterator() and Java8 forEachRemaining() method
  • Iterate over a queue with a forEach loop

Iteration sequence will be the same as the queue insertion order. If you need to iterate from the end of the queue to the front, simply use the descendingIterator function to traverse the queue in reverse order.

Special Purpose Java Queues

coding using Java Queue

Image via Pixabay

There are additional classes of queues that can be utilized for their specific characteristics:

Transfer Queue – this is a blocking queue that you can use when you want the application to wait after adding an element to the queue until another thread has retrieved that element. This is an unbounded queue.

Deque – pronounced “deck”, this interface can be implemented as a double-ended queue, where elements can be inserted or, retrieved, or removed at either end of the queue.

LinkedBlockingDeque class provides concurrent queue processing that includes methods:

  • takeFirst() to retrieve the first element in the queue
  • takeLast() to retrieve the last element in the queue

These methods will wait until the requested element is available, then retrieves and removes that element.

Comparing Use of Java Queues

 

via GIPHY
 

Determining the Java queue interface that is best for your application is generally based on your processing requirements and the data elements to be processed.

PriorityQueue – is your best choice when there is an inherent value attribute that calls for ordering the elements in that sequence.

Keep in mind that this implementation has performance implications due to the additional ordering of elements.

This applies to all methods including peek, enqueue, and dequeue.

ArrayDeque – a good general-use implementation, with good performance characteristics. This is a good go-to default when there are no implicit justifications for using other classes.

LinkedList – when there are requirements to remove elements within the interior of the queue, this class would provide that capability.

Due to the movement generated by this mode of processing, performance will not be up to the ArrayDeque level.

If your application does require functionality such as removing an element while iterating, LinkedList will still be a good choice.

More About the Java Queue Interface

via GIPHY

There is a wealth of information on the web, along with coding examples for implementing Java queues in your applications. Oracle Java Docs is an excellent resource for information on all things Java, including the use of Java queue interfaces.

Featured Image via Pixabay

Filed under: Java, Programming by admin
No Comments »

What Is An Insertion Sort Algorithm – Its Basic Definition

If you need to get a good understanding of what an insertion sort algorithm is, the best way to start is with a basic definition of what an algorithm is.

Quick Navigation

Types of Sorting
Insertion Sort Explained
Variations of an Insertion Sort
Insertion Sort Algorithm Characteristics/Caveats
Why Would You Use (or Not Use) an Insertion Sort Algorithm?
When to Use Insertion Sort
When Not to Use an Insertion Sort Algorithm
Making the Best Choice for Your Sorting Algorithms

An algorithm in its purest sense is just a formula or method for solving a problem. Even a simple task may include an algorithm by utilizing a standard process for arriving at a solution. This could include a variety of types of problems, and their associated resolutions:

  • Manual tasks such as how to select the best grocery products

  • Solutions to mathematic problems

  • Computer system processes that solve business problems

Modern computer applications are where insertion sort algorithms enter the picture. In computer science and mathematics, an algorithm is a defined specification that eases the burden of solving even complex problems.

By formalizing a process or function as a proven algorithm, programmers and scientists can reuse code and formulas to solve business and mathematical problems more efficiently.

Computer algorithms are essentially program logic that receives input values and produces consistent, reliable results as output. Algorithms can be applied for automated and consistent reasoning, performing calculations, and yes – sorting.

Types of Sorting

algorithms

There are multiple methodologies and algorithms for conducting computer sorting:

Select Columns Layout

  • Insertion sort

  • Bucket sort

  • Bubble sort

  • Selection sort

  • QuickSort

  • Counting sort

  • Merge sort

  • Radix sort

  • and others

Even within those variations in processing, and the applicable uses for each, there are additional classifications such as recursive insertion sort, binary insertion sort, recursive merge sort, and so on.

Insertion Sort Explained

So just what is an insertion sort algorithm?

Insertion sort algorithms work much in the same way as you would in sorting a deck of cards. Assume someone gives you stack of playing cards, already in order (or even a single card). Then they give you another card, asking you to place it in the proper sequence in the deck. You will scan through the deck you have, then insert the new card in its place.

Next, you’re given another card, with the same request – put in the deck – in sequence. With many iterations of cards passed to you, the process is repeated. This is essentially the process in working with an insertion sort algorithm.

For each iteration, processing is required to shift the array to insert the new entry, which can be an important factor in utilizing an insertion sort when large arrays or data sets are anticipated. In effect, the insertion sort algorithm proceeds in this manner:

  • Select the first element (since it is the first one, it is already in place, and no shifting is necessary)

  • Pick the next entry from the input array

  • Compare the value against the sorted list

  • Shift all elements higher than the new entry to the right

  • Insert the new entry

  • Repeat the process until the entire input set is complete, resulting in a sorted output set

This provides a reasonably straight-forward process, yet also reveals how the algorithm can result in considerable processing, when the input set is composed of extremely large arrays.

Variations of an Insertion Sort

pencils

Within the realm of insertion sort processing, there are additional variations:

Binary insertion sort - binary insertion sort can be used to reduce the actual number of comparisons over a normal insertion sort. By utilizing a binary search function to insert an element in the proper position of the output set, less processing is required. Normal insertion sort will require multiple iterations for comparison, depending on the size of the input array. In a worst case of large arrays, the binary insertion sort can have significant performance advantages.

Recursive insertion sort–insertion sort algorithms can also be written recursively, although this could have a negative impact on performance. Recursion can simplify coding of the algorithm, but can increase processing requirements.

Insertion sort methodology is more commonly implemented in a non-recursive manner.

Insertion Sort Algorithm Characteristics/Caveats

One factor of sorting algorithms is the attribute of being termed stable or unstable. This refers to the occurrence of equal values in array elements, and whether the sequence of those elements will be retained in the same order as originally encountered in the output set. Insertion sort algorithms are stable by their very nature.

Divide and conquer – algorithms that implement a divide and conquer methodology process data elements utilizing a somewhat more complex approach:

  • Divide – separate the data to be processed into multiple smaller sets of data

  • Conquer – recursively process the subsets of data to execute the algorithm separately

  • Combine – generate the resulting output set through combining the subsets

As divide and conquer algorithms require multiple steps, they are recursive in their processing methodology. Where large sets of data are involved, this type of algorithm can provide an advantage in run times (time complexity).

Insertion sort is not a divide and conquer algorithm, processing elements in a single pass.

Why Would You Use (or Not Use) an Insertion Sort Algorithm?

With the many variations of sort algorithms, why would you decide you use the insertion sort algorithm for any particular problem?

When to Use Insertion Sort

Utilizing an insertion sort algorithm can be an effective solution under certain conditions:

  • Input sets are relatively limited in size

  • Input sets are partially sorted, which increases the efficiency of the algorithm, through the requirement for fewer iterations

  • Space is a consideration – insertion sort requires only a single new memory space, reducing space complexity

  • Stability is an important factor – insertion sort is a stable algorithm, making it an effective choice when that is important for your output set

  • For managing online content, where your application receives one element at a time, insertion sort is a great choice due to its performance in handling such small volumes

Benefits of the insertion sort algorithm include its low overhead and simplicity. When a pre-sorted or partially-sorted input set is expected or known, performance of the insertion sort algorithm can be significantly better than many alternatives, including divide and conquer algorithms such as merge sort, heap sort, even QuickSort.

When Not to Use an Insertion Sort Algorithm

Bracelet

In many instances, the size of the input set to your sort algorithm is unpredictable, or you may even be aware that the volume of data will be large. In such use cases, insertion sort will not be a good choice to solve your sort requirements.

With average and worst-case scenarios (refer to Big O Notation later in this article), alternatives such as merge sort and heap sort will provide better performance.

Insertion sort is not your best choice when concerned with:

  • Large data volumes – insertion sort performance suffers with large input sets

  • Space is not an issue – divide and conquer algorithms will have a higher space complexity, but if that is not an issue, there are better options than insertion sort

  • Stability is not required – for many implementations, stability in the output is not a requirement, allowing the use of non-stable algorithmsthat offer better performance

  • If the input array is unsorted or reverse-sorted, insertion sort will not result in good performance

  • Optimizing processor use – larger data volumes will result in more CPU cycles when implementing an insertion sort algorithm over a divide and conquer solution

Making the Best Choice for Your Sorting Algorithms

Mathematicians and computer scientists have developed a set of guidelines termed Big O Notation, which provides guidelines for the efficiency of different sorting algorithms based on critical factors:

  • Efficiency in run times (time complexity)

  • Space requirements (space complexity)

Binary insertion sort

These algorithm variations have even been compiled into a “cheat sheet” that provides a quick reference to these factors, including performance in best, average, and worst case scenarios.For an insertion sort algorithm, worst case conditions occur when the input set is in reverse order, with best case being where the input set is already sorted.

Additional information, including tutorials on Big O Notation can be found on YouTube and on multiple websites.

It pays to do a little research before making your final choice of sort algorithm solutions. There are divide and conquer algorithms that determine the size of the input set first, and automatically switch to another alternative such as selection sort or insertion sort to process small arrays more efficiently.

Sorting algorithms that are right for your application will depend on the volume of data to be sorted, the condition of the data itself (duplicate values, pre-sorting, etc.), space requirements, and even the programming language in use (not all sorting techniques are supported by every language).

Filed under: Java by admin
No Comments »

What Is A Merge Sort Algorithm And How It Is Used

A primary function of every computer system is to organize data for effective use in analysis, reporting, or presentation purposes. You certainly cannot expect to logically make sense of data that is presented in a random sequence, and make judgements or decisions based on the information.

Quick Navigation

Sorting Efficiently with a Merge Sort Algorithm
What is a Divide and Conquer Algorithm?
Merge Sort Variations
Pros and Cons of a Merge Sort Algorithm
Pros for Merge Sort
Cons ofa Merge Sort Algorithm
Factors for Choosing the Best Sort Algorithm
Sorting Efficiently with a Merge Sort Algorithm
What is a Divide and Conquer Algorithm?
Merge Sort Variations
Pros and Cons of a Merge Sort Algorithm
Pros for Merge Sort
Cons ofa Merge Sort Algorithm
Factors for Choosing the Best Sort Algorithm

To solve that problem, computer programmers and mathematicians have created a variety of sorting algorithms that transform non-sequenced data into elements that are sorted into sets of records that provide information in a meaningful manner for business or scientific use.

In today’s sophisticated computer systems that commonly utilize extremely high data volumes for intelligent analysis – referred to as “big data”, efficient sorting techniques are more critical than ever before.

A merge sort algorithm is one of the more commonly-used and powerful solutions for sorting data structures and data content quickly and efficiently.

Sorting Efficiently with a Merge Sort Algorithm

colorful drinks

There are many options available to computer application developers for sorting sets of data to generate organized output.

Selection of the algorithm to be utilized is to some extent dependent on the language being utilized (ex: C++ “sort()” function can select a different algorithm depending on the array presented for sorting. Its native algorithm is the Introsort function, a blend of heapsort, insertion sort, and quicksort methodology. Depending on the depth of recursion of the array, quicksort or heap sort may be performed. For extremely small arrays, the high performance of insertion sort algorithm will be selected.

When executing a sort function in Python, a combination of insertion sort and merge sort will be used, known as Timsort.

A merge sort algorithm will sort an array into the desired sequence quickly and efficiently, utilizing a divide and conquer methodology. As with many sort algorithms, with a merge sort algorithm the array test will detect the size of the array, and if the size is 0 or 1, consider the data sorted with no processing required.

What is a Divide and Conquer Algorithm?

But what is a merge sort algorithm, and what makes it different from other sorting techniques?

Merge sort is just one of several divide and conquer algorithms that accomplishes its functions in a multi-step process:

  • Divide the array intotwo equal smaller arrays for processing efficiently

This is a simple process of dividing the array size by 2 to determine the midpoint, and creating the two subsets

  • Solve the sequencing of each subarray individually – conquer the problem

This is also a straight-forward process involving recursive calls for each subarray to execute the sort process

  • Combine the sorted subarrays back into the complete original array, now in sequence – this is the merge function that gives the algorithm its name, and requires heavy comparison processing to create the final result set

This divide, conquer, combine process can be performed much more efficiently than other methods such as insertion sort algorithm, which can take a considerable amount of processing time when arrays exceed more than minimal depth.

Array depth is one of the most important elements in determining the sort algorithm that will perform most efficiently when implemented in your solution. Other considerations include space requirements, memory available, and overall performance.

Since a merge sort algorithm will generate additional arrays in memory while processing the input set (divide), space is an important consideration in using merge sort for large arrays. Your trade-off is in performance – time complexity is a major advantage in using a divide and conquer algorithm like merge sort. Since these algorithms create subarrays as part of their basic functions, they are recursive in execution.

Factors for consideration in sort algorithm selection are available on websites for your comparison and decision-making purposes.

Merge Sort Variations

Variations

There are multiple variations or implementations of merge sort algorithms, providing options and flexibility in your choice of sorting methodology:

3-way merge sort

In a 3-way merge sort, instead of sub-setting the input array into two subarrays, three equally-sized separate arrays are created, sorted, then merged. Although the time complexity would seem to be reduced due to the smaller arrays being sorted, the increased number of comparisons required in the merge operation will raise the time complexity during that phase.

Bottom-up Implementation

Bottom-up processing utilizes indices and two buffers to iteratively merge sub-lists between the buffers to sort elements into the sorted array. The result is a non-recursive merge sort, contrary to the typical recursive nature of other merge sort variations.

Polyphase Merge Sort

This variation of a bottom-up merge sort is geared for external data sources where multiple files are being sorted, often including data stored on a hard drive or even a tape device. This includes data sets that will be uneven or unknown in their array sizes, being external input to the algorithm. Due to that criteria, polyphase merge sorts are not stable in nature.

Natural Merge

Similar to the processing of a bottom-up merge, natural merge further examines any existing sorted elements (naturally-occurring sequenced data), and takes advantage to move these elements in a single pass to the result set. In a perfect case, the array will be found to be in sequence, resulting in a single pass to create the solution. Even in a partially-sequenced array, the impact can be improved performance though fewer passes to solve the problem.

Oscillating Merge

Do you ever deal with data from tape drives, especially those that can read backwards? Oscillating merge sort algorithm was designed with that technology in mind. This variation of merge sort intersperses the input data with the merge process, rather than reading the entire set of data before merging can begin.

Pros and Cons of a Merge Sort Algorithm

Not all sort algorithms are created equal – in fact, there are significant differences that will impact your decision on the best sort algorithm for solving your problem.

Pros

  • Merge sort utilizes additional space over the original array to create its subsets of data to solve the problem and create sorted output.

  • A merge sort algorithm will process large arrays with reduced time complexity over many other options, notably an insertion sort algorithm.

  • Where stability is an important factor for your application, merge sort is a viable choice, since it is a stable algorithm. Stability means that where values being sorted are equal in multiple elements, the resulting output will retain the original sequence of those elements.

​

Cons

  • Space restrictions –since additional space is required to create the subsets of data for divide and conquer algorithms, you need to have space available to utilize this sort method.

  • Small arrays – where very small arrays will be sorted, other non-recursive, single-pass algorithms such as insertion sort may be more efficient.

​

Since the merge step makes an additional copy of the array to accomplish its work, extra space is required. While some algorithms such as insertion sort and selection sort do their work “in place” and are therefore preferred where space is at a premium, merge sort is not an in-place algorithm.

There is an exception to the requirement for a merge sort algorithm’s need for additional space to process – use of a linked list. Due to the nature of how linked lists reside in memory, no additional space is required for a merge sort with linked lists.

Factors for Choosing the Best Sort Algorithm

organization

Now that you’re comfortable with the concept of what a merge sort algorithm is, your dilemma may be what sort algorithm to utilize in your application. Big O Notation is a representation of how algorithms will perform, based on primary factors:

  • Time Complexity

  • Space Complexity

  • Array Size

Considering those factors plus any special requirements you have in your problem (such as stability issues mentioned earlier), you can make the decision on the algorithm that will perform best for your data and meet your application performance goals.

Where space is not a major consideration, there are additional sort algorithms to be explored for potentially improving your application performance and efficiency:

  • QuickSort

  • Heap Sort

  • Bucket Sort

  • Bubble Sort

There are additional sort algorithms available for your applications, each with their own pros and cons. Some are more useful when used with certain programming languages or may be more useful for website applications (such as insertion sort algorithms).

Utilizing sort selection tools and Big O Notation guidelines can help you determine the best sort algorithm for your implementation.

Keywords:What is a merge sort algorithm, merge sort

Filed under: Java by admin
No Comments »

Java Interview Questions

The Top 21 Most Common Java Interview Questions

It pays to know of the one most popular programming languages.

In 2016, Oracle noted Java was used by approximately 9 million developers and running on 7 billion devices worldwide. That’s an exponential growth curve, considering it’s only been public for less than 25 years.

Java was born in Santa Clara, California as part of the Silicon Valley boom in the early 1990s. Java was developed at Sun Microsystems to boost the abilities and effectiveness of C++ language.

It was released to the public in 1995 and quickly gained popularity. Java was designed to run independent of platform. Any device that has Java Runtime Environment (JRE), a lightweight application, can run a Java program. This provided developers a “write once, run anywhere” programming language. It significantly reduced the coding and resources necessary to write a program for multiple platforms.

Java was eventually acquired by Oracle as part of its larger purchase of Sun in January 2010.

Of all the programming languages available, how did Java surpass them and become such a hot commodity in today’s job market?

Why Java is One of the Top Programming Languages

Java is undeniably popular. It consistently leads the TIOBE index – a measure of the popularity of programming languages created by the TIOBE Company in the Netherlands – with the most recent rating of 17.8%. That’s up 5.4% from last year.

Below are just a few of the reasons why Java has become so popular:

  • The Five Principles: Sun Microsystems wanted to build on the C++ language and create something that more people could use. They explained this goal as Five Principles which guided the initial design and subsequent iterations of the language.
  • Open Source: Anyone can create Java applications at no cost. A massive community of users has grown around Java, providing additional resources and expertise for developers. Message boards and forums provide free publicity and ongoing training for users. With a growing library of functions and classes, Java is an easy choice when looking to deliver results quickly.
  • Concurrent: Programmers can process data in parallel, meaning multiple programs can run at the same time. This increases the efficiency and power of programs written in Java.
  • Wide Range of Uses: Java is used in banking and financial services, IT, and stock market trades. It provides a solid foundation for websites. Java is critical for applications in a wide range of industries.
  • Big-Name Users: Companies and programs that use Java include Minecraft, Adobe Creative, Google, and more.

Thanks to the high demand for this skill set, average salary range has been reported at $93,570 for a Java programmer. It’s no wonder Java developers and programmers are in such demand.

Knowing Java is only part of what you need to earn a position with one of the top companies in the world. Let’s look closely at the interview process and the questions you can expect.

Interview Questions

The interview is designed to give the business a better understanding of who you will be as an employee and how you will work as part of a team. The questions will also cover specific technical skills you’ll need.

Problem-Solving Questions

Managers want problem solvers in every layer of employment – from entry level to top management. The hiring manager will test your personal skills by asking about missed deadlines, office conflicts, loss of data, and overlapping deadlines. They are not only looking to see that you know how to fix a problem but want to know how you can deliver solutions when problems occur. Below are a few of the questions you should prepare to answer:

  • What is a challenge you’ve faced in the past and how did you handle it?
  • Have you ever had a project that was behind schedule? How did you manage the work and meet the deadline?
  • Tell me about a time where you faced a problem you couldn’t solve. How did you handle it?
  • Describe a creative solution you used to handle a work-related problem?
  • What kind of troubleshooting process do you use in your work?

Leadership-Based Questions

Do you wait for a solution or do you lead by proactively finding the answer? Everyone has their comfort zone with leadership. Hiring managers want to know where you will fit within the company. They may ask questions about your proudest accomplishment, what do you want to gain from this job, or if would you speak up if you knew something in the process was wrong.

  • In your opinion, what makes a great leader?
  • What experience do you have that will help you in this position?
  • What work-related responsibilities have you had in the past?
  • If you knew a manager was wrong, how would you handle it?
  • What is your greatest strength and greatest weakness?

Java Interview Questions

Java is considered one of the easier programming languages, especially when compared to languages like C, C++, Fortran, and Pascal. Even so, there are core skills and expertise every developer and programmer working in Java should have mastered.

The technical questions in the interview will be designed to not only determine your comfort and competence in Java programming, but also check that you have the core skills for the position. Before the interview, make sure to review the job listing to identify what those skills are. Take time to brush up on those skills and have answers ready for any specific technical questions the interviewer might ask.

Let’s look at a few other common Java interview questions:

  • Can you explain what a “platform independent programming language” means, and why Java fits this description?
  • Can you explain the difference between StringBuffer and String?
  • Tell me what you know about the finalize() method?
  • Can you explain the difference in Set and List interface?
  • Why doesn’t Java support multiple inheritances?
  • Tell me what you know about Java Exception Handling? Is there a difference between “throw” and “throws”?
  • What is the Final keyword in Java? How is a super keyword used?
  • Can you explain the abstract class in Java? How is it different from an abstract class in C++?
  • How does static variable work in Java?
  • How does Java store objects in memory?
  • What are the differences between HashTable and HashMap in Java?

Keep in mind, these are common Java interview questions. Many jobs will require specialized technical knowledge and Java programming that isn’t covered by these questions. Understand the position you are interviewing for and the expectations for the job.

Next, we’ll go over a few other things you can do to ace your interview.

Appearances Mean Everything

Beyond knowing the answers to the top interview questions, landing the job is all about first impressions and professionalism. Employers are looking for Java programmers that fit within the corporate culture and take pride in themselves. Confidence in your abilities translates to confidence in your appearance and mannerisms.

Below are some guidelines to acing the first impression:

Prepare for the Interview

You are an expert in your field, Java programming, but companies also expect you to know about them and how they are using Java. Go beyond the simple Google search and see what the company says about itself. Look at what others are saying about the company and who are their competitors. Review their business pain points and prepare responses on how you can solve them.

Dress Appropriately

Sometimes a recruiter or the hiring manager will provide guidelines on what to wear. If they don’t, do your research and learn what is expected in the corporate culture. Not every company will expect a suit, but some won’t give you a second glance if you wear jeans. In general, interviews tend to be more formal than your daily wear once you land the job.

  • Here are recommendations for women, including what to wear and suggestions on where to buy layers, blazers, dresses, and pants. You don’t have to buy the exact item in the article; use it as a guideline and tailor it to your style and budget.
  • Likewise, there are also suggestions for men for ties, shirts, and trousers. Again, make the style your own, but make sure it fits the expectations.

Print your Resume

Some companies and human resource departments still prefer paper. Print and bring a copy of your resume. It’s better to have it and not need it, then to not be prepared for someone to review your resume.

Accessories

Store your printed resume, laptop and any samples in a portfolio or briefcase, so they are crisp when you arrive. You will lose credibility if your work looks sloppy.

Follow Up

Gather business cards or contact information during the interview. Email a thank-you note within 24 hours (the sooner the better) of the interview. Express not only your thanks, but also your excitement and recap what you can bring to the company.

A Final Word on Java Interview Questions 

Learning Java is only the first step in a career. Even as the demand for quality employees and the sheer number of companies using Java continues to rise, competition for jobs is still fierce.

Preparing for Java interview questions and doing your research before you meet with a recruiter is critical to landing the job you want. You may be the best Java programmer for a position, but if you can’t ace the interview and show what an asset you will be for the company, you may never get a chance to show what you can do.

Meta Information

Focus Keyword(s): Java Interview Questions

Meta Keywords: Java programming, Java programmer

Meta Title: The Top 21 Most Common Java Interview Questions

Meta Description: Competition is fierce for Java programmer jobs. Stay ahead of the competition with these top Java interview questions.

WordPress Tags: Java, Java interview questions, Java programming

Filed under: Java by admin
7 Comments »

How System.out.println() works

In Java, how does System.out.println() work?

This question is an excellent example of how just some very basic knowledge of Java can lead you to the correct answer. Most interviewers would not expect you to know the answer to do this right away – but would like to see how you think and arrive at an answer.

Marcus Aurelius (a Roman emperor) once said: "Of each particular thing ask: what is it in itself? What is its nature?". This problem is an excellent example of how that sort of thinking can help one arrive at an answer with only some basic Java knowledge.

With that in mind, let’s break this down, starting with the dot operator. In Java, the dot operator can only be used to call methods and variables so we know that ‘out’ must be either a method or a variable. Now, how do we categorize ‘out’? Well, ‘out’ could not possibly be a method because of the fact that there are no parentheses – the ‘( )’ – after ‘out’, which means that out is clearly not a method that is being invoked. And, ‘out’ does not accept any arguments because only methods accept arguments – you will never see something like “System.out(2,3).println”. This means ‘out’ must be a variable.

What is “out” in System.out.println()?

We now know that ‘out’ is a variable, so we must now ask ourselves what kind of variable is it? There are two possibilities – it could be a static or an instance variable. Because ‘out’ is being called with the ‘System’ class name itself, and not an instance of a class (an object), then we know that ‘out’ must be a static variable, since only static variables can be called with just the class name itself. So now we know that ‘out’ is a static member variable belonging to the System class.

Is “out” in System.out.println() an instance variable?

Noticing the fact that ‘println()’ is clearly a method, we can further classify the ‘out’ in System.out.println(). We have already reasoned that ‘out’ is a static variable belonging to the class System. But now we can see that ‘out’ must be an instance of a class, because it is invoking the method ‘println()’.

The thought process that one should use to arrive at an answer is purposely illustrated above. Without knowing the exact answer beforehand, you can arrive at an approximate one by applying some basic knowledge of Java. Most interviewers wouldn’t expect you to know how System.out.println() works off the top of your head, but would rather see you use your basic Java knowledge to arrive at an answer that’s close to exact.

When and where is the “out” instantiated in System.out.println?

When the JVM is initialized, the method initializeSystemClass() is called that does exactly what it’s name says – it initializes the System class and sets the out variable. The initializeSystemClass() method actually calls another method to set the out variable – this method is called setOut().

The final answer to how system.out.println() works

The more exact answer to the original question is this: inside the System class is the declaration of ‘out’ that looks like: ‘public static final PrintStream out’, and inside the Prinstream class is a declaration of ‘println()’ that has a method signature that looks like: ‘public void println()’.

Here is what the different pieces of System.out.println() actually look like: 

//the System class belongs to java.lang package
class System {
  public static final PrintStream out;
  //...
}

//the Prinstream class belongs to java.io package
class PrintStream{
public void println();
//...
}

Filed under: Java by admin
21 Comments »

« Previous Page