Go语言视频零基础入门到精通

javalearner

这个实例说明了如何写自已的哈希表，这是一种产生冲突时线性查找的方法,下面是代码
    package arithmetic;
    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
    /**
* 数据项类
* 用来表示数据
* @author 星情
*
*/
class DataItem {
     private int iData = 0;
     
     public DataItem(int iData) {
         this.iData = iData;
     }
     
     public int getKey() {
         return iData;
     }
}
    /**
* 产生聚集时使用的线性查找
* @author 星情
*
*/
class HashTable {
     //数组
     private DataItem[] hashArray = null;
     //数组大小
     private int arraySize = 0;
     private DataItem nonItem = null;
     
     /**
      * 哈希表初始化
      * 其中设定一个占位项,即没有实际这样的数值,但是占位进行操作的一项
      * @param size 初始化大小
      */
     public HashTable(int size) {
         arraySize = size;
         hashArray = new DataItem[arraySize];
         nonItem = new DataItem(-1);
     }
     
     /**
      * 打印输出结果
      *
      */
     public void displayTable() {
         System.out.println("Table:");
         for (int i = 0; i < arraySize; i++) {
             if (hashArray != null)
                 System.out.print(hashArray.getKey() + " ");
             else
                 System.out.print("** ");
         }
         System.out.println();
     }
     
     /**
      * 哈希函数,计算哈希码
      * @param key 一个用来转换为哈希码的数字,这里就是DataItem的key
      * @return 哈希码
      */
     private int hashFunc(int key) {
         return key % arraySize;
     }
     
     /**
      * 插入新的元素
      * @param item 要插入的元素,必须是DataItem类型的
      */
     public void insert(DataItem item) {
         //获得DataItem的key
         int key = item.getKey();
         //通过哈希函数计算出哈希码
         int hashVal = this.hashFunc(key);
         
         //寻找能插入该元素的位置
         //这个位置不能为空,也不能是占位的那个元素,即nonItem
         while (hashArray[hashVal] != null && hashArray[hashVal] != nonItem) {
             hashVal++;
             //当线性查找到末尾的时候,应该从头查找
             //这句等于if(hashVal == arraySize) hashVal = 0;
             hashVal %= arraySize;
         }
         hashArray[hashVal] = item;
     }
     
     /**
      * 删除指定的元素
      * @param key 要删除的DataItem的值
      * @return 删除的元素,如果删除没有成功,则返回null
      */
     public DataItem delete(int key) {
         //计算哈希码
         int hashVal = this.hashFunc(key);
         
         //线性查找,直到找到空元素为止
         while (hashArray[hashVal] != null) {
             //找到指定元素,将该元素存入一个临时变量等待返回,并把这个变量设为占位变量--nonItem
             if (hashArray[hashVal].getKey() == key) {
                 DataItem temp = hashArray[hashVal];
                 hashArray[hashVal] = nonItem;
                 return temp;
             }
             //循环条件,哈希码++,并且如果到达尾端,从0开始
             hashVal++;
             hashVal %= arraySize;
         }
         //没有找到元素的情况,while退出,返回null
         return null;
     }
     
