hashtable.java

自己上学编的Hashtable的java源码

import java.io.*;
import java.math.BigInteger;
import java.util.*;

/*
 * Implements a Hash-Table structure as introduced in the 
 * lecture to store the information read by the RFID 
 * readers in the library.
 *	
 * Make sure that you have tested all the given test cases
 * given on the homepage before you submit your solution.
 *
 * More information is found on: 
 * http://www.deeds.informatik.tu-darmstadt.de/teaching/courses/SS08/ICS2/labs.html
 * 
 * @author Kun Fang
 */



public class HashTable {
	
	private int Functiontype;
	private int collisionResolutiontype;
	private int capacity;
	private int size;
	private Entry[] entries;
	
    /**
	 * The constructor
	 * 
	 * @param initialCapacity
	 *            represents the initial size of the Hash Table.
	 * @param hashFunction
	 *            can have the following values: division folding mid_square
	 * @param collisionResolution
	 *            can have the following values: linear_probing
	 *            quadratic_probing
	 * 
	 * The Hash-Table itself should be implemented as an array of entries
	 * (Entry[] in Java) and no other implementation will be accepted. When the
	 * load factor exceeds 75%, the capacity of the Hash-Table should be
	 * increased as described in the method rehash below. We assume a bucket
	 * factor of 1.
	 */
    public HashTable(int k, String hashFunction, String collisionResolution) {
    	capacity = k;
    	size = 0;
    	entries = new Entry[k];
    	
    	if(hashFunction.equals("division"))
    		Functiontype = 1;
    	else if(hashFunction.equals("folding"))
    		Functiontype = 2;
    	else if(hashFunction.equals("mid_square"))
    		Functiontype = 3;
    	else {
    		Functiontype = 0;
    		System.out.println("unvalid hashFunctiontype!");
    	}
    	
    	if(collisionResolution.equals("linear_probing"))
    		collisionResolutiontype = 1;
    	else if(collisionResolution.equals("quadratic_probing"))
    		collisionResolutiontype = 2;
    	else {
    		collisionResolutiontype = 0;
    		System.out.println("unvalid collisionResolutiontype!");
    	}
    }

    /**
	 * This method takes as input the name of a file containing a sequence of
	 * entries that should be inserted into the Hash-Table in the order they
	 * appear in the file. You cannot make any assumptions on the order of the
	 * entries nor is it allowed to change the order given in the file. You can
	 * assume that the file is located in the same directory as the executable
	 * program. The input file is similar to the input file for lab 1. The
	 * return value is the number of entries successfully inserted into the
	 * Hash-Table.
	 * 
	 * @param filename
	 *            name of the file containing the entries
	 * @return returns the number of entries successfully inserted in the
	 *         Hash-Table.
	 */
    public int loadFromFile (String filename) {
    	//data represent the orignal text file 
		Vector<String> data = new Vector<String>();
        //read file
		try {
			FileReader fr = new FileReader(filename);
			BufferedReader in = new BufferedReader(fr);

			String line;
			while ((line = in.readLine()) != null) {
				data.add(line);
			}
			in.close();
			fr.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();

		} catch (IOException e) {
			e.printStackTrace();
		}
		
		int j;
		String[] info;
		Entry en;
		size = 0;
		for (int i = 0; i < data.size(); i++) {
			info = new String[3];
			j = 0;
			String s = data.elementAt(i);
			StringTokenizer x = new StringTokenizer(s, ";");
			while (x.hasMoreTokens() && j < 3) {
				info[j++] = x.nextToken();
			}
			en = new Entry(info[0],info[1],info[2]);
			insert(en);
			
		}
		return size;
    }
    
