想不明白hash查找為什么快
想不明白hash查找為什么快
/* These functions are based on Peter J. Weinberger\’s hash function (from the Dragon Book). The constant 24 in the original function was replaced with 23 to produce fewer collisions on input such as \”a\”, \”aa\”, \”aaa\”, \”aaaa\”, …*/static uint hash(const uchar *p, int n){ uint h = 0; uint g; while (n–) { h = (h << 4) + *p++; if ((g = (h & 0xf0000000)) != 0) h ^= g >> 23; h &= ~g; } return h;}以上是一個hash函數(shù)，hash函數(shù)本身的復(fù)雜度是o(n)的，比如計算string a的百科hash值，復(fù)雜度和比較string a == b差不多，加減乘除對計算機(jī)來說還是很快的，想想指令系統(tǒng)里的那些指令，hash函數(shù)的沖突概率還是很小的(與hash函數(shù)設(shè)計有關(guān))。
從檢索的角度看，Hash技術(shù)的檢索效率**，從Hash技術(shù)的角度論述檢索快的原因
如果你寫的hash函數(shù)不好的話，hash表可以退化為線性表，hash函數(shù)，你可以想一想為什么這么快呢？因為他利用了所存數(shù)據(jù)的結(jié)構(gòu)，就拿用hash表存字符串來說，他正是利用了字符串的結(jié)構(gòu)，比如舉個例子，hash(str)=27*27*str[2]+27*str[1]+str[0]，通過這個就區(qū)分出了abc和acb的不同了但是hash函數(shù)也有缺點，一點點變動對于他的影響都是很大的，首先開辟更大的內(nèi)存空間和copy數(shù)據(jù)不說，還要從新定義hash函數(shù)凡事有利有弊
簡要回答哈希表這種數(shù)據(jù)結(jié)構(gòu)應(yīng)用在查找操作中的優(yōu)勢？
優(yōu)勢：
從時間和空間的角度分析：
時間高效：利用哈?？墒共迦?、查找、刪除、修改、替換操作的時間復(fù)雜度達(dá)到O(1)，這是其他查找方式無法達(dá)到的（比如樹形查找O(logn)、二分查找O(logn)、順序查找O(n)等）。即使出現(xiàn)碰撞，整體理論值也可以接近O(1)。
空間可接受：哈希的比較合適的空間消耗以O(shè)(2n)**，對于其他同類算法（主要是樹形查找方式），要分為兩類。
**種是以葉子存放有效值的樹(如b+樹、線段樹)，其空間消耗可認(rèn)為是O(4n);第二種是所有節(jié)點均存放有效值，空間消耗可認(rèn)為O(n)。
[筆記]為什么hashmap查詢速度快? 如何理解hashmap的散列?
舉個例子，通訊錄 a-z 進(jìn)行分組，2萬個好友，如果不進(jìn)行分組，最差的時候要查2萬次，平均找1萬次，那么通過建立索引，要提高很多倍了。 但是我要跟大家說一個笑話，如果你的好友全是你的子孫，全跟你姓，那結(jié)果還是一樣的 哈哈，除非不用姓。
那么 hashmap 是通過hashcode進(jìn)行散列，hashcode 是如何分組不得而知，但是原理也是一樣，盡可能的平均分布 均勻 ，比如1萬個數(shù)據(jù)如果 只有10個組，或者說 100個組里面數(shù)據(jù)全部在 **個組，這效率還是一樣 速度比簡單粗暴的list 更慢了，為什么速度更慢了？ 比如1萬個數(shù)據(jù) 分了100個組，但是數(shù)據(jù)在 第100組，是不是要查找100個組 然后找了100個組還不夠，還要繼續(xù) 循環(huán)1萬次，這速度當(dāng)然是沒有提升反而更慢了。
