package com.ys.hash;
public class HashDouble {
    private DataItem[] hashArray;   //DataItem類，表示每個數(shù)據(jù)項信息
    private int arraySize;//數(shù)組的初始大小
    private int itemNum;//數(shù)組實際存儲了多少項數(shù)據(jù)
    private DataItem nonItem;//用于刪除數(shù)據(jù)項
    public HashDouble(){
        this.arraySize = 13;
        hashArray = new DataItem[arraySize];
        nonItem = new DataItem(-1);//刪除的數(shù)據(jù)項下標為-1
    }
    //判斷數(shù)組是否存儲滿了
    public boolean isFull(){
        return (itemNum == arraySize);
    }
    //判斷數(shù)組是否為空
    public boolean isEmpty(){
        return (itemNum == 0);
    }
    //打印數(shù)組內(nèi)容
    public void display(){
        System.out.println("Table:");
        for(int j = 0 ; j < arraySize ; j++){
            if(hashArray[j] != null){
                System.out.print(hashArray[j].getKey() + " ");
            }else{
                System.out.print("** ");
            }
        }
    }
    //通過哈希函數(shù)轉換得到數(shù)組下標
    public int hashFunction1(int key){
        return key%arraySize;
    }
    public int hashFunction2(int key){
        return 5 - key%5;
    }
    //插入數(shù)據(jù)項
    public void insert(DataItem item){
        if(isFull()){
            //擴展哈希表
            System.out.println("哈希表已滿，重新哈?；?..");
            extendHashTable();
        }
        int key = item.getKey();
        int hashVal = hashFunction1(key);
        int stepSize = hashFunction2(key);//用第二個哈希函數(shù)計算探測步數(shù)
        while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
            hashVal += stepSize;
            hashVal %= arraySize;//以指定的步數(shù)向后探測
        }
        hashArray[hashVal] = item;
        itemNum++;
    }
    /**
     * 數(shù)組有固定的大小，而且不能擴展，所以擴展哈希表只能另外創(chuàng)建一個更大的數(shù)組，然后把舊數(shù)組中的數(shù)據(jù)插到新的數(shù)組中。
     * 但是哈希表是根據(jù)數(shù)組大小計算給定數(shù)據(jù)的位置的，所以這些數(shù)據(jù)項不能再放在新數(shù)組中和老數(shù)組相同的位置上。
     * 因此不能直接拷貝，需要按順序遍歷老數(shù)組，并使用insert方法向新數(shù)組中插入每個數(shù)據(jù)項。
     * 這個過程叫做重新哈希化。這是一個耗時的過程，但如果數(shù)組要進行擴展，這個過程是必須的。
     */
    public void extendHashTable(){
        int num = arraySize;
        itemNum = 0;//重新計數(shù)，因為下面要把原來的數(shù)據(jù)轉移到新的擴張的數(shù)組中
        arraySize *= 2;//數(shù)組大小翻倍
        DataItem[] oldHashArray = hashArray;
        hashArray = new DataItem[arraySize];
        for(int i = 0 ; i < num ; i++){
            insert(oldHashArray[i]);
        }
    }
    //刪除數(shù)據(jù)項
    public DataItem delete(int key){
        if(isEmpty()){
            System.out.println("Hash Table is Empty!");
            return null;
        }
        int hashVal = hashFunction1(key);
        int stepSize = hashFunction2(key);
        while(hashArray[hashVal] != null){
            if(hashArray[hashVal].getKey() == key){
                DataItem temp = hashArray[hashVal];
                hashArray[hashVal] = nonItem;//nonItem表示空Item,其key為-1
                itemNum--;
                return temp;
            }
            hashVal += stepSize;
            hashVal %= arraySize;
        }
        return null;
    }
    //查找數(shù)據(jù)項
    public DataItem find(int key){
        int hashVal = hashFunction1(key);
        int stepSize = hashFunction2(key);
        while(hashArray[hashVal] != null){
            if(hashArray[hashVal].getKey() == key){
                return hashArray[hashVal];
            }
            hashVal += stepSize;
            hashVal %= arraySize;
        }
        return null;
    }
    public static class DataItem{
        private int iData;
        public DataItem(int iData){
            this.iData = iData;
        }
        public int getKey(){
            return iData;
        }
    }
}

package com.ys.hash;
public class SortLink {
    private LinkNode first;
    public SortLink(){
        first = null;
    }
    public boolean isEmpty(){
        return (first == null);
    }
    public void insert(LinkNode node){
        int key = node.getKey();
        LinkNode previous = null;
        LinkNode current = first;
        while(current != null && current.getKey() < key){
            previous = current;
            current = current.next;
        }
        if(previous == null){
            first = node;
        }else{
            previous.next = node;
        }
　　　　　　node.next = curent;
    }
    public void delete(int key){
        LinkNode previous = null;
        LinkNode current = first;
        if(isEmpty()){
            System.out.println("Linked is Empty!!!");
            return;
        }
        while(current != null && current.getKey() != key){
            previous = current;
            current = current.next;
        }
        if(previous == null){
            first = first.next;
        }else{
            previous.next = current.next;
        }
    }
    public LinkNode find(int key){
        LinkNode current = first;
        while(current != null && current.getKey() <= key){
            if(current.getKey() == key){
                return current;
            }
                        current = current.next;
        }
        return null;
    }
    public void displayLink(){
        System.out.println("Link(First->Last)");
        LinkNode current = first;
        while(current != null){
            current.displayLink();
            current = current.next;
        }
        System.out.println("");
    }
    class LinkNode{
        private int iData;
        public LinkNode next;
        public LinkNode(int iData){
            this.iData = iData;
        }
        public int getKey(){
            return iData;
        }
        public void displayLink(){
            System.out.println(iData + " ");
        }
    }
}

package com.ys.hash;
import com.ys.hash.SortLink.LinkNode;
public class HashChain {
    private SortLink[] hashArray;//數(shù)組中存放鏈表
    private int arraySize;
    public HashChain(int size){
        arraySize = size;
        hashArray = new SortLink[arraySize];
        //new 出每個空鏈表初始化數(shù)組
        for(int i = 0 ; i < arraySize ; i++){
            hashArray[i] = new SortLink();
        }
    }
    public void displayTable(){
        for(int i = 0 ; i < arraySize ; i++){
            System.out.print(i + "：");
            hashArray[i].displayLink();
        }
    }
    public int hashFunction(int key){
        return key%arraySize;
    }
    public void insert(LinkNode node){
        int key = node.getKey();
        int hashVal = hashFunction(key);
        hashArray[hashVal].insert(node);//直接往鏈表中添加即可
    }
    public LinkNode delete(int key){
        int hashVal = hashFunction(key);
        LinkNode temp = find(key);
        hashArray[hashVal].delete(key);//從鏈表中找到要刪除的數(shù)據(jù)項，直接刪除
        return temp;
    }
    public LinkNode find(int key){
        int hashVal = hashFunction(key);
        LinkNode node = hashArray[hashVal].find(key);
        return node;
    }
}