Mapping in Java

Mapping:
                 The basic idea behind mapping is to establish a relation between two or more seemingly unrelated set of data structures. A common example of mapping is when a word string is mapped to its integer equivalent based on the ASCII values of it's characters. At a first glance, it might make little sense to develop a relationship between a string and an integer. However, mapping is very useful in programming and is, in fact, very common. 
                The main attraction to mapping is the reduced search time. While a linear search requires O(n) in the average case, search in mapping takes O(n) in worst case, only if the hashing function is not carefully chosen.

A mapping overview - buckets (ranges/numbers) mapped to keys (Strings)

(Image courtesy - Wikipedia)

Types of Mapping and Data Structures in Java:

1) One-to-one Map - java.util.hashmap:
                    HashMap is the most commonly used data structure that maps an object with a key. Both the object and the key can be of any data type, provided that the data type extends Object. Thus, primitive data types like int, float, double, etc. are not used as object and keys. Their corresponding wrapper classes like Integer, Float, Double, etc., however, can be used since they all extend Object.
                    HashMap maps any object using a key. Both the object and the key can be determined by the programmer, provided that the key is unique. Every key in the HashMap maps to one object only. Thus, this is a one-to-one mapping kind of data structure.
                     Already hashed objects can be retrieved from a key by the Map.get() method. Map.put() assigns an object to a key.

2) One-to-one bidirectional Map - org.apache.commons.collections.BidiMap:
                      One shortcoming of java.util.HashMap is that one cannot retrieve a key from its value. This is logical in the sense that the value is derived from the key, and hence the value should depend on the key and not the other way around. If, we try to search a key from a value, we may need to traverse the entire HashMap, which takes O(n) and defeats the purpose of a HashMap.
                       However, there may be times when we need to establish a bidirectional relationship between 2 objects whilst preserving the fast searching of a HashMap. Fortunately, BidiMap becomes useful in such cases. Note that in the case of BidiMap, the words "key" and "value" do not hold their semantic value. Since, both depend on each other, neither is a key. Both are simply values, strictly speaking.
                       BidiMap gives a convenient function getKey() which returns the key for the value argument. Both the key and value can be anything that extends the Object class. Again, "key" and "values" should not be taken literally.


3) One-to-many Map using java.util.hashmap:
                         Although generally used for one-to-one mapping, we can implement one-to-many mapping using java.util.hashmap. As mentioned earlier, the value can be anything that extends Object, we can use a List, or an ArrayList, or any other Collection for that matter as value, thus making the map one-to-many.
                          One key will thus map to one list of values. These values may now be arranged in any order as possible. If there is a specific order in the values, then an ArrayList is preferred, since it provides arbitrary access via indexes. In any case, the primary point of consideration here should be that the values must be arranged in a way that the main advantage of using a Map i.e. O(1) average search time should not be compromised to a large extent.

Traversing through a Map in Java:
                           There are a few ways to traverse through a map in Java, but the one we suggest is using an Iterator via a Map.Entry of the map. After assigning an iterator to a map, it traverses through the map via its next() method. A Map.Entry will create an Entry object from which the key and the value of the Entry can be easily obtained via the getKey() and getValue() methods. Both HashMap and BiDiMap can be traversed in the same way.

 

Arbitrary Precision Types In Java

QUESTION : 
What will be the output in the following code snippet?

Here's the snapshot of the output of the above function

NOTE : 
For built-in primitive data types such as int, long, double, etc. Java never throws any overflow or underflow exception, even though the size and the bounds for these data types is defined. 

Why? Because all data is internally stored by the JVM in binary-format. Thus, in actual memory, each variable, whether int or double is stored as a string of 1's and 0's. There is no concept of a "negative sign" in binary system. Negative numbers are stored in a special format called 2's complement . 

Hence, when the bound on any data type is reached and exceeded, the JVM simply reverses the sign of the number and prints the largest number in that sign. For example, in the above example, if we exceed 2147483647 which is the upper bound on int, the sign is reversed to negative and the value of smallest possible int is printed.

