knowledge For All

Hash table with separate chaining

import java.io.IOException;

class Link {
  private int data;
  public Link next;

  public Link(int d) {
    data = d;
  }

  public int getKey() {
    return data;
  }

  public void displayLink() {
    System.out.print(data + " ");
  }
}

class SortedList {
  private Link first;
  public SortedList() {
    first = null;
  }

  public void insert(Link theLink){
    int key = theLink.getKey();
    Link previous = null; // start at first
    Link current = first;
    // until end of list,
        //or current bigger than key,
    while (current != null && key > current.getKey()) { 
      previous = current;
      current = current.next; // go to next item
    }
    if (previous == null) // if beginning of list,
      first = theLink; 
    else
      // not at beginning,
      previous.next = theLink; 
    theLink.next = current; 
  }

  public void delete(int key){ 
    Link previous = null; 
    Link current = first;

    while (current != null && key != current.getKey()) { 
      previous = current;
      current = current.next; 
    }
    // disconnect link
    if (previous == null) //   if beginning of list delete first link
      first = first.next;       
    else
      //   not at beginning
      previous.next = current.next; //delete current link
  }

  public Link find(int key) {
    Link current = first; 
    while (current != null && current.getKey() <= key) { // or key too small,
      if (current.getKey() == key) // found, return link
        return current;  
      current = current.next; // go to next item
    }
    return null; // cannot find it
  }

  public void displayList() {
    System.out.print("List: ");
    Link current = first;
    while (current != null){
      current.displayLink(); 
      current = current.next;
    }
    System.out.println("");
  }
}

public class HashChain {
  private SortedList[] hashArray; 

  private int arraySize;

  public HashChain(int size) {
    arraySize = size;
    hashArray = new SortedList[arraySize];
    for (int i = 0; i < arraySize; i++)
      hashArray[i] = new SortedList(); 
  }

  public void displayTable() {
    for (int j = 0; j < arraySize; j++) {
      System.out.print(j + ". "); 
      hashArray[j].displayList(); 
    }
  }

  public int hashFunc(int key) {
    return key % arraySize;
  }

  public void insert(Link theLink) {
    int key = theLink.getKey();
    int hashVal = hashFunc(key); 
    hashArray[hashVal].insert(theLink); 
  }

  public void delete(int key) {
    int hashVal = hashFunc(key); // hash the key
    hashArray[hashVal].delete(key); 
  }

  public Link find(int key) {
    int hashVal = hashFunc(key); // hash the key
    Link theLink = hashArray[hashVal].find(key); // get link
    return theLink;
  }

  public static void main(String[] args) throws IOException {
    int aKey;
    Link dataItem;
    int size, initSize, keysPerCell = 100;
    size = 20;
    initSize = 10;
    HashChain hashTable = new HashChain(size);

    for (int i = 0; i < initSize; i++){
      aKey = (int) (java.lang.Math.random() * keysPerCell * size);
      dataItem = new Link(aKey);
      hashTable.insert(dataItem);
    }
    hashTable.displayTable();
    aKey = 100;
    dataItem = new Link(aKey);
    hashTable.insert(dataItem);
    aKey = 100;
    hashTable.delete(aKey);

    aKey = 50;
    dataItem = hashTable.find(aKey);
    if (dataItem != null)
      System.out.println("Found " + aKey);
    else
      System.out.println("Could not find " + aKey);
  }

}

OUTPUT

0. List:
1. List:
2. List:
3. List: 1483
4. List: 204
5. List: 445 605
6. List: 1686
7. List:
8. List: 1748
9. List: 229
10. List:
11. List:
12. List:
13. List:
14. List:
15. List: 635
16. List:
17. List:
18. List: 1218
19. List: 379

Hash table with separate chaining

import java.io.IOException;

class Link {
  private int data;
  public Link next;

  public Link(int d) {
    data = d;
  }

  public int getKey() {
    return data;
  }

  public void displayLink() {
    System.out.print(data + " ");
  }
}

class SortedList {
  private Link first;
  public SortedList() {
    first = null;
  }