    /**
	 * This method inserts the entry insertEntry into the Hash-Table. Note that
	 * you have to deal with collisions if you want to insert an entry into a
	 * slot which is not empty. This method returns true if the insertion of the
	 * entry insertEntry is successful and false if the key of this entry
	 * already exists in the Hash-Table (the existing key/value pair is left
	 * unchanged).
	 * 
	 * @param insertEntry
	 *            entry to insert into the Hash-table
	 * @return returns true if the entry insertEntry is successfully inserted
	 *         false if the entry already exists in the Hash-Table
	 */
    public boolean insert(Entry insertEntry) {
    	Long x;
    	String s = new String();
    	
        if(find(insertEntry.getKey()) == null) {
        	
        	if (4 * size >= 3 * capacity) {
        		rehash();
        		return insert(insertEntry);
        	}        	
        //division hashFunction
        	if(Functiontype == 1) {

        		for(int t = 0 ; t < 5 ; t++)
        			s  += String.valueOf((int)(insertEntry.getKey().charAt(t)));
        		x = Long.valueOf(s);
        		int y = (int) (x % capacity);
        		set(insertEntry , y);
        	}
        
        //folding hashFunction
        	else if(Functiontype == 2) {
        		
        		for(int t = 0 ; t < 5 ; t++)
        			s  += String.valueOf((int)(insertEntry.getKey().charAt(t)));
        		x = Long.valueOf(s);
        		
        		int a , b = 0, i = 0;
        		while(x > 0) {
        			a = (int) (x % 10);
        			if(i % 6 == 2 || i % 6 == 3)
        				a *= 100;
        			if(i % 6 == 1 || i % 6 == 4)
        				a *= 10;
        			b += a;
        			x /= 10;
        			i++;
        		}
        		set(insertEntry , (b % 1000) % capacity);
        	}
        	
        //mid_square hashFunction
        	else if(Functiontype == 3) {
        		
        		
        		for(int t = 0 ; t < 5 ; t++)
        			s  += String.valueOf((int)(insertEntry.getKey().charAt(t)));
        		x = Long.valueOf(s);
        		BigInteger x1 = BigInteger.valueOf(x);
        		x1 = x1.multiply(x1);
        		BigInteger x2 = BigInteger.valueOf(1000000000);
        		x1 = x1.divide(x2);
        		x2 = BigInteger.valueOf(1000);
        		x1 = x1.mod(x2);
        		set(insertEntry , x1.intValue() % capacity);
        	}
        	else
        		return false;
        	
        	size++;
        	return true;
        }
    	return false;
    }
    
    /**
	 * This method inserts the entry insertEntry into the Hash-Table. 
	 * 
	 * @param insertEntry
	 *            entry to insert into the Hash-table
	 *        position 
	 *        	  the position try to insert
	 */
    public void set(Entry insertEntry, int position) {
    	
    	if(entries[position] == null || entries[position].mark.equals("delete")) {
    		entries[position] = insertEntry;
    		entries[position].setmark("aktive");
    	}
    	
    	//linear_probing
    	else if(collisionResolutiontype == 1) {
    		Entry en = new Entry();
    		en = insertEntry;
    		en.root.add(String.valueOf(position));
    		if(position + 1 >= capacity)
    			set(en, position + 1 - capacity);
    		else
    			set(en, position + 1);
    	}
    	
    	//quadratic_probing
    	else if(collisionResolutiontype == 2) {

    		quad(insertEntry, position, 2);
    	}
    }
    
    /**
	 * This method is to deal with collision with quadratic_probing
	 * 
	 * @param insertEntry
	 *            entry to insert into the Hash-table
	 *        position 
	 *        	  last position try to insert
	 *        i
	 *        	  quadratic_probing control number
	 */
    public void quad(Entry insertEntry, int position,int i) {
    	int j = (i/2) * (i/2);
    	if(i % 2 == 1)
			j = j *(-1);
    	j = position - j;
		while(j < 0)
			j = capacity + j;
		while(j > capacity)
			j = j - capacity;
		
		Entry en = insertEntry;
		en.root.add(String.valueOf(position));
		
    	if(entries[j] == null || entries[j].mark.equals("delete")) {    		
    		entries[j] = insertEntry;
    		entries[j].setmark("aktive");
    	}
    	else {
    		quad(en, j, i + 1);
    	}
    }
    
    /**
	 * This method deletes the entry from the Hash-Table, having deleteKey as
	 * key This method returns the entry, having deleteKey as key if the
	 * deletion is successful and null if the key deleteKey is not found in the
	 * Hash-Table.
	 * 
	 * @param deleteKey
	 *            key of the entry to delete from the Hash-Table
	 * @return returns the deleted entry if the deletion ends successfully null
	 *         if the entry is not found in the Hash-Table
	 */
    public Entry delete(String deleteKey) {
    	for(int i = 0 ; i < capacity ; i++)
    		if(entries[i] != null && entries[i].getKey().equals(deleteKey)) {
    			entries[i].setmark("delete");
    			size--;
    			return entries[i];
    		}
    	return null;
    }

    /**
	 * This method searches in the Hash-Table for the entry with key searchKey.
	 * It returns the entry, having searchKey as key if such an entry is found,
	 * null otherwise.
	 * 
	 * @param searchKey
	 *            key of the entry to find in the Hash-table
	 * @return returns the entry having searchKey as key if such an entry exists
	 *         null if the entry is not found in the Hash-Table
	 */
    public Entry find(String searchKey) {
    	for(int i = 0 ; i < capacity ; i++)
    		if(entries[i] != null && !(entries[i].mark.equals("delete")))
    			if(entries[i].getKey().equals(searchKey))
    				return entries[i];
    	return null;
    }
    
