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

yy2011

这个实例说明了如何写自已的哈希表，这是一种产生冲突时线性查找的方法,下面是代码

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\n");
         } // 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;
    }
}