差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- cs:dsa:courses:gtx_1332x:ii_non_linear:start [2024/03/25 12:25] – [Quadratic Probing] codinghare
+++ cs:dsa:courses:gtx_1332x:ii_non_linear:start [2024/04/14 14:21] (当前版本) – [原理：双子节点的情况] codinghare
@@ 行 200: / 行 200: @@
 //Predecessor//（**最大前继**） 是指在 BST 中，比 root **小**的节点中**最大**的一个节点；而 //Successor//（**最大后继**） 是指在 BST 中，比 root **大**的节点中**最小**的一个节点。比如下面 BST 中的 ''21'' 和 ''30'' 就是 root ''24'' 的最大前继和最小后继：
 \\ \\
-{{ :cs:dsa:courses:gtx_1332x:ii_non_linear:prede_n_successor.svg?250 |}}
+{{ :cs:dsa:courses:gtx_1332x:ii_non_linear:prede_n_successor_1_.svg?250 |}}
   * **//为什么要使用 Predecessor 和  Successor？该如何使用？//**
 这种解决方案来源于一种很朴素的想法，化繁为简。首先可以明确的是，直接删除拥有两个子节点的节点，并且还要保证 BST 的结构不出问题，是非常困难的。但相比之下，删除只有一个子节点或者没有子节点的节点则非常简单。因此，相比直接删除节点，我们选择**替换**节点中的内容，而这正是使用 Predecessor 或 Successor 的精妙之处。
@@ 行 480: / 行 480: @@
 </WRAP>
 ===Quadratic Probing===
-//Linear Probing// 带来的问题被称为 //**primary clustering**（turtling）//。该问题指当 hash map 中**连续**的区域越来越大时（这是必然的，因为递增找空最终会将整个 hashmap 变为连续的区块。），我们每做一次 Probing 找空位都要跨越之前的连续区块。因此，我们需要一种更快的方式来找空位。
+//Linear Probing// 带来的问题被称为 //**primary clustering**// (//turtling//)。该问题指当 hash map 中**连续**的区域越来越大时（这是必然的，因为递增找空最终会将整个 hashmap 变为连续的区块。），我们每做一次 Probing 找空位都要跨越之前的连续区块。因此，我们需要一种更快的方式来找空位。
 \\ \\
 一种方式是将之前计算 index 中的 ''(h + oriIndex) % backArray.length'' 更改为：
@@ 行 493: / 行 493: @@
   * 数学上，如果使用**质数**作为 Hash table 的长度，且 laoding factor 不超过 ''0.5''，则该种情况不会出现。
 ===Double Hashing===
+//Double Hashing// 通过综合使用 linear / quadratic Probing，在降低 probing clustering 的同时，尽量优化了性能。通常，//Double Hashing// 包含两个 hash function：
+  *  $H(k)$ ：计算 index 的哈希函数：''h(k) % q''，''q'' 是小于哈希表长度的某个**质数**
+  *  $D(k)$ : 基于  $H(k)$  计算 probing 的值 ：''q - (h(k) % q''
+<WRAP center round box 100%>
+Linear Probing 可以被视作是 double hashing 的特殊形式。
+</WRAP>
 ====Preformance====
 ==SkipList==
@@ 行 502: / 行 509: @@
 ==Heap==
 ^Operation^Best^Average^Worst^
-|Find Min / max| $O(1)$ | $O(1)$ | $O(1)$ |
+|**//Find Min// / max**| $O(1)$ | $O(1)$ | $O(1)$ |
-|Add| $O(1)$ | $O(1)$ |$O(n)/O(log(n))*$|
+|**//Add//**| $O(1)$ | $O(1)$ |$O(n)/O(log(n))*$|
-|Remove Min/max| $O(1)$ | $O(log(n))$ | $O(log(n))$ |
+|**//Remove Min/max//**| $O(1)$ | $O(log(n))$ | $O(log(n))$ |
-|Aribitray Search/Remove| $O(1)$ | $O(n)$ | $O(n)$ |
+|**//Aribitray Search//**/Remove| $O(1)$ | $O(n)$ | $O(n)$ |
-|BuildHeap|- $O(n)$ | $O(n)$ | $O(n)$ |
+|**//BuildHeap//**|- $O(n)$ | $O(n)$ | $O(n)$ |
-|Space Complexity| $O(n)$ | $O(n)$ | $O(n)$ |
+|**//Space Complexity//**| $O(n)$ | $O(n)$ | $O(n)$ |
+==HashMap==
+^Operation^Best^Average^Worst^
+|Put / Add New Key (Closed Addressing)| $O(1)$ | $O(1)$ | $O(n)$ |
+|Put / Add New Key (Open Addressing)| $O(1)$ | $O(1)$ | $O(n)^*$  /  $O(n^2)$ |
+|Remove Key| $O(1)$ | $O(1)$ | $O(n)$ |
+|Searching for a Key| $O(1)$ | $O(1)$ | $O(n)$ |
+|Obtaining a KeySet| $O(1)$ | $O(1)$ | $O(n)$ |
+|Obtaining a List of Values| $O(1)$ | $O(1)$ | $O(n)$ |

What & How & Why

[ About ]

[ My Links ]

[ Notice ]

页面工具

站点工具

用户工具

差别