    /**
	 * This method returns a Vector<String> containing the output Hash-Table.
	 * The output should be directly interpretable dot code. Each item in the
	 * Vector corresponds to one line of the output Hash-Table. The nodes of the
	 * output Hash-Table should contain the keys of the entries and also the
	 * data.
	 * 
	 * @return returns the output Hash-Table in directly interpretable dot code
	 */    
    public Vector<String> getHashTable() {
    	if(entries != null) {
    		Vector<String> temp = new Vector<String>();
    		temp.add("Digraph{");
    		temp.add("nodesep=.05;");
    		temp.add("rankdir=LR;");
    		temp.add("node[shape=record,height=.1];");
    		
    		String s = new String("ht[label=\"<f0>0");
    		for(int i = 1 ; i < capacity ; i++) 
    			s += "|<f" + String.valueOf(i) + ">" + String.valueOf(i);
    		s += "\"]";
    		temp.add(s);
    		
    		int j = 1;
    		for(int i = 0 ; i < capacity ; i++)
    			if(entries[i] != null && entries[i].mark.equals("aktive")) {
    				s = new String("node" + String.valueOf(j) + "[label=\"{<l>" + entries[i].getKey()
    						+ "|" + entries[i].getData());
    				for(String ss : entries[i].root)
    				if(ss != null) {
    					s += "|";
    					break;
    				}
    				for(String ss : entries[i].root)
    						s += ss + ",";
    				
    				s += "}\"];";
    				temp.add(s);
    				temp.add("ht:f" + String.valueOf(i) + "->node" + String.valueOf(j) + ":l;");
    				j++;
    			}    				

    		temp.add("}");
    		return temp;
    	}
    	return null;
    }

    

    /**
	 * This method returns a Vector<Entry>. The returned vector contains the
	 * entries of the Hash-Table in ascending order.
	 * 
	 * @return returns the entries stored in the Hash_Table in ascending order
	 */
    public Vector<Entry> getSorted() {
    	int i, j;
    	Vector<Entry> temp = new Vector<Entry>();
    	Entry en1, en2;
    	
    	for(i = 0 ; i < capacity ; i++) 
    		if(entries[i].mark.equals("aktive"))
    			temp.add(entries[i]);
    	for(i = temp.size() - 1 ; i > 0 ; i--)
    		for(j = 0 ; j < i; j++)    			
    			if(temp.elementAt(j).getKey().compareTo(temp.elementAt(j+1).getKey()) > 0) {
    				en1 = temp.elementAt(j);
        			en2 = temp.elementAt(j+1);
        			temp.setElementAt(en2,j);
					temp.setElementAt(en1,j+1);
    			}
    	return temp;
    }

    /**
	 * This method increases the capacity of the Hash-Table and reorganizes it,
	 * in order to accommodate and access its entries more efficiently. This
	 * method is called automatically when the load factor exceeds 75%. To
	 * increase the size of the Hash-Table, you multiply the actual capacity by
	 * 10 and search for the closest primary number less than the result of this
	 * multiplication. For example if the actual capacity of the Hash-Table is
	 * 101, the capacity will be increased to 1009, which is the closest primary
	 * number less than (101*10).
	 */    
    private void rehash() {
    	size = 0;
    	Entry[] temp = new Entry[capacity];
    	temp = entries;
    	int j = capacity;
    	capacity = NextPrime( 10*capacity );
    	entries = new Entry[capacity];
    	
    	for(int i = 0 ; i < j ; i++) 
    		if(temp[i] != null && temp[i].mark.equals("aktive"))
    			insert(temp[i]);
    }
    
    /**
	 * This method find first bigger prime as given 
	 * 
	 * @param N  given number
	 * 
	 * @return returns the first bigger prime as given
	 */
    private int NextPrime ( int N ) {
        if ( N % 2 == 0 ) N--;           //even is not prime
        for ( ; !IsPrime (N); N-=2 ); 	 //not prime,continue to call itself
        return N;
    }

    /**
	 * This method test if the given number is a prime
	 * 
	 * @param N  given number
	 * 
	 * @return returns 	true  N is a prime
	 * 					false N is not a prime
	 */
    private boolean IsPrime ( int N ) {
    	
        for ( int i = 3; i*i <= N; i += 2 )
            if ( N % i == 0 ) return false; 	//not prime,return false
        return true;                                 //is prime,return true
    }
}