哈希表-線性探測插入删除

插入删除接近常量，大o表示法最快的方式

哈希表查詢也快,但是底層存儲結構是數組，一旦建立無法改變大小

哈希表無法用來有序周遊

沖突的解決方法：開放位址法（線性探測，二次探測，再哈希）和鍊位址法

//資料項(key值)
public class DataItem {
    private int iData;
    public DataItem(int ii) {
        iData=ii;
    }
    public int getkey() {
        return iData;
    }
    

}      

//哈希表
public class HashTable {
    private DataItem[] hashArray;//數組
    private int arraySize;//哈希表的大小
    private DataItem nonItem;//标志删除之後，該位置存入的資料項
    public HashTable(int size) {//初始化
        arraySize=size;
        hashArray=new DataItem[arraySize];
        nonItem=new DataItem(-1);
    }
    //列印
    public void displayTable() {
        System.out.print("table:");
        for(int j=0;j<arraySize;j++)
            if(hashArray[j]!=null)
                System.out.print(hashArray[j].getkey()+" ");
            else//如果沒有值，就列印**
                System.out.print("** ");
    }
    //哈希化
    public int hashFunc(int key) {
        return key%arraySize;
    }
    //插入
    public void insert(DataItem item) {
        int key=item.getkey();
        int hashVal=hashFunc(key);//哈希化
        //線性探測插入
        while(hashArray[hashVal]!=null &&  hashArray[hashVal].getkey()!=-1)//如果不是空的,也不是删除之後可以插入的
            {hashVal++;//目前位置被占，尋找下一個位置
             hashVal=hashVal%arraySize;//保證沒有超出索引
            }
        hashArray[hashVal]=item;
        
            
        
    }
    //删除(需要判斷哈希化後的位置有值.并且key是不是那個值)
    public DataItem delete(int key) {
        int hashVal=hashFunc(key);
        while(hashArray[hashVal]!=null) {
            if(hashArray[hashVal].getkey()==key) {
                DataItem temp=hashArray[hashVal];
                hashArray[hashVal]=nonItem;
                return temp;
            }
            hashVal++;
            hashVal=hashVal%arraySize;
        }
        return null;//沒有找到
    }
    //查找
    public DataItem find(int key) {
        int hashVal=hashFunc(key);
        while(hashArray[hashVal]!=null) {
            if(hashArray[hashVal].getkey()==key) {
    
                return hashArray[hashVal];
            }
            hashVal++;
            hashVal=hashVal%arraySize;
        }
        return null;
    }
    
    
    
    
    
    
    
    
    
    
    
    

    
    

}      

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Test {
    public static void main(String [] agrs) throws IOException {
        DataItem aDataItem;
        int akey,size,n,keysPerCell;
        System.out.print("Enter:");
        size=getInt();
        System.out.println("初始化：");
        n=getInt();
        keysPerCell=10;
        HashTable theHashTable=new HashTable(size);
        for(int j=0;j<n;j++) {
            akey=(int)(java.lang.Math.random()*keysPerCell*size);
            aDataItem=new DataItem(akey);
            theHashTable.insert(aDataItem);
        }
        while(true) {
            System.out.print("Enter first of show,isnert,delete ,find:");
            char choice=getChar();
            switch(choice){
                case 's':
                    theHashTable.displayTable();
                    break;
                case 'i':
                    System.out.print("insert：");
                    akey=getInt();
                    aDataItem=new DataItem(akey);
                    theHashTable.insert(aDataItem);
                    break;
                case 'd':
                    System.out.println("輸入要删除的key");
                    akey=getInt();
                    theHashTable.delete(akey);
                    break;
                case 'f':
                    System.out.println("輸入要查找的key");
                    akey=getInt();
                    aDataItem=theHashTable.find(akey);
                    if(aDataItem!=null)
                        System.out.println("found"+akey);
                    else
                        System.out.println("沒有找到");
                    break;
                    default:
                        System.out.println("無效的輸入");
            }
        }
        
        
        
    }
    public static String getString() throws IOException{
        InputStreamReader isr=new InputStreamReader(System.in);
        BufferedReader br=new BufferedReader(isr);
        return br.readLine();
    }
    public static char getChar() throws IOException{
        return getString().charAt(0);
    }
    public static int getInt() throws IOException{
        return Integer.parseInt(getString());
    }

}      

轉載于:https://www.cnblogs.com/S-Mustard/p/7717264.html