資料結構--解決散列沖突，分離連結法

散清單的實作經常叫做散列。

散列是一種用以常數平均時間運作插入。删除，和查找的技術。可是那些須要元素資訊排序的樹操作不會得到支援。

是以比如findMax,findMin以及排序後周遊這些操作都是散列不支援的。

假設當一個元素被插入時與已經插入的元素散列（比方散清單的數組序号，非常多元素插入到同一個數組序号中）。那麼就會産生一個沖突，這個沖突須要消除。解決沖突的辦法有兩種：

1 分離連結法

2  開放定址法（包含線性探測，平方探測，雙散列）

兩者都有可能須要再散列

以下說明分離連結法，上代碼：

package com.itany.separatechainning;

import java.util.LinkedList;
import java.util.List;

/*
 *解決沖突的第一個方法時分離連結法 其做法是将散列到同一個值得全部元素保留到一個表中
 *為運作一次查找 我們通過散列函數來決定到底周遊哪一個連結清單，然後我們再在被确定的連結清單中運作一次查找
 *散清單存儲一個List連結清單數組 
 */
public class SeparateChainingHashTable<T>
{
    private static final int DEFAULT_TABLE_SIZE=101;
    //我們定義散清單的填裝因子：散清單中元素個數和散清單大小的比  這裡是1 即集合連結清單的平均長度是1
    private int currentSize;
    private List<T>[] theLists;
    public SeparateChainingHashTable()
    {
        this(DEFAULT_TABLE_SIZE);
    }
    public SeparateChainingHashTable(int size)
    {
        //對數組中的List進行初始化
        theLists=new LinkedList[nextPrime(size)];
        for(int i=0;i<theLists.length;i++)
        {
            theLists[i]=new LinkedList<T>();
        }
    }
    public void makeEmpty()
    {
        for (List<T> list : theLists)
        {
            list.clear();
        }
        currentSize=0;
    }
    public void insert(T t)
    {
        List<T> whichList=theLists[myHash(t)];
        if(!contains(t))
        {
            whichList.add(t);
            currentSize++;
            if(currentSize>theLists.length)
                reHash();
        }
    }
    public boolean contains(T t)
    {
        //通過myHash找出是哪一個集合
        List<T> whichList=theLists[myHash(t)];
        return whichList.contains(t);
    }
    public void remove(T t)
    {
        List<T> whichList=theLists[myHash(t)];
        if(contains(t))
        {
            whichList.remove(t);
            currentSize--;
        }
    }
    private int myHash(T t)
    {
        int hash=t.hashCode();
        //對每個t得到數組的序号 大小從0-theLists.length-1 進行配置設定
        hash%=theLists.length;
        //防止hash值為負數
        if(hash<0)
            hash+=theLists.length;
        return hash;
    }
    //有一種情況是currentSize>theLists.length 須要對數組進行擴容 即再散列
    //由于清單裝的太滿 那麼操作時間将會變得更長。且插入操作可能失敗  此時的方法時建立另外一個兩倍大的表
    //并且使用一個新的相關的散列函數(由于計算時tableSize變了)，掃描整個原始散清單，計算每個元素的新散列值   并将它們插入到新表中
    private void reHash()
    {
        List<T>[] oldLists=theLists;//複制一下一會要用    theLists在又一次new一個
        theLists=new LinkedList[nextPrime(2*theLists.length)];
        for(int i=0;i<theLists.length;i++)
        {
            theLists[i]=new LinkedList<T>();
        }
        //把原來的元素拷貝到新的數組中  注意是把集合中的元素複制進去
        for(int i=0;i<oldLists.length;i++)
        {
            for (T t : oldLists[i])
            {
                insert(t);
            }
        }

    }
    //表的大小是一個素數 這能夠保證一個非常好的分布
    //是否是素數
    private static boolean isPrime(int num)
    {
        int i=1;
        while((num%(i+1))!=0)
        {
            i++;
        }
        if(i==num-1)
        {
            return true;
        }
        else 
        {
            return false;
        }
    }


    private static int nextPrime(int num)
    {
        while(!isPrime(num))
        {
            num++;
        }
        return num;
    }

}      

package com.itany.separatechainning;

//能夠放在散清單中的Employee類的樣例
/*
 * 想把類放在散清單中 必須提供兩個方法。一個是equals方法 由于要在list的集合中進行查找contains方法時會用到equals進行比較
 * 另一個是hashCode方法  由于須要通過它來找出Employee對象該放在哪一個集合中（找出數組的相應序号）
 */

public class Employee
{
    private String name;
    public Employee(String name)
    {
        this.name=name;
    }
    @Override
    public boolean equals(Object obj)
    {
        return obj instanceof Employee && name.equals(((Employee)obj).name);
    }
    public int hashCode()
    {
        //String類是有自己的hashCode方法
        return name.hashCode();
    }
    /*
     * String類自己的hashCode方法
     * public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
     */
}      

package com.itany.separatechainning;

public class Test
{

    public static void main(String[] args)
    {
        Employee e1=new Employee("zhangsan");
        Employee e2=new Employee("lisi");
        Employee e3=new Employee("wangwu");
        Employee e4=new Employee("zhaoliu");
        SeparateChainingHashTable<Employee> sc=new SeparateChainingHashTable<Employee>();
        System.out.println(sc.contains(e1));
        sc.insert(e1);
        System.out.println(sc.contains(e1));
        sc.remove(e1);
        System.out.println(sc.contains(e1));

    }

}      

結果：

false

true