數(shù)據(jù)結(jié)構(gòu)——哈希表解析介紹.doc

本文根據(jù)他人博文整理而來(lái)，尊重原創(chuàng)。在前面的系列文章中，依次介紹了基于無(wú)序列表的順序查找，基于有序數(shù)組的二分查找，平衡查找樹，以及紅黑樹，下圖是他們?cè)谄骄约白畈钋闆r下的時(shí)間復(fù)雜度：可以看到在時(shí)間復(fù)雜度上，紅黑樹在平均情況下插入，查找以及刪除上都達(dá)到了lgN的時(shí)間復(fù)雜度。那么有沒(méi)有查找效率更高的數(shù)據(jù)結(jié)構(gòu)呢，答案就是本文接下來(lái)要介紹了散列表，也叫哈希表(Hash Table)什么是哈希表哈希表就是一種以 鍵-值(key-indexed) 存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)，我們只要輸入待查找的值即key，即可查找到其對(duì)應(yīng)的值。哈希的思路很簡(jiǎn)單，如果所有的鍵都是整數(shù)，那么就可以使用一個(gè)簡(jiǎn)單的無(wú)序數(shù)組來(lái)實(shí)現(xiàn)：將鍵作為索引，值即為其對(duì)應(yīng)的值，這樣就可以快速訪問(wèn)任意鍵的值。這是對(duì)于簡(jiǎn)單的鍵的情況，我們將其擴(kuò)展到可以處理更加復(fù)雜的類型的鍵。使用哈希查找有兩個(gè)步驟:1. 使用哈希函數(shù)將被查找的鍵轉(zhuǎn)換為數(shù)組的索引。在理想的情況下，不同的鍵會(huì)被轉(zhuǎn)換為不同的索引值，但是在有些情況下我們需要處理多個(gè)鍵被哈希到同一個(gè)索引值的情況。所以哈希查找的第二個(gè)步驟就是處理沖突2. 處理哈希碰撞沖突。有很多處理哈希碰撞沖突的方法，本文后面會(huì)介紹拉鏈法和線性探測(cè)法。哈希表是一個(gè)在時(shí)間和空間上做出權(quán)衡的經(jīng)典例子。如果沒(méi)有內(nèi)存限制，那么可以直接將鍵作為數(shù)組的索引。那么所有的查找時(shí)間復(fù)雜度為O(1)；如果沒(méi)有時(shí)間限制，那么我們可以使用無(wú)序數(shù)組并進(jìn)行順序查找，這樣只需要很少的內(nèi)存。哈希表使用了適度的時(shí)間和空間來(lái)在這兩個(gè)極端之間找到了平衡。只需要調(diào)整哈希函數(shù)算法即可在時(shí)間和空間上做出取舍。哈希函數(shù)哈希查找第一步就是使用哈希函數(shù)將鍵映射成索引。這種映射函數(shù)就是哈希函數(shù)。如果我們有一個(gè)保存0-M數(shù)組，那么我們就需要一個(gè)能夠?qū)⑷我怄I轉(zhuǎn)換為該數(shù)組范圍內(nèi)的索引（0M-1）的哈希函數(shù)。哈希函數(shù)需要易于計(jì)算并且能夠均勻分布所有鍵。比如舉個(gè)簡(jiǎn)單的例子，使用手機(jī)號(hào)碼后三位就比前三位作為key更好，因?yàn)榍叭皇謾C(jī)號(hào)碼的重復(fù)率很高。再比如使用身份證號(hào)碼出生年月位數(shù)要比使用前幾位數(shù)要更好。在實(shí)際中，我們的鍵并不都是數(shù)字，有可能是字符串，還有可能是幾個(gè)值的組合等，所以我們需要實(shí)現(xiàn)自己的哈希函數(shù)。1. 正整數(shù)獲取正整數(shù)哈希值最常用的方法是使用除留余數(shù)法。即對(duì)于大小為素?cái)?shù)M的數(shù)組，對(duì)于任意正整數(shù)k，計(jì)算k除以M的余數(shù)。M一般取素?cái)?shù)。2. 字符串將字符串作為鍵的時(shí)候，我們也可以將他作為一個(gè)大的整數(shù)，采用保留除余法。我們可以將組成字符串的每一個(gè)字符取值然后進(jìn)行哈希，比如public int GetHashCode(string str) char s = str.ToCharArray(); int hash = 0; for (int i = 0; i s.Length; i+) hash = si + (31 * hash); return hash;上面的哈希值是Horner計(jì)算字符串哈希值的方法，公式為:h = s0 31L1+ + sL 3 312+ sL 2 311+ sL 1 310舉個(gè)例子，比如要獲取”call”的哈希值，字符串c對(duì)應(yīng)的unicode為99，a對(duì)應(yīng)的unicode為97，L對(duì)應(yīng)的unicode為108，所以字符串”call”的哈希值為 3045982 = 99313+ 97312+ 108311+ 108310= 108 + 31 (108 + 31 (97 + 31 (99)如果對(duì)每個(gè)字符去哈希值可能會(huì)比較耗時(shí)，所以可以通過(guò)間隔取N個(gè)字符來(lái)獲取哈西值來(lái)節(jié)省時(shí)間，比如，可以 獲取每8-9個(gè)字符來(lái)獲取哈希值：public int GetHashCode(string str) char s = str.ToCharArray(); int hash = 0; int skip = Math.Max(1, s.Length / 8); for (int i = 0; i s.Length; i+=skip) hash = si + (31 * hash); return hash;但是，對(duì)于某些情況，不同的字符串會(huì)產(chǎn)生相同的哈希值，這就是前面說(shuō)到的哈希沖突（Hash Collisions），比如下面的四個(gè)字符串：如果我們按照每8個(gè)字符取哈希的話，就會(huì)得到一樣的哈希值。所以下面來(lái)講解如何解決哈希碰撞：避免哈希沖突拉鏈法 (Separate chaining with linked lists)通過(guò)哈希函數(shù)，我們可以將鍵轉(zhuǎn)換為數(shù)組的索引(0-M-1)，但是對(duì)于兩個(gè)或者多個(gè)鍵具有相同索引值的情況，我們需要有一種方法來(lái)處理這種沖突。一種比較直接的辦法就是，將大小為M 的數(shù)組的每一個(gè)元素指向一個(gè)條鏈表，鏈表中的每一個(gè)節(jié)點(diǎn)都存儲(chǔ)散列值為該索引的鍵值對(duì)，這就是拉鏈法。下圖很清楚的描述了什么是拉鏈法。圖中，”John Smith”和”Sandra Dee” 通過(guò)哈希函數(shù)都指向了152 這個(gè)索引，該索引又指向了一個(gè)鏈表， 在鏈表中依次存儲(chǔ)了這兩個(gè)字符串。該方法的基本思想就是選擇足夠大的M，使得所有的鏈表都盡可能的短小，以保證查找的效率。對(duì)采用拉鏈法的哈希實(shí)現(xiàn)的查找分為兩步，首先是根據(jù)散列值找到等一應(yīng)的鏈表，然后沿著鏈表順序找到相應(yīng)的鍵。 我們現(xiàn)在使用我們之前介紹符號(hào)表中的使用無(wú)序鏈表實(shí)現(xiàn)的查找表SequentSearchSymbolTable來(lái)實(shí)現(xiàn)我們這里的哈希表。當(dāng)然，您也可以使用.NET里面內(nèi)置的LinkList。首先我們需要定義一個(gè)鏈表的總數(shù)，在內(nèi)部我們定義一個(gè)SequentSearchSymbolTable的數(shù)組。然后每一個(gè)映射到索引的地方保存一個(gè)這樣的數(shù)組。public class SeperateChainingHashSet : SymbolTables where TKey : IComparable, IEquatable private int M;/散列表大小 private SequentSearchSymbolTable st;/ public SeperateChainingHashSet() : this(997) public SeperateChainingHashSet(int m) this.M = m; st = new SequentSearchSymbolTablem; for (int i = 0; i m; i+) sti = new SequentSearchSymbolTable(); private int hash(TKey key) return (key.GetHashCode() & 0x7fffffff) % M; public override TValue Get(TKey key) return sthash(key).Get(key); public override void Put(TKey key, TValue value) sthash(key).Put(key, value); 可以看到，該實(shí)現(xiàn)中使用 Get方法來(lái)獲取指定key的Value值，我們首先通過(guò)hash方法來(lái)找到key對(duì)應(yīng)的索引值，即找到SequentSearchSymbolTable數(shù)組中存儲(chǔ)該元素的查找表，然后調(diào)用查找表的Get方法，根據(jù)key找到對(duì)應(yīng)的Value。 Put方法用來(lái)存儲(chǔ)鍵值對(duì)，首先通過(guò)hash方法找到改key對(duì)應(yīng)的哈希值，然后找到SequentSearchSymbolTable數(shù)組中存儲(chǔ)該元素的查找表，然后調(diào)用查找表的Put方法，將鍵值對(duì)存儲(chǔ)起來(lái)。 hash方法來(lái)計(jì)算key的哈希值， 這里首先通過(guò)取與&操作，將符號(hào)位去除，然后采用除留余數(shù)法將key應(yīng)到到0-M-1的范圍，這也是我們的查找表數(shù)組索引的范圍。實(shí)現(xiàn)基于拉鏈表的散列表，目標(biāo)是選擇適當(dāng)?shù)臄?shù)組大小M，使得既不會(huì)因?yàn)榭真湵矶速M(fèi)內(nèi)存空間，也不會(huì)因?yàn)殒湵硖诓檎疑侠速M(fèi)太多時(shí)間。拉鏈表的優(yōu)點(diǎn)在于，這種數(shù)組大小M的選擇不是關(guān)鍵性的，如果存入的鍵多于預(yù)期，那么查找的時(shí)間只會(huì)比選擇更大的數(shù)組稍長(zhǎng)，另外，我們也可以使用更高效的結(jié)構(gòu)來(lái)代替鏈表存儲(chǔ)。如果存入的鍵少于預(yù)期，索然有些浪費(fèi)空間，但是查找速度就會(huì)很快。所以當(dāng)內(nèi)存不緊張時(shí)，我們可以選擇足夠大的M，可以使得查找時(shí)間變?yōu)槌?shù)，如果內(nèi)存緊張時(shí)，選擇盡量大的M仍能夠?qū)⑿阅芴岣進(jìn)倍。線性探測(cè)法線性探測(cè)法是開放尋址法解決哈希沖突的一種方法，基本原理為，使用大小為M的數(shù)組來(lái)保存N個(gè)鍵值對(duì)，其中MN，我們需要使用數(shù)組中的空位解決碰撞沖突。如下圖所示：對(duì)照前面的拉鏈法，在該圖中，”Ted Baker” 是有唯一的哈希值153的，但是由于153被”Sandra Dee”占用了。而原先”Snadra Dee”和”John Smith”的哈希值都是152的，但是在對(duì)”Sandra Dee”進(jìn)行哈希的時(shí)候發(fā)現(xiàn)152已經(jīng)被占用了，所以往下找發(fā)現(xiàn)153沒(méi)有被占用，所以存放在153上，然后”Ted Baker”哈希到153上，發(fā)現(xiàn)已經(jīng)被占用了，所以往下找，發(fā)現(xiàn)154沒(méi)有被占用，所以值存到了154上。開放尋址法中最簡(jiǎn)單的是線性探測(cè)法：當(dāng)碰撞發(fā)生時(shí)即一個(gè)鍵的散列值被另外一個(gè)鍵占用時(shí)，直接檢查散列表中的下一個(gè)位置即將索引值加1，這樣的線性探測(cè)會(huì)出現(xiàn)三種結(jié)果：1. 命中，該位置的鍵和被查找的鍵相同2. 未命中，鍵為空3. 繼續(xù)查找，該位置和鍵被查找的鍵不同。實(shí)現(xiàn)線性探測(cè)法也很簡(jiǎn)單，我們只需要兩個(gè)大小相同的數(shù)組分別記錄key和value。public class LinearProbingHashSet : SymbolTables where TKey : IComparable, IEquatable private int N;/符號(hào)表中鍵值對(duì)的總數(shù) private int M = 16;/線性探測(cè)表的大小 private TKey keys; private TValue values; public LinearProbingHashSet() keys = new TKeyM; values = new TValueM; private int hash(TKey key) return (key.GetHashCode() & 0xFFFFFFF) % M; public override TValue Get(TKey key) for (int i = hash(key); keysi != null; i = (i + 1) % M) if (key.Equals(keysi) return valuesi; return default(TValue); public override void Put(TKey key, TValue value) int hashCode = hash(key); for (int i = hashCode; keysi != null; i = (i + 1) % M) if (keysi.Equals(key)/如果和已有的key相等，則用新值覆蓋 valuesi = value; return; /插入 keysi = key; valuesi = value; 線性探查（Linear Probing）方式雖然簡(jiǎn)單，但是有一些問(wèn)題，它會(huì)導(dǎo)致同類哈希的聚集。在存入的時(shí)候存在沖突，在查找的時(shí)候沖突依然存在。性能分析我們可以看到，哈希表存儲(chǔ)和查找數(shù)據(jù)的時(shí)候分為兩步，第一步為將鍵通過(guò)哈希函數(shù)映射為數(shù)組中的索引， 這個(gè)過(guò)程可以認(rèn)為是只需要常數(shù)時(shí)間的。第二步是，如果出現(xiàn)哈希值沖突，如何解決，前面介紹了拉鏈法和線性探測(cè)法下面就這兩種方法進(jìn)行討論：對(duì)于拉鏈法，查找的效率在于鏈表的長(zhǎng)度，一般的我們應(yīng)該保證長(zhǎng)度在M/8M/2之間，如果鏈表的長(zhǎng)度大于M/2，我們可以擴(kuò)充鏈表長(zhǎng)度。如果長(zhǎng)度在0M/8時(shí)，我們可以縮小鏈表。對(duì)于線性探測(cè)法，也是如此，但是動(dòng)態(tài)調(diào)整數(shù)組的大小需要對(duì)所有的值從新進(jìn)行重新散列并插入新的表中。不管是拉鏈法還是散列法，這種動(dòng)態(tài)調(diào)整鏈表或者數(shù)組的大小以提高查詢效率的同時(shí)，還應(yīng)該考慮動(dòng)態(tài)改變鏈表或者數(shù)組大小的成本。散列表長(zhǎng)度加倍的插入需要進(jìn)行大量的探測(cè)， 這種均攤成本在很多時(shí)候需要考慮。哈希碰撞攻擊我們知道如果哈希函數(shù)選擇不當(dāng)會(huì)使得大量的鍵都會(huì)映射到相同的索引上，不管是采用拉鏈法還是開放尋址法解決沖突，在后面查找的時(shí)候都需要進(jìn)行多次探測(cè)或者查找， 在很多時(shí)候會(huì)使得哈希表的查找效率退化，而不再是常數(shù)時(shí)間。下圖清楚的描述了退化后的哈希表：哈希表攻擊就是通過(guò)精心構(gòu)造哈希函數(shù)，使得所有的鍵經(jīng)過(guò)哈希函數(shù)后都映射到同一個(gè)或者幾個(gè)索引上，將哈希表退化為了一個(gè)單鏈表，這樣哈希表的各種操作，比如插入，查找都從O(1)退化到了鏈表的查找操作，這樣就會(huì)消耗大量的CPU資源，導(dǎo)致系統(tǒng)無(wú)法響應(yīng)，從而達(dá)到拒絕服務(wù)供給(Denial of Service, Dos)的目的。之前由于多種編程語(yǔ)言的哈希算法的“非隨機(jī)”而出現(xiàn)了Hash碰撞的DoS安全漏洞，在ASP.NET中也曾出現(xiàn)過(guò)這一問(wèn)題。在.NET中String的哈希值內(nèi)部實(shí)現(xiàn)中，通過(guò)使用哈希值隨機(jī)化來(lái)對(duì)這種問(wèn)題進(jìn)行了限制，通過(guò)對(duì)碰撞次數(shù)設(shè)置閾值，超過(guò)該閾值就對(duì)哈希函數(shù)進(jìn)行隨機(jī)化，這也是防止哈希表退化的一種做法。下面是BCL中string類型的GetHashCode方法的實(shí)現(xiàn)，可以看到，當(dāng)碰撞超過(guò)一定次數(shù)的時(shí)候，就會(huì)開啟條件編譯，對(duì)哈希函數(shù)進(jìn)行隨機(jī)化。ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail), SecuritySafeCritical, _DynamicallyInvokablepublic override unsafe int GetHashCode() if (HashHelpers.s_UseRandomizedStringHashing) return InternalMarvin32HashString(this, this.Length, 0L); fixed (char* str = (char*) this) char* chPtr = str; int num = 0x15051505; int num2 = num; int* numPtr = (int*) chPtr; int length = this.Length; while (length 2) num = (num 0x1b) numPtr0; num2 = (num2 0x1b) numPtr1; numPtr += 2; length -= 4; if (length 0) num = (num 0x1b) numPtr0; return (num + (num2 * 0x5d588b65); .NET中哈希的實(shí)現(xiàn)我們可以通過(guò)在線源碼查看.NET 中Dictionary，類型的實(shí)現(xiàn)，我們知道任何作為key的值添加到Dictionary中時(shí)，首先會(huì)獲取key的hashcode，然后將其映射到不同的bucket中去：public Dictionary(int capacity, IEqualityComparer comparer) if (capacity 0) Initialize(capacity); parer = comparer ? EqualityComparer.Default;在Dictionary初始化的時(shí)候，會(huì)如果傳入了大小，會(huì)初始化bucket 就是調(diào)用Initialize方法：private void Initialize(int capacity) int size = HashHelpers.GetPrime(capacity); buckets = new intsize; for (int i = 0; i = 0; i = entriesi.next) if (entriesi.hashCode = hashCode & comparer.Equals(entriesi.key, key) if (add) ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); entriesi.value = value; version+; return; #if FEATURE_RANDOMIZED_STRING_HASHING collisionCount+;#endif int index; if (freeCount 0) index = freeList; freeList = entriesindex.next; freeCount-; else if (count = entries.Length) Resize(); targetBucket = hashCode % buckets.Length; index = count; count+; entriesindex.hashCode = hashCode; entriesindex.next = bucketstargetBucket; entriesindex.key = key; entriesindex.value = value; bucketstargetBucket = index; version+; #if FEATURE_RANDOMIZED_STRING_HASHING if(collisionCount HashHelpers.HashCollisionThreshold & HashHelpers.IsWellKnownEqualityComparer(comparer) comparer = (IEqualityComparer) HashHelpers.GetRandomizedEqualityComparer(comparer); Resize(entries.Length, true); #endif 首先，根據(jù)key獲取其hashcode，然后將hashcode除以backet的大小取余映射到目標(biāo)backet中，然后遍歷該bucket存儲(chǔ)的鏈表，如果找到和key相同的值，如果不允許后添加的鍵與存在的鍵相同替換值(add)，則拋出異常，如果允許，則替換之前的值，然后返回。如果沒(méi)有找到，則將新添加的值放到新的bucket中，當(dāng)空余空間不足的時(shí)候，會(huì)進(jìn)行擴(kuò)容操作(Resize)，然后重新hash到目標(biāo)bucket。這里面需要注意的是Resize操作比較消耗資源?？偨Y(jié)前面幾篇文章先后介紹了基于無(wú)序列表的順序查找，基于有序數(shù)組的二分查找，平衡查找樹，以及紅黑樹，本篇文章最后介紹了查找算法中的最后一類即符號(hào)表又稱哈希表,并介紹了哈希函數(shù)以及處理哈希沖突的兩種方法：拉鏈法和線性探測(cè)法。各種查找算法的最壞和平均條件下各種操作的時(shí)間復(fù)雜度如下圖:在實(shí)際編寫代碼中，如何選擇合適的數(shù)據(jù)結(jié)構(gòu)需要根據(jù)具體的數(shù)據(jù)規(guī)模，查找效率要求，時(shí)間和空間局限來(lái)做出合適的選擇。希望本文以及前面的幾篇文章對(duì)您有所幫助。說(shuō)明:本程序建立的哈希表示意圖:哈希函數(shù)為對(duì)哈希表長(zhǎng)取余源代碼:cppview plaincopy1. /*2. *哈希表算法實(shí)現(xiàn)3. *(c)copyright2013,jdh4. *AllRightReserved5. *文件名:main.c6. *程序員:jdh7. */8. 9. #include10. #include11. 12. /*13. *宏定義14. */15. 16. /*17. *數(shù)據(jù)類型重定義18. */19. 20. #defineuint8_tunsignedchar21. #defineuint16_tunsignedshort22. #defineuint32_tunsignedlong23. 24. /*25. *哈希表長(zhǎng)度26. */27. 28. #defineHASH_TABLE_LEN10029. 30. /*31. *數(shù)據(jù)結(jié)構(gòu)32. */33. /鏈表節(jié)點(diǎn)34. typedefstruct_Link_Node35. 36. uint16_tid;37. uint16_tdata;38. struct_Link_Node*next;39. Link_Node,*Link_Node_Ptr;40. 41. /哈希表頭42. typedefstruct_Hash_Header43. 44. struct_Link_Node*next;45. Hash_Header,*Hash_Header_Ptr;46. 47. /*48. *全局變量49. */50. 51. /哈希表52. Hash_Header_PtrHash_TableHASH_TABLE_LEN;53. 54. /*55. *函數(shù)56. */57. 58. /*59. *哈希表函數(shù)60. *說(shuō)明:61. *1.用哈希函數(shù)生成id對(duì)應(yīng)的哈希表中的位置62. 輸入:id63. 返回:位置64. */65. 66. uint8_thash_func(uint16_tid)67. 68. uint8_tpos=0;69. 70. pos=id%HASH_TABLE_LEN;71. 72. returnpos;73. 74. 75. /*76. *初始化節(jié)點(diǎn)77. *返回:結(jié)點(diǎn)指針78. */79. 80. Link_Node_Ptrinit_link_node(void)81. 82. Link_Node_Ptrnode;83. 84. /申請(qǐng)節(jié)點(diǎn)85. node=(Link_Node_Ptr)malloc(sizeof(Link_Node);86. /初始化長(zhǎng)度為087. node-next=NULL;88. 89. returnnode;90. 91. 92. /*93. *初始化哈希表頭結(jié)點(diǎn)94. *返回哈希表頭結(jié)點(diǎn)指針95. */96. 97. Hash_Header_Ptrinit_hash_header_node(void)98. 99. Hash_Header_Ptrnode;100. 101. /申請(qǐng)節(jié)點(diǎn)102. node=(Hash_Header_Ptr)malloc(sizeof(Hash_Header);103. /初始化長(zhǎng)度為0104. node-next=NULL;105. 106. returnnode;107. 108. 109. 110. /*111. *哈希表初始化112. *說(shuō)明:113. *1.初始化哈希表Hash_Table114. *2.哈希表長(zhǎng)度最大不能超過(guò)256115. */116. 117. voidinit_hash_table(void)118. 119. uint8_ti=0;120. 121. for(i=0;inext=NULL;125. 126. 127. 128. /*129. *在哈希表增加節(jié)點(diǎn)130. *說(shuō)明:131. *1.在哈希表的某個(gè)鏈表末增加數(shù)據(jù)132. 輸入:new_node:新節(jié)點(diǎn)133. */134. 135. voidappend_link_node(Link_Node_Ptrnew_node)136. 137. Link_Node_Ptrnode;138. uint8_tpos=0;139. 140. /新節(jié)點(diǎn)下一個(gè)指向?yàn)榭?41. new_node-next=NULL;142. 143. /用哈希函數(shù)獲得位置144. pos=hash_func(new_node-id);145. 146. /判斷是否為空鏈表147. if(Hash_Tablepos-next=NULL)148. 149. /空鏈表150. Hash_Tablepos-next=new_node;151. 152. else153. 154. /不是空鏈表155. /獲取根節(jié)點(diǎn)156. node=Hash_Tablepos-next;157. 158. /遍歷159. while(node-next!=NULL)160. 161. node=node-next;162. 163. 164. /插入165. node-next=new_node;166. 167. 168. 169. /*170. *在哈希表查詢節(jié)點(diǎn)171. *說(shuō)明:172. *1.知道在哈希表某處的單鏈表中,并開始遍歷.173. *2.返回的是查詢節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指針.這么做是為了做刪除操作.174. 輸入:pos:哈希表數(shù)組位置,從0開始計(jì)數(shù)175. id:所需要查詢節(jié)點(diǎn)的id176. root:如果是根節(jié)點(diǎn),則*root=1,否則為0177. 返回:所需查詢的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指針,如果是根節(jié)點(diǎn)則返回根節(jié)點(diǎn),失敗返回0178. */179. 180. Link_Node_Ptrsearch_link_node(uint16_tid,uint8_t*root)181. 182. Link_Node_Ptrnode;183. uint8_tpos=0;184. 185. /用哈希函數(shù)獲得位置186. pos=hash_func(id);187. 188. /獲取根節(jié)點(diǎn)189. node=Hash_Tablepos-next;190. 191. /判斷單鏈表是否存在192. if(node=NULL)193. 194. return0;195. 196. 197. /判斷是否是根節(jié)點(diǎn)198. if(node-id=id)199. 200. /是根節(jié)點(diǎn)201. *root=1;202. returnnode;203. 204. else205. 206. /不是根節(jié)點(diǎn)207. *root=0;208. /遍歷209. while(node-next!=NULL)210. 211. if(node-next-id=id)212. 213. returnnode;214. 215. else216. 217. node=node-n