  public void insert(Link theLink){
    int key = theLink.getKey();
    Link previous = null; // start at first
    Link current = first;
    // until end of list,
        //or current bigger than key,
    while (current != null && key > current.getKey()) { 
      previous = current;
      current = current.next; // go to next item
    }
    if (previous == null) // if beginning of list,
      first = theLink; 
    else
      // not at beginning,
      previous.next = theLink; 
    theLink.next = current; 
  }

  public void delete(int key){ 
    Link previous = null; 
    Link current = first;

    while (current != null && key != current.getKey()) { 
      previous = current;
      current = current.next; 
    }
    // disconnect link
    if (previous == null) //   if beginning of list delete first link
      first = first.next;       
    else
      //   not at beginning
      previous.next = current.next; //delete current link
  }

  public Link find(int key) {
    Link current = first; 
    while (current != null && current.getKey() <= key) { // or key too small,
      if (current.getKey() == key) // found, return link
        return current;  
      current = current.next; // go to next item
    }
    return null; // cannot find it
  }

  public void displayList() {
    System.out.print("List: ");
    Link current = first;
    while (current != null){
      current.displayLink(); 
      current = current.next;
    }
    System.out.println("");
  }
}

public class HashChain {
  private SortedList[] hashArray; 

  private int arraySize;

  public HashChain(int size) {
    arraySize = size;
    hashArray = new SortedList[arraySize];
    for (int i = 0; i < arraySize; i++)
      hashArray[i] = new SortedList(); 
  }

  public void displayTable() {
    for (int j = 0; j < arraySize; j++) {
      System.out.print(j + ". "); 
      hashArray[j].displayList(); 
    }
  }

  public int hashFunc(int key) {
    return key % arraySize;
  }

  public void insert(Link theLink) {
    int key = theLink.getKey();
    int hashVal = hashFunc(key); 
    hashArray[hashVal].insert(theLink); 
  }

  public void delete(int key) {
    int hashVal = hashFunc(key); // hash the key
    hashArray[hashVal].delete(key); 
  }

  public Link find(int key) {
    int hashVal = hashFunc(key); // hash the key
    Link theLink = hashArray[hashVal].find(key); // get link
    return theLink;
  }

  public static void main(String[] args) throws IOException {
    int aKey;
    Link dataItem;
    int size, initSize, keysPerCell = 100;
    size = 20;
    initSize = 10;
    HashChain hashTable = new HashChain(size);

    for (int i = 0; i < initSize; i++){
      aKey = (int) (java.lang.Math.random() * keysPerCell * size);
      dataItem = new Link(aKey);
      hashTable.insert(dataItem);
    }
    hashTable.displayTable();
    aKey = 100;
    dataItem = new Link(aKey);
    hashTable.insert(dataItem);
    aKey = 100;
    hashTable.delete(aKey);

    aKey = 50;
    dataItem = hashTable.find(aKey);
    if (dataItem != null)
      System.out.println("Found " + aKey);
    else
      System.out.println("Could not find " + aKey);
  }

}

OUTPUT

0. List:
1. List:
2. List:
3. List: 1483
4. List: 204
5. List: 445 605
6. List: 1686
7. List:
8. List: 1748
9. List: 229
10. List:
11. List:
12. List:
13. List:
14. List:
15. List: 635
16. List:
17. List:
18. List: 1218
19. List: 379

Hash table drill program

import java.util.Random;
import java.io.*;
import java.util.Scanner;

public class HashDrill
{ // Selection the hash function for int hash()
   static private int   option = 0;

   static private boolean[] displaced;

   // Seeded in main, used in fillTable
   static Random generator = new Random();

   static Scanner console = new Scanner(System.in);

// Hash function, based on the selection option
   private static int hash ( int value, int size )
   { int d1 = Math.abs(value),
          d0 = d1 % 10;
      int key = d1 % size;   // Used for single-digit value

      // More than one digit; isolate d1 and compute.
      if ( d1 != d0 )
      { while ( d1 > 9 )
            d1 /= 10;
         if ( option == 0 )
            key = (d1*10 + d0) % size;
         else
            key = (d1 * d0) % size;
      }
      return key;
   }

