链表实现的散列表（Java版）

客官°小女子只卖身不卖艺 2022-06-18 09:19 148阅读 0赞

public class SeparateChainingHashTable<AnyType> \{  
    private static final int DEFAULT\_TABLE\_SIZE=101;//初始化散列表的大小  
    private List<AnyType> \[\] theLists;//指向散列表的引用  
    private int currentSize;//当前插入元素的个数  
    public SeparateChainingHashTable()\{//初始化  
        this(DEFAULT\_TABLE\_SIZE);  
    \}  
    @SuppressWarnings("unchecked")  
    public SeparateChainingHashTable(int size)\{  
        theLists=new LinkedList\[nextPrime(size)\];//确定存hash值的链表的长度  
        for(int i=0;i<theLists.length;i++)  
            theLists\[i\]=new LinkedList<>();//对于每个链表中的元素，再构建一个链表用于存hash值  
    \}  
    /\*  
     \* Make the hash table logically empty  
     \*/  
    public void makeEmpty()\{  
        for(int i=0;i<theLists.length;i++)  
            theLists\[i\].clear();//把链表中的hash值清除  
        currentSize=0;  
    \}  
    /\*  
     \* 返回下一个素数  
     \*/  
    private static int nextPrime(int n)\{  
        if(n%2==0)  
            n++;  
        for(;!isPrime(n);n+=2)  
            ;  
        return n;  
    \}  
    /\*  
     \* 判断是否是素数  
     \*/  
    private static boolean isPrime(int n)\{  
        if(n==2||n==3)  
            return true;  
        if(n==1||n%2==0)  
            return false;  
        for(int i=3;i\*i<=n;i+=2)  
            if(n%i==0)  
                return false;  
        return true;  
    \}  
    /\*  
     \* 求hash值  
     \*/  
    private int myhash(AnyType x)\{  
        int hashVal=x.hashCode();  
        hashVal%=theLists.length;//因为hash值可能超过边界，所以对链表长度取余数，确保不会超过边界  
        if(hashVal<0)//防止下表越界  
            hashVal+=theLists.length;  
        return hashVal;  
    \}  
    public boolean contains(AnyType x)\{  
        List<AnyType> whichList=theLists\[myhash(x)\];//先通过hash值定位到链表中的位置  
        return whichList.contains(x);//然后再查看这个位置是否有该值  
    \}  
    public void insert(AnyType x)\{  
        List<AnyType> whichList=theLists\[myhash(x)\];  
        if(!whichList.contains(x))\{//如果不包含当前元素的话，就执行插入，否则什么都不做  
            whichList.add(x);//直接向当前链表总插入元素  
            if(++currentSize>theLists.length)//如果当前的大小已经满了，那么再散列，扩大大小  
                rehash();  
        \}  
    \}  
    /\*  
     \* 移除指定元素  
     \*/  
    public void remove(AnyType x)\{  
        List<AnyType> whileList=theLists\[myhash(x)\];//获得当前元素所在位置的引用  
        if(whileList.contains(x))\{  
            whileList.remove(x);  
            currentSize--;  
        \}  
    \}  
    /\*  
     \* Rehashing for separate chaining hash table  
     \*/  
    @SuppressWarnings("unchecked")  
    private void rehash()\{  
        List<AnyType>\[\] oldLists=theLists;//原来散列表的长度  
        theLists=new List\[nextPrime(2\*theLists.length)\];//现在散列表的长度  
        for(int j=0;j<theLists.length;j++)  
            theLists\[j\]=new LinkedList<>();//对现在散列表的每个元素再new一个链表  
        currentSize=0;  
        for(int i=0;i<oldLists.length;i++)  
            for(AnyType item:oldLists\[i\])//这里需要注意，是把每一个元素执行插入，而不是散列表元素的引用  
                insert(item);//把原来散列表中的所有元素插入新的散列表中  
    \}  
\}

测试：

public static void main(String\[\] args) \{  
        // TODO Auto-generated method stub  
        SeparateChainingHashTable<String> s=new SeparateChainingHashTable<>();  
        s.insert("hello");  
        s.insert("the");  
        s.insert("world");  
        s.insert("!");  
        s.insert("12");  
        System.out.println("当前散列表是否含有world："+s.contains("world"));  
        s.remove("world");  
        System.out.println("当前散列表是否含有world："+s.contains("world"));  
        System.out.println("当前散列表是否含有hello："+s.contains("hello"));  
        s.makeEmpty();  
        System.out.println("当前散列表是否含有hello："+s.contains("hello"));

效果：

当前散列表是否含有world：true  
当前散列表是否含有world：false  
当前散列表是否含有hello：true  
当前散列表是否含有hello：false