快捷導(dǎo)航

算法系列15天速成第五天五大經(jīng)典查找【中】

更新時(shí)間：2013年11月10日 10:30:38 作者：

大家可否知道，其實(shí)查找中有一種O(1)的查找，即所謂的秒殺

哈希查找：

    對(duì)的，他就是哈希查找，說(shuō)到哈希，大家肯定要提到哈希函數(shù)，呵呵，這東西已經(jīng)在我們腦子里面形成
固有思維了。大家一定要知道“哈?！爸械膶?duì)應(yīng)關(guān)系。
     比如說(shuō)： ”5“是一個(gè)要保存的數(shù)，然后我丟給哈希函數(shù)，哈希函數(shù)給我返回一個(gè)”2"，那么此時(shí)的”5“
和“2”就建立一種對(duì)應(yīng)關(guān)系，這種關(guān)系就是所謂的“哈希關(guān)系”，在實(shí)際應(yīng)用中也就形成了”2“是key，”5“是value。
    那么有的朋友就會(huì)問(wèn)如何做哈希，首先做哈希必須要遵守兩點(diǎn)原則：
          ①: key盡可能的分散，也就是我丟一個(gè)“6”和“5”給你，你都返回一個(gè)“2”，那么這樣的哈希函數(shù)不盡完美。
          ②：哈希函數(shù)盡可能的簡(jiǎn)單，也就是說(shuō)丟一個(gè)“6”給你，你哈希函數(shù)要搞1小時(shí)才能給我，這樣也是不好的。

其實(shí)常用的做哈希的手法有“五種”：
第一種：”直接定址法“。
                  很容易理解，key=Value+C；這個(gè)“C"是常量。Value+C其實(shí)就是一個(gè)簡(jiǎn)單的哈希函數(shù)。
第二種：“除法取余法”。
                  很容易理解， key=value%C;解釋同上。
第三種：“數(shù)字分析法”。
                  這種蠻有意思，比如有一組value1=112233，value2=112633，value3=119033，
                  針對(duì)這樣的數(shù)我們分析數(shù)中間兩個(gè)數(shù)比較波動(dòng)，其他數(shù)不變。那么我們?nèi)ey的值就可以是
                  key1=22,key2=26,key3=90。
第四種：“平方取中法”。此處忽略，見(jiàn)名識(shí)意。
第五種：“折疊法”。
                 這種蠻有意思,比如value=135790，要求key是2位數(shù)的散列值。那么我們將value變?yōu)?3+57+90=160，
                 然后去掉高位“1”,此時(shí)key=60，哈哈，這就是他們的哈希關(guān)系，這樣做的目的就是key與每一位value都相
                 關(guān)，來(lái)做到“散列地址”盡可能分散的目地。

正所謂常在河邊走，哪有不濕鞋。哈希也一樣，你哈希函數(shù)設(shè)計(jì)的再好，搞不好哪一次就撞樓了，那么拋給我們的問(wèn)題
就是如果來(lái)解決“散列地址“的沖突。

其實(shí)解決沖突常用的手法也就2種：

第一種： “開(kāi)放地址法“。
                 所謂”開(kāi)放地址“，其實(shí)就是數(shù)組中未使用的地址。也就是說(shuō)，在發(fā)生沖突的地方，后到的那個(gè)元素（可采用兩種方式
                 :①線(xiàn)性探測(cè)，②函數(shù)探測(cè)）向數(shù)組后尋找"開(kāi)放地址“然后把自己插進(jìn)入。

第二種：”鏈接法“。
                這個(gè)大家暫時(shí)不懂也沒(méi)關(guān)系，我就先介紹一下原理，就是在每個(gè)元素上放一個(gè)”指針域“，在發(fā)生沖突的地方，后到的那
               個(gè)元素將自己的數(shù)據(jù)域拋給沖突中的元素，此時(shí)沖突的地方就形成了一個(gè)鏈表。

上面啰嗦了那么多，也就是想讓大家在”設(shè)計(jì)哈?！昂汀苯鉀Q沖突“這兩個(gè)方面提一點(diǎn)參考和手段。

那么下面就上代碼了，
     設(shè)計(jì)函數(shù)采用：”除法取余法“。
     沖突方面采用:”開(kāi)放地址線(xiàn)性探測(cè)法"。

復(fù)制代碼代碼如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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

//原數(shù)據(jù)
static List<int> list = new List<int>() { 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中沒(méi)有找到！");

}
}

        ///<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)鍵值，則用開(kāi)放尋址法解決
            while (hash[hashAddress] != 0 && hash[hashAddress] != key)
            {
                hashAddress = (++hashAddress) % hashLength;
            }

            //查找到了開(kāi)放單元，表示查找失敗
            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存在，則說(shuō)明已經(jīng)被別人占用，此時(shí)必須解決沖突
            while (hash[hashAddress] != 0)
            {
                //用開(kāi)放尋址法找到
                hashAddress = (++hashAddress) % hashLength;
            }

            //將data存入字典中
            hash[hashAddress] = data;
        }
    }
}

結(jié)果：

索引查找：
     一提到“索引”，估計(jì)大家第一反應(yīng)就是“數(shù)據(jù)庫(kù)索引”，對(duì)的，其實(shí)主鍵建立“索引”，就是方便我們?cè)诤Ａ繑?shù)據(jù)中查找。
關(guān)于“索引”的知識(shí)，估計(jì)大家都比我清楚，我就簡(jiǎn)單介紹下。
我們自己寫(xiě)算法來(lái)實(shí)現(xiàn)索引查找時(shí)常使用的三個(gè)術(shù)語(yǔ)：
第一：主表，      這個(gè)很簡(jiǎn)單，要查找的對(duì)象。
第二：索引項(xiàng)，   一般我們會(huì)用函數(shù)將一個(gè)主表劃分成幾個(gè)子表，每個(gè)子表建立一個(gè)索引，這個(gè)索引叫做索引項(xiàng)。
第三：索引表,    索引項(xiàng)的集合也就是索引表。

一般“索引項(xiàng)”包含三種內(nèi)容：index，start，length

第一： index，也就是索引指向主表的關(guān)鍵字。
第二：start，也就是index在主表中的位置。
第三：length, 也就是子表的區(qū)間長(zhǎng)度。

復(fù)制代碼代碼如下:

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ū)間段的開(kāi)始位置
            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插入集合中，過(guò)索引
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，則說(shuō)明在索引中查找失敗
            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;
        }
    }
}