How do we avoid this? By casting the number into a larger data type and checking its value. If indeed, overflow or underflow has occurred, we can throw an exception and take the necessary rectification. Following is a code snippet which illustrates this.

What if overflow/underflow is a valid case in my problem?
Overflow is a valid case practically when problems involving very large numbers are present. In such cases, a way to implement variables is to use Arbitrary Precision Data Types. Java offers 2 arbitrary precision types : BigInteger and BigDecimal in java.math library.

The word "arbitrary precision" means that a variable of such type uses exactly as much space as required or mentioned. Thus, the precision is "set" according to our needs. Theoretically, there is no limitation to the size, the only limitations being that of insufficient memory. 

It is important to note that these data types are implemented internally as a collection of primitive data type. Thus, BigInteger is implemented as an array of ints. Also, these are implemented classes and not default and Java does not allow operator overloading. Thus, primitive operations such as addition, multiplication, power, etc. although present for these classes, do not use operators such as "+", "*" etc. Instead, they use functions such as a.add(b), a.multiply(b), etc. Since the use of functions is involved, the operations tend to be slower.

BigInteger is generally used for large integers and BigDecimal is used when extremely high levels of precisions is required (1000th decimal place of π).

Tic Tac Toe Applet

Here is a simple two-player Tic Tac Toe applet, just to get familiar with ActionListeners and basic GridView. Hopefully, the code below is well-commented and self-explanatory.


Here are some snaps of the output :

The Story Behind "public static void main"

All the beginners in Java language are first taught the Hello World program, which although very simple looking, contains a lot of the functionality secrets of Java.

The first method that a new java programmer writes is the “main” method.

The entire Hello World program looks something like the following:

public class HelloWorld {
 public static void main(String[] args) {
  System.out.println("Hello World");
 }
}

The output, obviously is:

Hello World

Let us explore the main method and all its keywords one by one:

The first thing one should know that the execution of a java program starts from the main function. After loading the program, the Java Virtual Machine (JVM) scans the program to search for “public static void main (String[] args)”

Public: “public” is an access-specifier and it means that the method can be called from outside of the class. The main method has to public so that the JVM can call it and begin the program.

Static: “static” means that only one copy of the main function is shared between all objects of the class and one doesn’t have to initialize a class object to call the main method. (For more information on “static”, click here)

Void: “void” is a return type. It indicates that the main function does not return anything. This is quite logical, as the main function is called implicitly by the JVM and not by another function. So it has no function to return value to.

(String[] args): The entire phrase inside the parentheses are arguments passed to the main function. The argument type is an array of the type java.lang.string and the name of the array is “args”. Consider the following program:

public class HelloWorld {
 public static void main(String[] args) {
  System.out.println("Hello World"); 
    for (int i = 0; i < args.length; i++) {
  System.out.println(args[i]);
     }
   }
}

If you are operating from the command prompt/terminal, and you enter

       java HelloWorld I’m Batman

The output will be:

Hello World

I’m

Batman

If you type: java HelloWorld “I’m Batman”, the output is:

Hello World

I’m Batman

If you are using the Eclipse IDE, you can enter the “program arguments” from Run>Run Configurations>(x)= Arguments (That’s the second tab) and then enter your arguments.

What does "static" mean in Java?

I have gone through many books of java but not many give sufficient explanation of what is the meaning of the keyword "static" in Java and when does one use it.

STATIC VARIABLES:

Making a variable static basically means that only one copy of the variable is shared between all the objects of the class. If one object changes the value of that variable, all the variables get the updated value.

Consider the following code snippet:

class StateOfACountry; 
 public String stateName;
 public String CM_name;
 public static String PM_name;
  
 public static void main(String []args){
  StateOfACountry state1 = new StateOfACountry();
  state1.CM_name = "CM1";
  state1.PM_name = "PM";
  System.out.println("State 1 CM name " + state1.CM_name);
  System.out.println("State 1 PM name " + state1.PM_name);
 
  StateOfACountry state2 = new StateOfACountry();
  System.out.println("State 2 CM name " + state2.CM_name);
  System.out.println("State 2 PM name " + state2.PM_name);
  
  state2.CM_name = "CM2";
  state2.PM_name = "PMabc";
  
  System.out.println("State 2 CM name " + state2.CM_name);
  System.out.println("State 2 PM name " + state2.PM_name);

  System.out.println("State 1 CM name " + state1.CM_name);
  System.out.println("State 1 PM name " + state1.PM_name);
  }
}

