The algorithm to insert a record into a hash table, shown in Algorithm 13.3, cal
ID: 3825467 • Letter: T
Question
The algorithm to insert a record into a hash table, shown in Algorithm 13.3, calculates the hash value of the new record from its key, which is an argument to the algorithm. On Lines 2 - 3, the key and next properties of the new record are set Line 4 checks if there are already entries in the hash table for that hash value. If there are no entries, the new record is added as the first element at that location on Lines 5 - 6. If there are entries, Lines 9 - 13 check if the record is already in the hash table. Lines 15 - 16 traverse the chain for the position where the new record will be in alphabetical order. On Lines 17 - 19, the pointers for the existing records are updated to include the new record. Pre - conditions Unused indices in the hash table are set to NULL. value is a valid hash table key value. Post - conditions Record inserted into the hash table at the correct location, as specified by the hash function. insert (value) index = hashSum(value, tablesize)//hash is calculated hashElementkey = value//set properties of new record hashElementnext = NULL hashElementprevious = NULL The steps to delete a record from a hash table, shown in Algorithm 13.4, follow the same pattern initially as the steps to insert and search for a record. The index for the element to delete is identified on Line 1 with a call to the hash function. Once the key value is found in the hash table chain, on Line 5, the next and previous pointers for the surrounding nodes in the chain are updated on Lines 6 - 8. One Line 9, the node is deleted, which frees the memory. Pre - conditions Unused indices in the hash table are NULL. value is a valid search key for a record in the hash table. Post - conditions Node with the specified key value deleted from the chain and the memory freed. Pointers in the linked list updated to bypass the deleted node. delete (value) index = hashSum (name, tableSize) if (hashTable [index].next ! = NULL)//there is a linked list. tmp = hashTable[index].next while (tmp ! = NULL) if (tmp.key = = value) tmp.previous.next = tmp.next Given the array: {Whiplash, Star Wars, The Godfather, Se7en, Beauty and the Beast} where after they were sent into the hashSum, the indexes returned were 0, 0, 2, 3, 0 respectively. Draw out a hash table based on the insert function shown in class, if the hashTable size of 4.Explanation / Answer
class HTable {
public static void main(String[] args) {
HashTable ht = new HashTable(29);
ht.insert(2116, 5);
ht.insert(1010, 400);
ht.insert(200, 20);
ht.insert(99, 71110);
ht.insert(99, 71111);
ht.insert(21161, 5);
ht.insert(10142, 400);
ht.insert(203, 20);
ht.insert(924, 71110);
ht.insert(915, 71111);
ht.insert(9198, 71111);
ht.htSearch(200);
ht.htSearch(9198);
ht.delete(9198);
ht.insert(9198, 71111);
ht.insert(9198, 71112);
ht.htSearch(9198);
ht.htSearch(77);
}
}
class HashTable {
private int tsize;
private int tcount;
private HashTableNode[] htNode;
public HashTable(int tsize) {
htNode = new HashTableNode[tsize] ;
this.tsize = tsize;
this.tcount = 0;
}
private int hash(int key){
return key%this.tsize;
}
//table of hashtable nodes
private HashTableNode getHashTableNode(int key){
HashTableNode temp = null;
HashTableNode htNode = null;
int hash = this.hash(key);
//iterate hashtable
for(int i=0;i<this.tcount;i++){
temp = this.htNode[i];
if(temp.getHash()==hash){
htNode = temp;
break;
}
}
return htNode;
}
private ListNode getList(int key){
int hash = this.hash(key);
HashTableNode htNode=null;
ListNode nList = null;
for(int i=0;i<this.tcount;i++){
htNode=this.htNode[i];
if(htNode.getHash()==hash){
if(htNode.getNcount()>0){
nList = htNode.getNlist();
}
}
}
return nList;
}
private ListNode search(int key){
ListNode node = null;
ListNode nList = null;
nList = this.getList(key);
if(nList!=null){
for(ListNode temp = nList;temp!=null;temp=temp.getNext()){
//key in the list matches with key searched
if(temp.getKey()==key){
node = temp;
break;
}
}
}
return node;
}
//search key in hashtable
public int htSearch(int key){
int value = Integer.MIN_VALUE;
ListNode node= this.search(key);
if(node!=null){
value = node.getValue();
}
if(value==Integer.MIN_VALUE){
System.out.println("key "+key+" not found!!");
}else{
System.out.println("key "+key+" found, value= "+value);
}
return value;
}
private boolean hashSearch(int key){
boolean retval = Boolean.FALSE;
int hash = this.hash(key);
HashTableNode htNode=null;
for(int i=0;i<this.tcount;i++){
htNode=this.htNode[i];
if(htNode.getHash()==hash){
retval=Boolean.TRUE;
break;
}
}
return retval;
}
public boolean insert(int key,int value){
//for each insertion increase this.tcount, if tcount==tsize dont insert hashtable is full
boolean retval = Boolean.FALSE;
int hash = this.hash(key);
HashTableNode htableNode=null;
ListNode htList = null;
ListNode temp = null;
ListNode temp1 = null;
//hash for the key exists, then insert in that list corresponding hash
if(this.hashSearch(hash)==Boolean.TRUE){
htableNode = this.getHashTableNode(hash);
htList = htableNode.getNlist();
temp = htList;
temp1 = null;
while(temp!=null){
temp1 = temp;
if(temp.getKey()==key){
System.out.println("Key "+key+" already present! overriting value "+value+"!!");
temp.setValue(value);
retval=Boolean.TRUE;
break;
}
temp = temp.getNext();
}
if(retval==Boolean.FALSE){
temp1.setNext(new ListNode(key,value));
retval=Boolean.TRUE;
}
}
else{
//
if(this.tcount<this.tsize-1){
for(int i=0;i<tcount;i++){}
//create new list
htList = new ListNode();
htList.setKey(key);
htList.setNext(null);
htList.setValue(value);
//create new hash table node
htableNode = new HashTableNode();
htableNode.setHash(hash);
htableNode.setNcount(1);
htableNode.setNlist(htList);
//put hashtable node to array of hashtableNodes in hashtable
this.htNode[tcount++] = htableNode;
retval=Boolean.TRUE;
}
else{
System.out.println("Hash Table Full!! cant insert!!! ");
}
}
if(retval==Boolean.TRUE){
System.out.println("key "+key+" inserted");
}
return retval;
}
public boolean delete(int key){
ListNode nList= this.getList(key);
ListNode temp =null;
boolean status = Boolean.FALSE;
int nodeIndex=0;
HashTableNode htableNode = null;
HashTableNode tempTNode = null;
int hash = this.hash(key);
//iterate hashtable
for(int i=0;i<this.tcount;i++){
tempTNode = this.htNode[i];
if(tempTNode.getHash()==hash){
htableNode = tempTNode;
nodeIndex = i;
break;
}
}
// HashTableNode htableNode = this.getHashTableNode(key);
if(htableNode!=null){
nList = htableNode.getNlist();
if(nList!=null){
if(nList.getKey()==key){
htableNode.setNlist(nList.getNext());
status = Boolean.TRUE;
}
else{
while(nList.getNext()!=null){
temp = nList;
if(nList.getKey()==key){
temp.setNext(nList.getNext());
status = Boolean.TRUE;
break;
}
nList = nList.getNext();
}
}
}
}
if(status==Boolean.FALSE){
System.out.println("Key "+key+" not found!!");
}else{
System.out.println("Key "+key+" deleted");
htableNode.setNcount(htableNode.getNcount()-1);
if(htableNode.getNlist()==null){
this.htNode[nodeIndex] = null;
this.tcount--;
}
}
return status;
}
public int getTsize() {
return tsize;
}
public void setTsize(int tsize) {
this.tsize = tsize;
}
public int getTcount() {
return tcount;
}
public void setTcount(int tcount) {
this.tcount = tcount;
}
public HashTableNode[] getHtNode() {
return htNode;
}
public void setHtNode(HashTableNode[] htNode) {
this.htNode = htNode;
}
}
class HashTableNode {
private int ncount;
private int hash;
private ListNode nlist;
public int getHash() {
return hash;
}
public void setHash(int hash) {
this.hash = hash;
}
public HashTableNode() {
this.ncount=0;
this.nlist=null;
}
public int getNcount() {
return ncount;
}
public void setNcount(int ncount) {
this.ncount = ncount;
}
public ListNode getNlist() {
return nlist;
}
public void setNlist(ListNode nlist) {
this.nlist = nlist;
}
}
class ListNode {
private ListNode next;
private int key;
private int value;
public ListNode() {
this.next=null;
}
public ListNode(int key,int value) {
this.next=null;
this.key=key;
this.value=value;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.