HashSet

Hashset as the name suggests is an implementation of the set interface. A set does not allow duplicates in the collection. if you try to insert the same object twice, the already existing is replaced. This collection does not guarantee of the insertion order and the objects will not be returned in any particular order

A HashSet depends on the hash function of the object and is backed by a hashmap. So a hashset similar to the hashmap depends heavily on the hashcode and equals method to implement its functionality.

A HashSet is not synchronized, it means that there is no guarantee of the consistency of the objects in the HashSet if they are accessed/modified by multiple threads.

 Set<String> nameSet = new HashSet<>();
       nameSet.add(null);
       nameSet.add("Jane");
       nameSet.add("polly");
       nameSet.add("Jane");
       nameSet.add(null);
       System.out.println(nameSet);

[null, polly, Jane]

As from the example it is clear that there is no particular order in which the elements retrieved. A null is also allowed to be inserted into the collection.

The HashSet is best for search operations if the hashcode function is designed so that there are minimum hash collisions. It is also advisable to initialize the Set with capacity if you know size it before hand.

As stated earlier a HashSet is backed by a HashMap, so all the elements are added as keys in the map and all the values are defaulted to a dummy element.

Below is representation of the add method in the HashSet. The add method adds element as key in the map and value is defaulted to a dummy value.

private static final Object PRESENT = new Object();
 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
 }

Advertisement

Access Modifiers

Java provides with various access modifiers to class, methods, variables, constructors to set access level and control who can access which variables or class or methods.

The Access levels are divided into below categories

• Public >> Access to everyone
• Private >> Access to enclosing class
• Protected >> Access to all subclass and within the package
• default >> Access to all classes within the package

Lets see how these modifiers affect the its functionality when applied to different key aspects of JAVA

	Public	Private	Protected	Default (No modifier)
Class	Acesss to everyone	NA	NA	Access to classes within package
Variable	Acess to everyone	Access to enclosing class members	Access within package and subclass	Access to classes within package
Method	Acess to everyone	Access to enclosing class members	Access within package and subclass	Access to classes within package
Constructor	Acess to everyone	Access to enclosing class members	Access within package and subclass	Access to classes within package

There is another keyword “final” which can be applied to a Class, Variable, Method. Although it does not determine the access but it has great significance.

When applied to a class it means, the class cannot be subclassed, i.e. extending a class marked final is not possible. A small example is described below. The keyword can be placed before or after the access modifier.

public final class Car {
}

The final keyword when applied to method of a class, makes the method final and does not allow the subclasses to be override.

And the final keyword when applied to a variable implies that the variable cannot be reassigned to a new instance once it is assigned a value.

Constructor

A Constructor is used to initialize an object. A constructer is nothing but a special function within a class which has same name as that of the class and does not return any value.

DEFAULT CONSTRUCTOR/NO ARG CONSTRUCTOR

public class car {

   car(){
      //initializing code
   }
}

The above code snippet creates a class car and has a constructer method which will initialize the class to form an instance. A constructer with no parameters is called default constructor. You can create only one no-arg constructor in a class. If you do not create a default constructor then Java will create one for you implicitly. There will be slight change in the behavior but we will come back to it later.

PARAMETERIZED CONSTRUCTOR

public class car {
   String make;
   String model;
   car(String make,String model){
      this.make = make;
      this.model = model;
   }
}

The above code snippet is an example of a parameterized constructor. As the name suggests, it is a constructor with parameters. If you have created a parameterized constructor then Java will not create a default constructor for you. This is where the behavior changes for the implicit default constructor. You can create multiple parameterized constructors in a class, however no two parameterized constructors can have same signature. By signature here I mean that no two constructors can have same type of parameter in same order.

Below code will result into a compilation error because the signature for both constructors are same.

public class car {

   car(String make, String model){
      //initializing code
   }

  car(String model, String Make){
      //initializing code
   }
}

Class and Object

Java is an object oriented programming language, each program is represented in terms of object. So an object is any real world object for e.g. a Car, Computer, Apple etc.

To understand it better, lets say we are given a program to read file from the system from a given specified location. So how do we represent a file and how do we represent its behavior ? Like a file is supposed to read, write or possible delete ? how do we represent all of this ?

In an OOP (Object oriented programming) we would represent a File and its behavior in a class. For e.g.

class File {
String fileName;

File(String fileName){
this.fileName = fileName;
}

public void read(){
 ...
}

public void write() {
 ..
}

}

So a class represents everything a file object can do. So in our example, a file can read and write.

So if we have to read a file, we have to create an instance of the file object, like below.

File myfile = new File("sample.txt")
myfile.read();

So now we have created a new instance of the File class which is represented by variable “myfile”. The variable “myfile” uniquely represents the file “sample.txt” and when we can call read/write method on the “myfile” instance and it will execute the code inside the methods read()/write() of the file class.

So the green box represents “Class” and all the yellow boxes represent “Object/Instances” of the class “File”. We can have as many objects of the class File as we want.

Linked List

LinkedList is an implementation of the List interface. As with all the list interfaces, this collection maintains the insertion order.

The LinkedList also implements a Deque interface. So a LinkedList represents a Deque and a List.

As the names suggests, this collection arranges elements similar to a linked list data structure. In a linked list data structure, each element has a previous and next reference, similarly in LinkedList, each element in the list is represented by a Node Object as below.

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

So each element is represented by the field “item” in the Node object of LinkedList class and it is the single element in the collection, whereas the field “prev” and “next” point to the Node object of previous element and the next element in the collection. Hmm, lets look at a visual representation of a linked list for a clearer picture if you have forgotten a linked list. Actually it really is a double linked list.

A Linked List Representation

so the above diagram is an example of linked list. Each element represent a node in the LinkedList. Apple being the first element in the list does not have a previous element linked to it. Every other element except the last element has previous and next element reference to navigate. The last element does not have any next element reference as it is the last element in the list.

So, how does the insertion work in case of linked list. So if I have to add an element to the list, a new “Node” object is created and the “prev” field is updated in the Node object to point to the last element in the list. So unlike an ArrayList a collection does not require a continuous allocation memory, it can create a node object anywhere and update its references.

INSERTION

So in the above diagram, we are adding “Peach” to the collection, so we just create new Node object and reference the last object in the “Prev” of the last element and the new element added becomes the last element in the collection. The LinkedList maintains the position of the first element and the last element the list.

A Deletion happens by traversing in the list and then updating the references of the prev element and the next element. Take a look at the representation below

Deletion

So we have removed the element “Lemon” by removing its references from the Previous and its next element. The dotted line represent old references. So now when we traverse, the element Lemon will never come into the picture.

Traversal is linear in case of a linked list, we cannot jump with index to a particular position as we can do with an ArrayList. Although the api provides us a way to fetch by index, but the retrieval is linear so it might take o(n) complexity to fetch an element. So compared to an ArrayList, fetching by index is slow.

	Insert	Delete	Retrieval
Complexity	o(1)	o(n/4)	o(n/4)

Basic linked list example

        List<String> linkedList = new LinkedList<>();
        linkedList.add("apple");
        linkedList.add("orange");
        linkedList.add("peach");

Please refer below java doc location for detailed description of the api

https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html