Java數據結構之實現哈希表的分離鏈接法

Posted on by

哈希表的分離鏈接法

原理

Hash Table可以看作是一種特殊的數組。他的原理基本上跟數組相同，給他一個數據，經過自己設置的哈希函數變換得到一個位置，並在這個位置當中放置該數據。哦對瞭，他還有個名字叫散列

0 1
數據1 數據2

就像這個數組，0號位置放著數據1，1號位置放數據2
而我們的哈希表則是通過一個函數f(x) 把數據1變成0，把數據2變成1，然後在得到位置插入數據1和數據2。
非常重要的是哈希表的長度為素數最好！！
而且當插入數據大於一半的時候我們要進行擴充！！！

沖突問題產生

現在這個表就是2個數據，所以不會產生什麼沖突，但是若一個數據他通過f(x)計算得到的位置也是0呢？是不是就跟數據1產生瞭沖突，因為數據1已經占據瞭這個位置，你無法進行插入操作。對不對。

所以我們該如何解決這個問題呢，誒，我們肯定是想兩個都可以插入是不是，就像一個炸串一樣把他串起來。如圖

在這裡插入圖片描述

a b c就像一個炸串，而如何實現這個炸串就有多種方式。這裡我們用線性表來實現

線性表實現

我們可以用java自帶的List ArrayList等表，這邊也給出單鏈表的實現方式。

public class MyArray<AnyType> {

我們首先得創建一個內部類用來存放數據，以及保存下個節點

 class ArrayNode<AnyType>{
     public AnyType data;
     public ArrayNode<AnyType> next;
     public ArrayNode(AnyType data){this(data,null);}
     private ArrayNode(AnyType data,ArrayNode<AnyType> next){
         this.data=data;
         this.next=next;
     }
 }//save type node;

設置我們這個線性表所需要的對象，例如size和一個頭節點，以及我們要進行初始化，判斷這個表是否為空等。

 private int theSize;//array list size
 private ArrayNode<AnyType> head; //head node every data behind it
 //init MyArray
 public MyArray(){doClear();}
 public void clear(){doClear();}
 private void doClear(){
     theSize=0;
     head=new ArrayNode<>(null);
 }
 //get size and is empty
 public int size(){return theSize;}
 public boolean isEmpty(){return theSize==0;}

接下來我們需要實現他的基本操作，是否包含，插入，獲得以及刪除。

   //contain
   public boolean contains(AnyType x){
       ArrayNode<AnyType> newNode=head;//get a new node=head
       while (newNode.next!=null) {
           newNode=newNode.next;
           if (newNode.data == x)
               return true;
       }
       return false;
   }
   //get the data in idx from array
   public AnyType get(int idx){return get(idx,head).data;}
   private ArrayNode<AnyType> get(int idx,ArrayNode<AnyType> node){
       if(idx<0||idx>size())
           throw new IndexOutOfBoundsException();//out of length
       ArrayNode<AnyType> newNode=node;
       //find start head.next
       for (int i = 0; i < idx; i++)
           newNode=newNode.next;
       return newNode;
   }
   //set data into array
   public void set(AnyType x){set(x,head);}
   private void set(AnyType x,ArrayNode<AnyType> node){
       ArrayNode<AnyType> newNode=node;
       while (newNode.next!=null)
           newNode=newNode.next;
       theSize++;
       newNode.next=new ArrayNode<>(x);
   }
    //remove
   public void remove(AnyType x){remove(x,head);}
   private void remove(AnyType x,ArrayNode<AnyType> node){
       if(!contains(x))
           return;
       while (node.next!=null){
           node=node.next;
           if (node.next.data==x)
               break;
       }
       ArrayNode<AnyType> oldNode=node.next;
       node.next=null;
       node.next=oldNode.next;
   }
}

哈希表實現

public class MyHashTable<AnyType>{
    //define the things that we need to use
    private static final int DEFAULT_SIZE = 10;
    private MyArray<AnyType>[] arrays;
    private int currentSize;

因為我實現的是學號的存儲
也就是帶0開頭的數據 所以我用字符串
這裡這個myHash就是我實現的簡單哈希函數，即獲得的數據字符串化，得到最後兩個字符

    private int myHash(AnyType x){
        String s=x.toString();
        return Integer.parseInt(s.substring(s.length()-2,s.length()));
    }

初始化哈希表,設置的默認大小為10，然後進行素數判斷，如果它不是素數，那麼就找到他的下一個素數作為表的大小。

    //init we should ensure that the table size is prime
    public MyHashTable(){
        ensureTable(nextPrime(DEFAULT_SIZE));
        makeEmpty();
    }
    private void ensureTable(int x){
        arrays=new MyArray[x];
        for (int i = 0; i < arrays.length; i++)
            arrays[i]=new MyArray<>();
    }
    //make the array empty
    public void makeEmpty(){
        currentSize=0;
        for(MyArray<AnyType> myArray:arrays)
            myArray.clear();
    }
    //size and empty
    public int size(){return currentSize;}
    public boolean isEmpty(){return currentSize==0;}

基本方法的實現，插入，獲得，刪除，包含

    //contain x
    public boolean contains(AnyType x){
        int position=myHash(x);
        return arrays[position].contains(x);
    }
    //insert x
    public void insert(AnyType x){
        int position=myHash(x);
        if(arrays[position].contains(x))
            return;
        else if(arrays[position].size()==0)
                if(++currentSize>arrays.length)
                    makeBigger();
        arrays[position].set(x);

    }
    //get idx data
    public MyArray<AnyType> get(int idx){ return arrays[idx];}

在這裡，如果插入的時候啦，實際的currentSize大於二分之一表的大小瞭
則進行擴充表
一般擴充表的話，我們是直接兩倍兩倍擴充的。

    //makeBigger
    public void makeBigger() {
        MyArray[] oldArray = arrays;
        arrays = new MyArray[2 * arrays.length];
        for (int i = 0; i < oldArray.length; i++)
            arrays[i] = oldArray[i];
    }

下一個素數查找，如果他是偶數，則給他加1這樣可以大大減少開銷。
然後進行下一個素數判斷，奇數當中找素數。

    //nextPrime
    private int nextPrime(int i){
        if(i%2==0)
            i++;
        for (; !isPrime(i); i+=2);//ensure i is jishu
        return i;
    }

是否為素數判斷，如果為2則范圍true
如果是1或者為偶數則返回false
都不滿足則從三開始，他的平方小於輸入的數，用奇數進行操作，因為用偶數的話，前面那個2就直接判斷瞭，所以我們用奇數，大大減少開銷。
我們也可以設置他的判斷條件是小於輸入的二分之一，但是我們用平方進行判斷大大減少瞭開銷，而且對於奇數來說是十分有效果的。

    //is Prime
    private boolean isPrime(int i){
        if(i==2||i==3)
            return true;
        if(i==1||i%2==0)
            return false;
        for (int j = 3; j*j<=i ; j+=2)
            if (i%j==0)
                return false;
        return true;
    }
}

測試

public class test {
    public static void main(String[] args) {
        MyHashTable<String> a=new MyHashTable<>();
        a.insert("001");
        a.insert("01");
        for(int i=1;i<a.get(1).size()+1;i++){
            System.out.println(a.get(1).get(i));
        }
    }
}

結果

在這裡插入圖片描述

到此這篇關於Java數據結構之實現哈希表的分離鏈接法的文章就介紹到這瞭,更多相關Java哈希表的分離鏈接法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：