knowledge For All: September 2012

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

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

knowledge For All

Hash table with separate chaining

Hash table with separate chaining