Re: [爆卦] 大學生推翻圖靈獎得主40年理論

作者: SkyIsMyLimit (天空才是我的極限)   2025-02-15 15:27:27
阿肥試著用白話文解釋,不深入探討。因為阿肥也只是略懂略懂。有大神看不下去的,請輕虐。
Hash 有兩種 set 跟map。map的做法呢一般又分兩種:array 跟 link list。這篇應該是著重在array這邊。一般情況下當array越來越滿,會發生碰撞,需要找出新的空位。40年理論是猜想使用greedy算法,普遍找空位的time complexity是log(n)。
而這篇提出的方法是把array切割為多個小塊,然後給這些小塊起編號以及紀錄;滿/空 的status。所以當碰撞發生時,查找就會快很多,普遍情況下會是O(1)。個人理解是相當於架一個樹在hash table上,進而達到優化查找時間,大guy是醬。

Links booklink

Contact Us: admin [ a t ] ucptt.com