     /**
      * 查找某元素
      * @param key 要查找元素的值
      * @return 返回找到的元素DataItem类型,如果没有找到,则返回null
      */
     public DataItem find(int key) {
         //计算哈希码
         int hashVal = this.hashFunc(key);
         
         while (hashArray[hashVal] != null) {
             if (hashArray[hashVal].getKey() == key)
                 return hashArray[hashVal];
             //循环条件,哈希码++,并且如果到达尾端,从0开始
             hashVal++;
             hashVal %= arraySize;
         }
         return null;
     }
}
    class HashTableApp
{
public static void main(String[] args) throws IOException
    {
    DataItem aDataItem;
    int aKey, size, n, keysPerCell;
                                  // get sizes
    System.out.print("Enter size of hash table: ");
    size = getInt();
    System.out.print("Enter initial number of items: ");
    n = getInt();
    keysPerCell = 10;
                                  // make table
    HashTable theHashTable = new HashTable(size);
       for(int j=0; j<n; j++)        // insert data
       {
       aKey = (int)(java.lang.Math.random() *
                                       keysPerCell * size);
       aDataItem = new DataItem(aKey);
       theHashTable.insert(aDataItem);
       }
       while(true)                   // interact with user
       {
       System.out.print("Enter first letter of ");
       System.out.print("show, insert, delete, or find: ");
       char choice = getChar();
       switch(choice)
          {
          case "s":
             theHashTable.displayTable();
             break;
          case "i":
          System.out.print("Enter key value to insert: ");
             aKey = getInt();
             aDataItem = new DataItem(aKey);
             theHashTable.insert(aDataItem);
             break;
          case "d":
             System.out.print("Enter key value to delete: ");
             aKey = getInt();
             theHashTable.delete(aKey);
             break;
          case "f":
             System.out.print("Enter key value to find: ");
             aKey = getInt();
             aDataItem = theHashTable.find(aKey);
             if(aDataItem != null)
                {
                System.out.println("Found " + aKey);
                }
             else
                System.out.println("Could not find " + aKey);
             break;
          default:
             System.out.print("Invalid entry
");
          } // end switch
       } // end while
    } // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
    {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    String s = br.readLine();
    return s;
    }
//--------------------------------------------------------------
public static char getChar() throws IOException
    {
    String s = getString();
    return s.charAt(0);
    }
//-------------------------------------------------------------
public static int getInt() throws IOException
    {
    String s = getString();
    return Integer.parseInt(s);
    }
//--------------------------------------------------------------
} // end class HashTableApp
////////////////////////////////////////////////////////////////
    再哈希化
    /**
* 注意的是,表的容量是一个质数
* 因为当再哈希化(二次探测也一样)的时候,探测位置达到数组最大值就得从头开始,这样做是为了防止陷入死循环
* 例如:
*     表的容量是15,步长为5,探测位置是0, 5, 10, 0, 5, 10....死循环
*     表的容量是13(质数),步长为5,探测位置是0, 5, 10, 2, 7, 12, 4...会遍历每个位置
* @author 星情
*
*/
class HashTable {
     private DataItem[] hashArray = null;
     private int arraySize = 0;
     private DataItem nonItem = null;
     
     public HashTable(int size) {
         this.arraySize = size;
         hashArray = new DataItem[arraySize];
         nonItem = new DataItem(-1);
     }
     
     public void displayTable() {
         System.out.print("Table: ");
         for (int i = 0; i < hashArray.length; i++) {
             if (hashArray != null)
                 System.out.print(hashArray.getKey() + " ");
             else
                 System.out.print("* ");
         }
         System.out.println();
     }
     
     public int hashFunc1(int key) {
         return key % arraySize;
     }
     
     public int hashFunc2(int key) {
         return 5 - key % 5;
     }
     
     public void insert(int key) {
         DataItem item = new DataItem(key);
         int hashVal = this.hashFunc1(key);
         int stepSize = this.hashFunc2(key);
         
         if (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
             hashVal += stepSize;
             hashVal %= stepSize;
         }
         hashArray[hashVal] = item;
     }
     
     public DataItem delete(int key) {
         int hashVal = this.hashFunc1(key);
         int stepSize = this.hashFunc2(key);
         
         while (hashArray[hashVal] != null) {
             if (hashArray[hashVal].getKey() == key) {
                 DataItem temp = hashArray[hashVal];
                 hashArray[hashVal] = nonItem;
                 return temp;
             }
             hashVal += stepSize;
             hashVal %= stepSize;
         }
         return null;
     }
     
     public DataItem find(int key) {
         int hashVal = this.hashFunc1(key);
         int stepSize = this.hashFunc2(key);
         
         while (hashArray[hashVal] != null) {
             if (hashArray[hashVal].getKey() == key)
                 return hashArray[hashVal];
             hashVal += stepSize;
             hashVal %= stepSize;
         }
         return null;
     }
}
   

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/10/29/235619234.zip