   // Fill table[], val[] and key[]
   private static void fillTable ( int[] table, int[] val, int[] key )
   { int j, k,
          size = table.length;

      // Initialize the table to empty (-1 throughout)
      for ( j = 0; j < size; j++ )
         table[j] = -1;

      // Generate the values, then place them into the table
      for ( j = 0; j < val.length; j++ )
      { k = generator.nextInt(4) + 1;
         val[j] = generator.nextInt((int)Math.pow(10,k));
         k = hash(val[j], size);
         key[j] = k;

         // Linear probe for an available cell
         while ( table[k] != -1 )
            k = (k+1) % size;
         // Position the value into the table
         table[k] = val[j];
         displaced[k] = k != hash(val[j], size);
      }
   }

   // Display table[], val[] and key[]
   private static void showTable ( int[] table, int[] val, int[] key )
   { int j;

      System.out.println ("\nd1 is the leading digit, d0 the trailing." +
         "\nHash function: " +
         ( option == 0 ? "(d1*10 + d0) % " : "(d1 * d0) % " ) +
         table.length );

      System.out.println ("\nindex    value key");
      for ( j = 0; j < val.length; j++ )
         System.out.printf ("%5d %8d %4d\n", j, val[j], key[j]);

      System.out.print ("\nPress enter to see the hash table.");
      console.nextLine();

      System.out.println ("\nindex    table");
      for ( j = 0; j < table.length; j++ )
      { System.out.printf ("%5d %8d", j, table[j]);
         if (displaced[j]) System.out.print(" *");
         System.out.println();
      }
   }

   public static void main ( String[] args )
   { long   seed = generator.nextLong();
      int    size = -1;
      int[] table;
      int[] val = new int[10];
      int[] key = new int[10];
      int    j, k;

      System.out.print ("Size: ");
      if ( args.length > 0 )
      { try
         { size = Integer.parseInt(args[0].trim()); }
         catch (Exception e)
         { System.out.println(e); System.exit(-1); }
         System.out.println(size);
      }
      else
      { size = console.nextInt(); console.nextLine(); }
      table = new int[size];
      displaced = new boolean[size];

      if ( args.length > 1 )
      { try
         { option = Integer.parseInt(args[1].trim()); }
         catch (Exception e)
         { System.out.println(e); System.exit(-1); }
      }

      if ( args.length > 2 )
      { try
         { seed = Long.parseLong(args[2].trim()); }
         catch (Exception e)
         { System.out.println(e); System.exit(-1); }
         System.out.println("Setting seed to " + seed);
      }
      generator.setSeed(seed);

      fillTable(table, val, key);

      showTable(table, val, key);
      System.out.print ("\nPress enter to exit.");
      console.nextLine();
   }
}

OUTPUT

Size: 10

d1 is the leading digit, d0 the trailing.
Hash function: (d1*10 + d0) % 10

index    value key
    0      501    1
    1      997    7
    2     3252    2
    3      624    4
    4      939    9
    5       46    6
    6      923    3
    7        8    8
    8       99    9
    9        8    8

Press enter to see the hash table.

index    table
    0       99 *
    1      501
    2     3252
    3      923
    4      624
    5        8 *
    6       46
    7      997
    8        8
    9      939

Hash table drill program

The n-Queens Problem

import java.util.*; //to import Scanner class for take the value from user of the chess board

