XIAOSUO 记录个人学习的足迹

　　在用线性查找和二分查找的过程中需要依据关键字进行若干次的比较判断，确定数据集合中是否存在关键字等于某个给定关键字的记录以及该记录在数据表中的位置，查找效率与比较的次数密切相关。在查找时需要不断进行比较的原因是建立数据表时，只考虑了各记录的关键字之间的相对大小，记录在表中的位置和其关键字无直接关系。而之前介绍的哈希表就记录了存储位置和其关键字之间的某种直接关系，那么使用哈希表进行查找时，就无须比较或只做很少的比较久能直接由关键字找到相应的记录。实际上哈希表也就是为解决查找问题提出的。具体哈希表的内容请参考之前的“散列表”相关文章。

　　下面我将通过实例来说明哈希算法的实现。
　　【例】数字序列{70，30，40，10，80，20，90，100，75，80，45}采用哈希表存放。哈希函数采用除13取余数，哈希冲突解决方法采用链表法。实现该实例的程序如下：

class chaintype
{
	private int key;
	private chaintype next;
	public int Key
	{
		get
		{
			return key;
		}
		set
		{
			key = value;
		}
	}
	public chaintype Next
	{
		get
		{
			return next;
		}
		set
		{
			next = value;
		}
	}
}
class SearchArithMetic
{
	/* 除模取余法的哈希函数*/
	public int Hash(int key, int Mod)
	{
		return key % Mod;
	}

	/*在哈希表中插入记录,用链表法解决冲突*/
	public bool HashInsert(chaintype[] a, int Key, int Mod)
	{
		int i;
		i = Hash(Key, Mod);
		chaintype pre;
		chaintype cur;
		pre = a[i];
		cur = a[i];
		while (cur != null && cur.Key != Key)
		{
			pre = cur;
			cur = cur.Next;
		}
		/* 未查找到时插入该记录在对应的链表尾*/
		if (cur == null)
		{
			cur = new chaintype();
			cur.Key = Key;
			cur.Next = null;
			/* 在该链插入第一个记录*/
			if (a[i] == null)
				a[i] = cur;
			/*在该链插入后续记录取*/
			else
				pre.Next = cur;
			return true;
		}
		return false;
	}
	/*在哈希表a中查找关键字Key*/
	public chaintype HashSearch(chaintype[] a, int Key, int Mod)
	{
		chaintype p;
		int i = Hash(Key, Mod);
		p = a[i];
		while (p != null && p.Key != Key)
			p = p.Next;
		/*查找不到时返回空值*/
		if (p == null) return null;
		/*查找到时返回该记录的地址*/
		else
			return p;
	}
}