The output is:

State 1 CM name CM1

State 1 PM name PM

State 2 CM name null

State 2 PM name PM

State 2 CM name CM2

State 2 PM name PMabc

State 1 CM name CM1

State 1 PM name PMabc

In the above example, the variables stateName, CM_name are not static while the variable PM_Name is. This is correct logically because if there are many states in a country, the Chief Minister (CM) of one state may be different from another. However, all states will share the same Prime Minister (PM) name. Thus we see that, if there is a variable which is common amongst all the objects in the same class, we should treat it as static.

Now, consider a case of re-elections. If the CM of state1 is changed, it is not necessary that the CM of state2 be changed as well. However, if the PM of the country is changed, then the change is reflected on the PM of all the states! (which is correct logically).

Thus, we see that the static variables belongs to the class on a whole and not to a particular object of the class. In the above case, a Prime Minister (PM) belongs to a country on a whole, rather than the state of a country.

All such variables which are not tied to an object should be made static in your programs.

STATIC FUNCTIONS:

The definition of static extends to functions as well i.e. a copy of static function is shared between all the objects of the class. A function is made static when two static functions have nothing in common between them.

Also, there is an additional clause: Static functions can access and operate on only static variables. This, of course, is logical as static functions are something that belong to the class rather than an object, and therefore should operate only on variables that too belong to the class.

Accessing non-static variables in static functions causes an error (try it!)

Consider the above example, now modified:

class StateOfACountry{
   public String stateName;
   public String CM_name;
   public static String PM_name;
           
   public static void changePM(String newPM_name){
     PM_name = newPM_name;
   }
           
   public void changeCM(String newCM_name){
     this.CM_name = newCM_name;
   }
 
   public static void main(String []args){
 
      StateOfACountry state1 = new StateOfACountry();
      state1.CM_name = "CM1";
      state1.PM_name = "PM";
           
      StateOfACountry state2 = new StateOfACountry();     
      state2.CM_name = "CM2";
      state2.PM_name = "PMabc";
      state1.changeCM("newCM1");
      System.out.println(state1.CM_name);
      System.out.println(state2.CM_name);
           
      state1.changePM("newPM1");
      System.out.println(state1.PM_name);
      System.out.println(state2.PM_name);          
     }
}

The output is:

newCM1

CM2

newPM1

newPM1

Thus we see that the function changeCM operates on the CM_name of a particular object, while the static function changePM operates on the static variable PM_name which is common for all the objects in the class.

INITIALIZING A STATIC VARIABLE:

Since static variables are not tied to any objects, they need not be initialized using an object. In other words, they do not have an “object state”.

public class MeaningOfStatic {
public static int var = display();
  public MeaningOfStatic() {
     System.out.println("Constructor Entered. Object is instantiated.");
  }
 public static int display(){
     System.out.println("Hello World");
     System.out.println(var);
     return 10;
   }
 
  public static void main(String[] args) {
     System.out.println("Main entered.");
     MeaningOfStatic object = new MeaningOfStatic();
     object.display();
     System.out.println(Math.PI);
     System.out.println(Math.sqrt(2)); //No object of Math is                                                initialized to invoke sqrt, because its static! 
     }
}

The output is:

Hello World

0

Main entered.

Constructor Entered. Object is instantiated.

Hello World

10

Thus we see that the static variable var was declared even before an object was initialized. It was also assigned value using the static function even before the main function was started! Because it isn’t tied to any particular object.

All lang.Math methods in java are static (e.g. Math.Random(), Math.sqrt()) because it wouldn’t make sense to tie all this methods to an object i.e. the methods Math.random, Math.sqrt have nothing in common.