Java數(shù)據(jù)結(jié)構(gòu)之實現(xiàn)哈希表的分離鏈接法

更新時間：2021年06月30日 11:35:11 作者：TanGBx

今天給大家?guī)淼氖顷P(guān)于Java數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識,文章圍繞著Java哈希表的分離鏈接法展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下

哈希表的分離鏈接法

原理

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

0	1
數(shù)據(jù)1	數(shù)據(jù)2

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

沖突問題產(chǎn)生

現(xiàn)在這個表就是2個數(shù)據(jù)，所以不會產(chǎn)生什么沖突，但是若一個數(shù)據(jù)他通過f(x)計算得到的位置也是0呢？是不是就跟數(shù)據(jù)1產(chǎn)生了沖突，因為數(shù)據(jù)1已經(jīng)占據(jù)了這個位置，你無法進(jìn)行插入操作。對不對。

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

在這里插入圖片描述

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

線性表實現(xiàn)

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

public class MyArray<AnyType> {

我們首先得創(chuàng)建一個內(nèi)部類用來存放數(shù)據(jù)，以及保存下個節(jié)點

 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;

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

 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;}

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

   //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;
   }
}

哈希表實現(xiàn)

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;

因為我實現(xiàn)的是學(xué)號的存儲
也就是帶0開頭的數(shù)據(jù) 所以我用字符串
這里這個myHash就是我實現(xiàn)的簡單哈希函數(shù)，即獲得的數(shù)據(jù)字符串化，得到最后兩個字符

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

初始化哈希表,設(shè)置的默認(rèn)大小為10，然后進(jìn)行素數(shù)判斷，如果它不是素數(shù)，那么就找到他的下一個素數(shù)作為表的大小。

    //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;}

基本方法的實現(xiàn)，插入，獲得，刪除，包含

    //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大于二分之一表的大小了
則進(jìn)行擴(kuò)充表
一般擴(kuò)充表的話，我們是直接兩倍兩倍擴(kuò)充的。

    //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];
    }

下一個素數(shù)查找，如果他是偶數(shù)，則給他加1這樣可以大大減少開銷。
然后進(jìn)行下一個素數(shù)判斷，奇數(shù)當(dāng)中找素數(shù)。

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

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

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