namespace HashSearch
{
    class Program
    {
        //“除法取余法”
        static int hashLength = 13;

        //原數據
        static List<int> list = new List<int>() { 13, 29, 27, 28, 26, 30, 38 };

        //哈希表長度
        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數據：" + 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;
        }
    }
}

namespace IndexSearchProgram
{
    class Program
    {
        ///<summary>
/// 索引項實體
///</summary>
        class IndexItem
        {
            //對應主表的值
            public int index;
            //主表記錄區(qū)間段的開始位置
            public int start;
            //主表記錄區(qū)間段的長度
            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;

            // 建立索引規(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>
/// 插入數據
///</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;
        }
    }
}