public class quen{

int[] x=new int[16]; //allocate a location for array storage

public void Nquens(int r, int n){

for(int c=0;c<n;c++){

if (canPlace(r,c)){

x[r] =c;

if(r==n-1){ //it's say successfully filled

print(x,n);

board(x,n);

break;

}

else Nquens(r+1,n); //call or move 1st one queen to up box

}

boolean canPlace(int r,int t){ // to check can place or not

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

if (x[i]==t||Math.abs(i-r)==Math.abs(x[i]-t)) //to check if any queen take place in vertical or horizontal line

return false;

}

return true;

}

public void print(int[] y,int n){ //print the possible way

System.out.println();

System.out.println("another posible way");

System.out.println();

for (int i=0;i<n;i++){//n or y.length

System.out.print(y[i]+"|");

}

System.out.println();

System.out.println("board");

}

public void board(int[] y,int n){ //command for print chess board

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

System.out.println();

for(int j=0;j<n;j++){

if(j==y[i]){

System.out.print("Q"+"|");}

else{

System.out.print("*"+"|");}

}

System.out.println();

for(int k=0;k<2*n;k++){

System.out.print("-");}

}

public static void main(String arg[]){ //main method head of the program

Scanner p=new Scanner(System.in); // to take the input from outside

System.out.println("enter your board length");

System.out.println();

int r=p.nextInt(); //to assign the value to r that take from outside

System.out.println("your possible ways are");

quen x=new quen(); //to create a new instance

x.Nquens(0,r); //call the method

}

Result for above coding

enter your board length
4

your possible ways are
Nquens          (0,4)
canplace        (0,0)
        yes     x[0]=0

Nquens          (1,4)
canplace        (1,0)
0==0    1==0
              no
canplace        (1,1)
0==1    1==1
                no
canplace        (1,2)
0==2    1==2
        yes     x[1]=2

Nquens          (2,4)
canplace        (2,0)
0==0    2==0
                no
canplace        (2,1)
0==1    2==1
2==1    1==1
                no
canplace        (2,2)
0==2    2==2
                no
canplace        (2,3)
0==3    2==3
2==3    1==1
                no
                no
canplace        (1,3)
0==3    1==3
        yes     x[1]=3

Nquens          (2,4)
canplace        (2,0)
0==0    2==0
                no
canplace        (2,1)
0==1    2==1
3==1    1==2
        yes     x[2]=1

Nquens          (3,4)
canplace        (3,0)
0==0    3==0
                no
canplace        (3,1)
0==1    3==1
3==1    2==2
                no
canplace        (3,2)
0==2    3==2
3==2    2==1
1==2    1==1
                no
canplace        (3,3)
0==3    3==3
                no
                no
canplace        (2,2)
0==2    2==2
                no
canplace        (2,3)
0==3    2==3
3==3    1==0
                no
                no
                no
canplace        (0,1)
        yes     x[0]=1

Nquens          (1,4)
canplace        (1,0)
1==0    1==1
                no
canplace        (1,1)
1==1    1==0
                no
canplace        (1,2)
1==2    1==1
                no
canplace        (1,3)
1==3    1==2
        yes     x[1]=3

Nquens          (2,4)
canplace        (2,0)
1==0    2==1
3==0    1==3
        yes     x[2]=0

Nquens          (3,4)
canplace        (3,0)
1==0    3==1
3==0    2==3
0==0    1==0
                no
canplace        (3,1)
1==1    3==0
                no
canplace        (3,2)
1==2    3==1
3==2    2==1
0==2    1==2
        yes     x[3]=2

posible way
1|3|0|2|
board

*|Q|*|*|
--------
*|*|*|Q|
--------
Q|*|*|*|
--------
*|*|Q|*|
--------                no
canplace        (3,3)
1==3    3==2
3==3    2==0
                no
                no
canplace        (2,1)
1==1    2==0
                no
canplace        (2,2)
1==2    2==1
3==2    1==1
                no
canplace        (2,3)
1==3    2==2
                no
                no
                no
canplace        (0,2)
        yes     x[0]=2

Nquens          (1,4)
canplace        (1,0)
2==0    1==2
        yes     x[1]=0

Nquens          (2,4)
canplace        (2,0)
2==0    2==2
                no
canplace        (2,1)
2==1    2==1
0==1    1==1
                no
canplace        (2,2)
2==2    2==0
                no
canplace        (2,3)
2==3    2==1
0==3    1==3
        yes     x[2]=3

Nquens          (3,4)
canplace        (3,0)
2==0    3==2
0==0    2==0
                no
canplace        (3,1)
2==1    3==1
0==1    2==1
3==1    1==2
        yes     x[3]=1

posible way
2|0|3|1|
board

*|*|Q|*|
--------
Q|*|*|*|
--------
*|*|*|Q|
--------
*|Q|*|*|
--------                no
canplace        (3,2)
2==2    3==0
                no
canplace        (3,3)
2==3    3==1
0==3    2==3
3==3    1==0
                no
                no
                no
canplace        (1,1)
2==1    1==1
                no
canplace        (1,2)
2==2    1==0
                no
canplace        (1,3)
2==3    1==1
                no
                no
canplace        (0,3)
        yes     x[0]=3

Nquens          (1,4)
canplace        (1,0)
3==0    1==3
        yes     x[1]=0

Nquens          (2,4)
canplace        (2,0)
3==0    2==3
0==0    1==0
                no
canplace        (2,1)
3==1    2==2
                no
canplace        (2,2)
3==2    2==1
0==2    1==2
        yes     x[2]=2

Nquens          (3,4)
canplace        (3,0)
3==0    3==3
                no
canplace        (3,1)
3==1    3==2
0==1    2==1
2==1    1==1
                no
canplace        (3,2)
3==2    3==1
0==2    2==2
                no
canplace        (3,3)
3==3    3==0
                no
                no
canplace        (2,3)
3==3    2==0
                no
                no
canplace        (1,1)
3==1    1==2
        yes     x[1]=1

Nquens          (2,4)
canplace        (2,0)
3==0    2==3
1==0    1==1
                no
canplace        (2,1)
3==1    2==2
                no
canplace        (2,2)
3==2    2==1
1==2    1==1
                no
canplace        (2,3)
3==3    2==0
                no
                no
canplace        (1,2)
3==2    1==1
                no
canplace        (1,3)
3==3    1==0
                no
                no

The n-Queens Problem

import java.util.*; //to import Scanner class for take the value from user of the chess board

public class quen{

int[] x=new int[16]; //allocate a location for array storage

5 Ways a Personal Blog Can Boost Your Career

When I first graduated from business school, I leveraged our school's alumni network to seek advice on securing my first job. One successful businessperson I spoke to advised that starting a blog would be one of the best things I could do to advance in my career. Looking back,
I completely agree with this advice. Building a blog is one of the best tools for getting started and advancing in your career field. If you don't have a personal blog yet, I hope to provide some concrete reasons in this article on why you must start one today.

1. Personal Branding
The idea of the personal brand that was coined by Tom Peters in 1997 has been greatly accelerated by the Internet which connects everyone and provides a platform for easy self publishing of content that can be broadcast to a large audience for free. By producing great content on your blog, you will establish an online presence that will strengthen your personal brand. For example, Dan Schawbel created a blog called The Personal Branding Blog which grew to thousands of monthly readers and established Dan as the expert on personal branding for Generation Y professionals while resulting in a book deal and national recognition.

2. Get Found Online
A pro tip when starting a personal blog is register your name as the domain. A good example is www.ChrisBrogan.com. Google strongly favors websites with the exact keyword phrase in the domain, so you will have a strong chance of ranking number one in Google for your name if you secure an exact match domain and create worthwhile content. If the .com domain for your name is not available, the .org is a good alternative. When people search Google for your name you will be able to attract visitors to your blog and communicate a focused message about who you are and what you offer. Generally, the more great articles you write on your blog, the more traffic you will attract from search engines like Google or Bing.
3. Knowledge Advancement
If you are regularly blogging and want to add value to readers, you will have to know what you are writing about to explain your ideas effectively and not embarrass yourself. This requires reading other blogs, books, and industry publications in your field to have the sufficient knowledge to support your ideas. Increasing your knowledge in your field can be invaluable in your career, and a blog can motivate you to spend more time learning what you should know.

4. Relationship Building
Blogs are inherently interactive because anyone can start a conversation with you by leaving a comment on an article. You can often meet people in your industry who leave insightful comments on your blog. Follow up with these people via email or LinkedIn. Contributing thoughtful comments on the blogs of people in your industry can get the attention of influential people in your field. A couple great blogging tactics is to interview people on your blog or write guest articles on influential blogs, which can both help develop valuable relationships.

5. Demonstration of Skill
Some people have suggested that a personal blog will someday replace the resume. Although this is far from reality in 2012, a blog can provide a lot more information for employers than a resume. A blog shows how you think, demonstrates your communication skills, and showcases the quality of your ideas. If you are able to build a substantial audience, this can be a great example of your online marketing acumen or your ability to execute a successful project.

Charles Sipe is the Executive Editor of Masters In Accounting, a career resource site for students interested in pursuing a masters in accounting degree.