package com.wpr.collection;

import java.util.LinkedList;

import java.util.List;

public class HashTable<AnyType> {

    private static final int DEFAULT_TABLE_SIZE = 101;

    private List<AnyType>[] theList;

    private int curSize;

    public HashTable() {

        this(DEFAULT_TABLE_SIZE);

    }

    public HashTable(int size) {

        //构造一个质数长度的链表

        this.theList = new LinkedList[nextPrime(size)];

        for(int i=0;i<theList.length;i++){

            theList[i]= new LinkedList<>();

        }

    }

    /**

     * 插入，如果元素已经存在，直接返回

     * @param x

     */

    public void insert(AnyType x){

        List<AnyType> temp = theList[myHast(x)];

        if(!temp.contains(x)){

            temp.add(x);

            if(++curSize>theList.length)

                reHash();

        }

    }

    /**

     * 表的size太小，数据的长度和表长相等时重新调整表长，装填因子为1

     */

    private void reHash() {

        List<AnyType>[] old = theList;

        theList = new LinkedList[theList.length*2];

        //更新hashTable

        for(int i=0;i<theList.length;i++)

            theList[i]=new LinkedList<>();

        curSize = 0;

        for(int i=0;i<old.length;i++){

            for(AnyType x:old[i])

                insert(x);

        }

    }

    public void clear(){

        for(List l:theList){

            l.clear();

        }

    }

    public void remove(AnyType x){

        List<AnyType> temp = theList[myHast(x)];

        if(temp.contains(x)){

            temp.remove(x);

            curSize--;

        }

    }

    public boolean contain(AnyType x){

        List<AnyType> temp = theList[myHast(x)];

        return temp.contains(x);

    }

    /**

     * 计算数据的hash值

     * @param x

     * @return

     */

    private int myHast(AnyType x) {

        int hashValue = x.hashCode();

        hashValue%=theList.length;

        if(hashValue<0)

            hashValue+=theList.length;

        return hashValue;

    }

    /**

     * 返回一个比size大的质数

     * @param size

     * @return

     */

    private int nextPrime(int size) {

        if(size%2==0)

            size++;

        while(!isPrime(size)){

            size +=2;

        }

        return 0;

    }

    /**

     * 判断size是否为质数

     * @param size

     * @return

     */

    private boolean isPrime(int size) {

        if(size%2==0||size==1)

            return false;

        if(size==2 || size==3)

            return true;

        for(int i=3;i<Math.sqrt(size);i+=2){

            if(size%i==0)

                return false;

        }

        return true;

    }

}