哈希表的java实现

什么是哈希表？

1.哈希表是通过关键码key来直接进行访问的一种数据结构
2.也就是它通过关键码来值映射到表中的一个位置来访问记录，进而加快访问的速度
3.存放记录的数组叫做散列表(哈希表)

哈希表的根据解决冲突方式不同分为的两种样式

1.分离链接法

2.线性探测法

散列函数

1.什么是散列函数？

简单的说，就是已知一个值value,通过将value代入散列函数就可以知道其在散列表中所存放的位置。

2.散列函数的例子

1.一般情况下如果输入的数字是整数，那么合理的方法就是直接返回key mod tablesize,也就是散列函数是f(x)=x%tablesize
2.其中x是数值，而tablesize则是整个表的大小
3.假如x=13,tablesize=4,那么通过将x代入散列函数可以得到13 mod 4=1,那么由此可以得出13应当放在散列表的1这个下标的位置

冲突的问题

为什么会产生冲突？

1.假如同时又两个值13，和17，tablesize=4,那么将这两个值都代入散列函数，分别得到他们的下标分别是1,1。
2.你会发现他们放的位置是一样的，但是table[1]这个位置只能放一个值，咋办？如果硬放的话一个值会把另外一个值覆盖掉，肯定不行

解决冲突的方法

1.分离链接法

这种方法，比较符合直接的思路，既然冲突，我们都将这两个元素放到这个位置，摞起来不就行了，的确这是一种好方法，其实现是建立一张比较大的索引表，每一个
位置存放一个指向单链表的指针，冲突的元素依次插入这个单链表的末尾

2.开放寻址法

因为开放定址法必须放在表内，所以开放定址法所需要的表要比分离链接散列用表大。

代码的实现

分离链接法

# include <iostream>
using namespace std;
 int MAXSIZE=20000;
 int Max=19999;
typedef struct node{
    int elem;
    struct node* next;
}NODE,*PNODE;//定义节点
typedef struct hash{
    struct node** hash_table;//哈希表
}HASH;
void Init_Hash(HASH  &HS);//初始化哈希表
int  Hash_function(int n);//哈希函数
void print_Hash(HASH &HS);//打印哈希表
int main(void)
{
    HASH HS;
    Init_Hash(HS);
    print_Hash(HS);

    return 0;
}
void Init_Hash(HASH& HS)//将散列表输入数据
{
    int num;
    int site;
    cout<<"请输入"<<MAXSIZE<<"个介于0-19999的整数"<<endl;
    HS.hash_table=new PNODE[MAXSIZE];
    //初始化散列表
    for(int i=0;i<MAXSIZE;i++)
    {
        HS.hash_table[i]=NULL;
    }
    //依次输入相应的值
    for(int i=0;i<MAXSIZE;i++)
    {
        cout<<"请输入第"<<i+1<<"个数字："<<endl;
        cin>>num;
        site=Hash_function(num);
        //cout<<site<<endl;
        if(HS.hash_table[site]==NULL)//不冲突的条件之下
        {
            PNODE pnew=new NODE;
            pnew->elem=num;
            pnew->next=NULL;
            HS.hash_table[site]=pnew;
        }
        else
        {
            PNODE visit=HS.hash_table[site];
            while(visit->next!=NULL)
            {
            //  cout<<"1"<<" ";
                visit=visit->next;
            }
            PNODE pnew=new NODE;
            pnew->elem=num;
            pnew->next=NULL;
            visit->next=pnew;
        }

    }

}
int  Hash_function(int n)
{
    return n/2;
}
void print_Hash(HASH &HS)
{
    cout<<"打印的哈希表为："<<endl;
    for(int i=0;i<Max/2;i++)
    {
        if(HS.hash_table[i]!=NULL)
        {
            cout<<"下标为 "<<i+1<<" ";
            PNODE visit=HS.hash_table[i];
            while(visit!=NULL)
            {
                cout<<visit->elem<<" ";
                visit=visit->next;
            }
            cout<<"\n";
        }
    }
}

开放寻址法

DateItem类

package hash;

public class DateItem {
    private int iData;

    public DateItem(int iData)
    {

        this.iData = iData;
    }



    public int getKey() {
        // TODO Auto-generated method stub
        return this.iData;
    }
}

OpenAdressHashtable类

package hash;


public class OpenAdressHashtable {

    private DateItem[] hashArray;
    private int arraySize;
    private DateItem nonItem;

    public OpenAdressHashtable(int size)
    {
        arraySize=size;
        hashArray=new DateItem[arraySize];
        nonItem=new DateItem(-1);
    }

    public void showTable()//显示哈希表
    {
        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("*");
            }
        }
        System.out.println();
    }

    public int hashFunc(int key)//哈希函数
    {
        return key%arraySize;
    }

    public void insertIntoTable(DateItem item)//插入哈希表
    {
        int key=item.getKey();
        int hashVal=hashFunc(key);
        while(hashArray[hashVal]!=null&&hashArray[hashVal].getKey()!=-1)
        {
            hashVal++;//被占了，探测下一个位置
            hashVal%=arraySize;//防止越界
        }
        hashArray[hashVal]=item;//插入
    }

    //哈希表删除
    public DateItem deleteItem(int key)
    {
        int hashVal=hashFunc(key);
        while(hashArray[hashVal]!=null)
        {
            if(hashArray[hashVal].getKey()==key)
            {
                DateItem temp=hashArray[hashVal];
                hashArray[hashVal]=nonItem;//删除它
                return temp;
            }
            ++hashVal;
            hashVal%=arraySize;
        }
        return null;
    }

    //哈希表查找

    public DateItem findItem(int key)
    {
        int hashVal=hashFunc(key);
        while(hashArray[hashVal]!=null)
        {
            if(hashArray[hashVal].getKey()==key)
            {
                return hashArray[hashVal];
            }
            hashVal++;
            hashVal%=arraySize;

        }
        return null;
    }

}