using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace HashSearch
{
class Program
{
//“除法取余法”
static int hashLength = 13;
//原数据
static Listint> list = new Listint>() { 13, 29, 27, 28, 26, 30, 38 };
//哈希表长度
static int[] hash = new int[hashLength];
static void Main(string[] args)
{
//创建hash
for (int i = 0; i list.Count; i++)
{
InsertHash(hash, hashLength, list[i]);
}
Console.WriteLine("Hash数据:" + string.Join(",", hash));
while (true)
{
Console.WriteLine("\n请输入要查找数字:");
int result = int.Parse(Console.ReadLine());
var index = SearchHash(hash, hashLength, result);
if (index != -1)
Console.WriteLine("数字" + result + "在索引的位置是:" + index);
else
Console.WriteLine("呜呜," + result + " 在hash中没有找到!");
}
}
///summary>
/// Hash表检索数据
////summary>
///param name="dic">/param>
///param name="hashLength">/param>
///param name="key">/param>
///returns>/returns>
static int SearchHash(int[] hash, int hashLength, int key)
{
//哈希函数
int hashAddress = key % hashLength;
//指定hashAdrress对应值存在但不是关键值,则用开放寻址法解决
while (hash[hashAddress] != 0 hash[hashAddress] != key)
{
hashAddress = (++hashAddress) % hashLength;
}
//查找到了开放单元,表示查找失败
if (hash[hashAddress] == 0)
return -1;
return hashAddress;
}
///summary>
///数据插入Hash表
////summary>
///param name="dic">哈希表/param>
///param name="hashLength">/param>
///param name="data">/param>
static void InsertHash(int[] hash, int hashLength, int data)
{
//哈希函数
int hashAddress = data % 13;
//如果key存在,则说明已经被别人占用,此时必须解决冲突
while (hash[hashAddress] != 0)
{
//用开放寻址法找到
hashAddress = (++hashAddress) % hashLength;
}
//将data存入字典中
hash[hashAddress] = data;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace IndexSearchProgram
{
class Program
{
///summary>
/// 索引项实体
////summary>
class IndexItem
{
//对应主表的值
public int index;
//主表记录区间段的开始位置
public int start;
//主表记录区间段的长度
public int length;
}
static void Main(string[] args)
{
Console.WriteLine("原数据为:" + string.Join(",", students));
int value = 205;
Console.WriteLine("\n插入数据" + value);
//将205插入集合中,过索引
var index = insert(value);
//如果插入成功,获取205元素所在的位置
if (index == 1)
{
Console.WriteLine("\n插入后数据:" + string.Join(",", students));
Console.WriteLine("\n数据元素:205在数组中的位置为 " + indexSearch(205) + "位");
}
Console.ReadLine();
}
///summary>
/// 学生主表
////summary>
static int[] students = {
101,102,103,104,105,0,0,0,0,0,
201,202,203,204,0,0,0,0,0,0,
301,302,303,0,0,0,0,0,0,0
};
///summary>
///学生索引表
////summary>
static IndexItem[] indexItem = {
new IndexItem(){ index=1, start=0, length=5},
new IndexItem(){ index=2, start=10, length=4},
new IndexItem(){ index=3, start=20, length=3},
};
///summary>
/// 查找数据
////summary>
///param name="key">/param>
///returns>/returns>
public static int indexSearch(int key)
{
IndexItem item = null;
// 建立索引规则
var index = key / 100;
//首先去索引找
for (int i = 0; i indexItem.Count(); i++)
{
if (indexItem[i].index == index)
{
item = new IndexItem() { start = indexItem[i].start, length = indexItem[i].length };
break;
}
}
//如果item为null,则说明在索引中查找失败
if (item == null)
return -1;
for (int i = item.start; i item.start + item.length; i++)
{
if (students[i] == key)
{
return i;
}
}
return -1;
}
///summary>
/// 插入数据
////summary>
///param name="key">/param>
///returns>/returns>
public static int insert(int key)
{
IndexItem item = null;
//建立索引规则
var index = key / 100;
int i = 0;
for (i = 0; i indexItem.Count(); i++)
{
//获取到了索引
if (indexItem[i].index == index)
{
item = new IndexItem()
{
start = indexItem[i].start,
length = indexItem[i].length
};
break;
}
}
if (item == null)
return -1;
//更新主表
students[item.start + item.length] = key;
//更新索引表
indexItem[i].length++;
return 1;
}
}
}