using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace HashSearch
{
class Program
{
//“除法取余法”
static int hashLength = 13;
//原數(shù)據(jù)
static Listint> list = new Listint>() { 13, 29, 27, 28, 26, 30, 38 };
//哈希表長(zhǎng)度
static int[] hash = new int[hashLength];
static void Main(string[] args)
{
//創(chuàng)建hash
for (int i = 0; i list.Count; i++)
{
InsertHash(hash, hashLength, list[i]);
}
Console.WriteLine("Hash數(shù)據(jù)：" + string.Join(",", hash));
while (true)
{
Console.WriteLine("\n請(qǐng)輸入要查找數(shù)字：");
int result = int.Parse(Console.ReadLine());
var index = SearchHash(hash, hashLength, result);
if (index != -1)
Console.WriteLine("數(shù)字" + result + "在索引的位置是:" + index);
else
Console.WriteLine("嗚嗚，" + result + " 在hash中沒有找到！");
}
}
///summary>
/// Hash表檢索數(shù)據(jù)
////summary>
///param name="dic">/param>
///param name="hashLength">/param>
///param name="key">/param>
///returns>/returns>
static int SearchHash(int[] hash, int hashLength, int key)
{
//哈希函數(shù)
int hashAddress = key % hashLength;
//指定hashAdrress對(duì)應(yīng)值存在但不是關(guān)鍵值，則用開放尋址法解決
while (hash[hashAddress] != 0 hash[hashAddress] != key)
{
hashAddress = (++hashAddress) % hashLength;
}
//查找到了開放單元，表示查找失敗
if (hash[hashAddress] == 0)
return -1;
return hashAddress;
}
///summary>
///數(shù)據(jù)插入Hash表
////summary>
///param name="dic">哈希表/param>
///param name="hashLength">/param>
///param name="data">/param>
static void InsertHash(int[] hash, int hashLength, int data)
{
//哈希函數(shù)
int hashAddress = data % 13;
//如果key存在，則說明已經(jīng)被別人占用，此時(shí)必須解決沖突
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>
/// 索引項(xiàng)實(shí)體
////summary>
class IndexItem
{
//對(duì)應(yīng)主表的值
public int index;
//主表記錄區(qū)間段的開始位置
public int start;
//主表記錄區(qū)間段的長(zhǎng)度
public int length;
}
static void Main(string[] args)
{
Console.WriteLine("原數(shù)據(jù)為：" + string.Join(",", students));
int value = 205;
Console.WriteLine("\n插入數(shù)據(jù)" + value);
//將205插入集合中，過索引
var index = insert(value);
//如果插入成功，獲取205元素所在的位置
if (index == 1)
{
Console.WriteLine("\n插入后數(shù)據(jù)：" + string.Join(",", students));
Console.WriteLine("\n數(shù)據(jù)元素：205在數(shù)組中的位置為 " + indexSearch(205) + "位");
}
Console.ReadLine();
}
///summary>
/// 學(xué)生主表
////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>
///學(xué)生索引表
////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>
/// 查找數(shù)據(jù)
////summary>
///param name="key">/param>
///returns>/returns>
public static int indexSearch(int key)
{
IndexItem item = null;
// 建立索引規(guī)則
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>
/// 插入數(shù)據(jù)
////summary>
///param name="key">/param>
///returns>/returns>
public static int insert(int key)
{
IndexItem item = null;
//建立索引規(guī)則
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;
}
}
}
