A Simple Implementation of LinkedList in java

public class MyLinkedList {

Entry head;
Entry last;
void add(Object obj){
if(last !=null){
last.next = new Entry(obj, null, null);
last.next.pre = last;
last = last.next;
}else{
last = head= new Entry(obj, null, null);

}
}
Object get(int index){
int i =0 ;
Entry prev = head;
while(i++ prev = prev.next;
}
return prev.value;
}
class Entry {
Object value;
Entry next;
Entry pre;

Entry(Object value, Entry next, Entry pre){
this.value = value;
this.next = next;
this.pre = pre;
}

}

public static void main(String []args){
MyLinkedList myList = new MyLinkedList();
myList.add("shiv1");
myList.add("shiv2");
myList.add("shiv3");
myList.add("shiv3");
System.out.println("print second "+(String)myList.get(3));

}

}

HashMap Made Easy

HashMap Implementation strategy:

HashMap uses hash function to map keys for ex names to index/buckets/slots in the array.



Noramally every HashMap implementation assumes more than one key produce same hash values, known as hash collisions. The performance of hashmap ie how faster search works and memory not wasted doesn't depends directly on the no of stored entries n. Actually it depend on the load factor = no of stored entries/ size of array. Average look up cast is constant for load factor 0-.7, beyand this result in more hash collision reducing the search performance. Load factor near to zero indicate lot of memory waste without significant improvement in search.



Java collection framework implementation followes seperate chaining/direct chaining/chaining strategy. Each slot in table/array has a link to linked list that has key value pairs that hashed to same location. For ex in above picture john smith and sandra dee hashed values is same as array index 152. Now entry john Smith will be stored at index 152 and have a link of another entry names sandra(a linked list referred by slot 152).

HashMap Implementation

The following code has similar HashMap implementation as it is in collection package of java. This is very simplified and useful for the people who just want to know how its been implementated in collection framework.


public class MyHashMap {

Entity [] table;
int initialCap = 5;

MyHashMap(){
table = new Entity[initialCap];
}

int hash(Integer index){
return index%initialCap ;
}

Object put(Object key, Object value){
Object toRet= null;
int hash = hash(((Integer)key));
Entity e = table[hash];
table[hash((Integer)key)] = new Entity(hash, key, value, e);
if(e!=null)
toRet = e.value;
return toRet;
}

Object get(Object key){
int hash = hash((Integer)key);
for(Entity e= table[hash]; e!=null; e= e.next ){
if(hash == e.hash && key.equals(e.key)){
return e.value;
}

}
return null;
}

class Entity{

public int hash ;
public Object key;
public Object value;
public Entity next;

Entity(int hash, Object key, Object value, Entity next){
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public boolean equals(Object o){
if(!(o instanceof Entity)) return false;
if((Integer)this.key == (Integer)(((Entity)o).key)) return true;
return false;
}
}

public static void main (String [] args){

MyHashMap map = new MyHashMap();
map.put(1, 2);
map.put(2, 3);
map.put(3, 7);
map.put(4, 1);
map.put(5, 4);
map.put(6, 5);
map.put(7, 6);
System.out.println("got my value :-)"+map.get(1));


}
}

Feel free to experiment. I will appreciate your effort to find some logical error in the code.

Different XML processing mechanism DOM, OM, SAX

By XML processing i mean different approces to create, read and update xml document.

Creating XML document::

There are two ways we can create XML document::

1. DOM

2. OM

DOM is expensive in the sence it creats in memeory object.

To parse XML files commonly avalible approches are as follows>>

1. DOM

2. SAX

3. OM

DOM

DOM reads the complete XML document feeded in one shot and creates in memory object for that. Creating in memory object for complete xml document has got its advantage and disadvantage.

Adv: since we have complete xml as in memory object we can nevigate to different part of the xml documnet we can read it manupulate it.

DisAdv: Suppose we have got a document having 3000 emplyee element. so it will create 3000 emplyee element in memory, which will consume lot of memory.

Now some code ...How we'll do that...

//get the factory
DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
//get the document builder
DocumentBuilder db = dbf.newDocumentBuilder();
//parse using builder to create dom represntaion of xml
Document dom = db.parse("employees.xml");
//get the root elememt
Element docEle = dom.getDocumentElement();
//get a nodelist of elements
NodeList nl = docEle.getElementsByTagName("Employee");
for(int i = 0 ; i < nl.getLength();i++) {
//get the employee element
Element empEl = (Element)nl.item(i);
String name = getTextValue(empEl,"Name");
int id = getIntValue(empEl,"Id");
int age = getIntValue(empEl,"Age");
String type = empEl.getAttribute("type");
}
SAX
sax do event based parsing...now what does that means...that means it will parse xml documnet based on the event it find in XML document....actually sax treats strat, end and getting some char as event.. while do sax parsing we can register our handler with parser that will be invoked when parser will encounter with such event. We can write our code in the handler to process the xml stream thrown by the parser.
//Create a custom handler
public class MyHandler extends DefaultHandler{
private String tempVal;
//to maintain context
private Employee tempEmp;

//Event Handlers
public void startElement(String uri, String localName, String qName, Attributes attributes) throws SAXException {
if(qName.equalsIgnoreCase("Employee")) {
//create a new instance of employee
tempEmp = new Employee();
tempEmp.setType(attributes.getValue("type"));
}
public void characters(char[] ch, int start, int length) throws SAXException {
tempVal = new String(ch,start,length);
}
public void endElement(String uri, String localName, String qName) throws SAXException {
if(qName.equalsIgnoreCase("Employee")) {
//add it to the list
myEmpls.add(tempEmp);
}else if (qName.equalsIgnoreCase("Name")) {
tempEmp.setName(tempVal);
}else if (qName.equalsIgnoreCase("Id")) {
tempEmp.setId(Integer.parseInt(tempVal));
}else if (qName.equalsIgnoreCase("Age")) {
tempEmp.setAge(Integer.parseInt(tempVal));
}
}
}
//get the factory
SAXParserFactory spf = SAXParserFactory.newInstance();
//get a new instance of parser
SAXParser sp = spf.newSAXParser();
//parse the file and also register this class for call backs
MyHandler handle= new MyHandler();
sp.parse("employees.xml", handle);
Now here comes adv and disadv with sax:
Adv: Doesn't consume lot of memory why so, it's give only that element it's reading at a given moment.
DisAdv: There is no way we can go back while traversing in XML document.
Now let's talk about stax parser.
StAX(Streaming API for XML) parser:
The above two parsers we discussed earlier were push parser. STAX is push parser. Now what does that mean???
In push parsing wn u start parsing it will throw all the parsed info on you, in case of DOM parser it will read complete complete XML document in one shot while in case of SAX parse once it started parsing it will keep on throwing event as it progress and it cant go back.
In pull parsing we have better control, lets take an example to compare.
FileInputStream fileInputStream =
new FileInputStream(fileLocation);
XMLStreamReader xmlStreamReader =
XMLInputFactory.newInstance().
createXMLStreamReader(fileInputStream);
we have created XMLStreamReader which has got iterator type of API to move forward while parsing.
xmlStreamReader.hasNext();
xmlStreamReader.next();
Thing to note here is paser wont move further untill we call next(). In case of SAX parse once we start parsing we dont have any control it will keep on throwing the element till it reaches the end of the document to be parsed.