hash 是什麼
可以很簡單的理解為“摘要”
就是將一段資料對映到有限長度的資料,比如說原資料是一段非常長的字串m,那麼hash的數字h就代表的該字串。
A hash function is any function that can be used to map data of arbitrary size to data of fixed size. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. One use is a data structure called a hash table, widely used in computer software for rapid data lookup.
hash值是怎麼產生的
對m進行計算(進行有失真壓縮)並輸出為一個固定長度的值
hash碰撞
由不同的原始資料壓縮時產生了相同的結果,生成的hash值一致
hash碰撞的解決方案
Probing , 在array找出一個空的位置。
試想如果我們計算10個元素的hash值都一樣,那麼每次存放和讀取都會發生Probing,讀取時間就會變成最高Ο(n)複雜度。
一個簡單的策略是,當字典中存放的元素超過70%,就擴大字典體積。
Hash 攻擊
即重複傳送相同hash值的原資料,這樣會導致耗時很大,由於每一次的插入都會造成hash碰撞,從而hash table將會退化為連結串列
Reference
https://www.zhihu.com/question/26762707
https://www.kawabangga.com/posts/2493
http://www.laruence.com/2011/12/30/2435.html
想要看到更多瑋哥的學習筆記、考試複習資料、面試準備資料?想要看到IBM工作時期的技術積累和國外初創公司的經驗總結?
image
敬請關注: