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

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

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

哈希表的分離鏈接法

原理

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

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

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

沖突問題產(chǎn)生

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

所以我們?cè)撊绾谓鉀Q這個(gè)問題呢，誒，我們肯定是想兩個(gè)都可以插入是不是，就像一個(gè)炸串一樣把他串起來。如圖

在這里插入圖片描述

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

線性表實(shí)現(xiàn)

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

public class MyArray<AnyType> {

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

 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è)置我們這個(gè)線性表所需要的對(duì)象，例如size和一個(gè)頭節(jié)點(diǎn)，以及我們要進(jìn)行初始化，判斷這個(gè)表是否為空等。

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

接下來我們需要實(shí)現(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;
   }
}

哈希表實(shí)現(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;

因?yàn)槲覍?shí)現(xiàn)的是學(xué)號(hào)的存儲(chǔ)
也就是帶0開頭的數(shù)據(jù) 所以我用字符串
這里這個(gè)myHash就是我實(shí)現(xiàn)的簡(jiǎn)單哈希函數(shù)，即獲得的數(shù)據(jù)字符串化，得到最后兩個(gè)字符

    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)行素?cái)?shù)判斷，如果它不是素?cái)?shù)，那么就找到他的下一個(gè)素?cái)?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;}

基本方法的實(shí)現(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];}

在這里，如果插入的時(shí)候啦，實(shí)際的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];
    }

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

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

是否為素?cái)?shù)判斷，如果為2則范圍true
如果是1或者為偶數(shù)則返回false
都不滿足則從三開始，他的平方小于輸入的數(shù)，用奇數(shù)進(jìn)行操作，因?yàn)橛门紨?shù)的話，前面那個(gè)2就直接判斷了，所以我們用奇數(shù)，大大減少開銷。
我們也可以設(shè)置他的判斷條件是小于輸入的二分之一，但是我們用平方進(jìn)行判斷大大減少了開銷，而且對(duì)于奇數(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;
    }
}

測(cè)試

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

結(jié)果

在這里插入圖片描述

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)哈希表的分離鏈接法的文章就介紹到這了,更多相關(guān)Java哈希表的分離鏈接法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: