WeiBlog

//解决冲突的方式

//1.桶式散列法
//在数组列表中存储数组列表
//一个键(主容器数组列表索引)可存储多个值(数组列表内的“数组列表的多个值“)
class BucketHash
{

    private const int SIZE = 101;
    ArrayList[] date;

    public BucketHash()
    {
        date = new ArrayList[SIZE];
        for (int i = 0; i < SIZE; i++)
        {
            date[i] = new ArrayList(4);
        }
    }

    public int Hash(string s)
    {
        long key = 0;
        char[] cname = s.ToCharArray();
        for (int i = 0; i < cname.Length; i++)
        {
            key += 37 * key + (int)cname[i];
        }
        key = key % date.GetUpperBound(0);
        if (key < 0)
            key += date.GetUpperBound(0);
        return (int)key;
    }

    public void Insert(string s)
    {
        int hash_key = Hash(s);
        if (!date[hash_key].Contains(s))
            date[hash_key].Add(s);

    }

    public void Remove(string s)
    {
        int hash_key = Hash(s);
        if (date[hash_key].Contains(s))
            date[hash_key].Remove(s);
    }

    public void ShowTable()
    {
        for (int i = 0; i < date.Length; i++)
        {
            if (date[i].Count>0)
            {
                Console.Write(i+":");
                foreach (string s in date[i])
                {
                    Console.Write(s);
                }
                Console.WriteLine();
            }
                
        }
    }
}

}
//示例程序
class Program
{
static void Main(string[] args)
{
//桶式散列法
BucketHash bkHash = new BucketHash();
for (int i = 0; i < someName .Length; i++)
{
bkHash.Insert(someName[i]);
}
bkHash.ShowTable();

    }

//2.开放地址法
//发生冲突时，寻找下一个空的散列地址（平方探测直至找到下一个空位置）

//多重散列
//存在多种哈希函数，发生冲突时调用备选哈希函数