据此哈希函数，最后两位相同的 key 都会被映 射到相同的桶。而通过线性探测，它们被依次存储在该桶以及之下的桶中。 图 6‑6 开放寻址（线性探测）哈希表的键值对分布 然而，线性探测容易产生“聚集现象”。具体来说，数组中连续被占用的位置越长，这些连续位置发生哈希冲 突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。 值得注意的是，我们不能在开放寻 定的步数，而是跳过“探测次数的平方”的步数，即 1, 4, 9, … 步。 平方探测主要具有以下优势。 ‧ 平方探测通过跳过探测次数平方的距离，试图缓解线性探测的聚集效应。 ‧ 平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀。 然而，平方探测并不是完美的。 ‧ 仍然存在聚集现象，即某些位置比其他位置更容易被占用。 ‧ 由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能 ，以此类推，直到找到空位后插入元素。 ‧ 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；若遇到空位或已尝试所有哈 希函数，说明哈希表中不存在该元素，则返回 None 。 与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量。 Tip 请注意，开放寻址（线性探测、平方探测和多次哈希）哈希表都存在“不能直接删除元素”的问题。 6.2.3 编程语言的选择 各种编程语言采取了不同的哈希表实现策略，下面举几个例子。

据此哈希函数，最后两位相同的 key 都会被映 射到相同的桶。而通过线性探测，它们被依次存储在该桶以及之下的桶中。 图 6‑6 开放寻址（线性探测）哈希表的键值对分布 然而，线性探测容易产生“聚集现象”。具体来说，数组中连续被占用的位置越长，这些连续位置发生哈希冲 突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。 值得注意的是，我们不能在开放寻 定的步数，而是跳过“探测次数的平方”的步数，即 1, 4, 9, … 步。 平方探测主要具有以下优势。 ‧ 平方探测通过跳过探测次数平方的距离，试图缓解线性探测的聚集效应。 ‧ 平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀。 然而，平方探测并不是完美的。 ‧ 仍然存在聚集现象，即某些位置比其他位置更容易被占用。 ‧ 由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能 ，以此类推，直到找到空位后插入元素。 ‧ 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；若遇到空位或已尝试所有哈 希函数，说明哈希表中不存在该元素，则返回 None 。 与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量。 Tip 请注意，开放寻址（线性探测、平方探测和多次哈希）哈希表都存在“不能直接删除元素”的问题。 6.2.3 编程语言的选择 各种编程语言采取了不同的哈希表实现策略，下面举几个例子。

據此雜湊函式，最後兩位相同的 key 都會被對 映到相同的桶。而透過線性探查，它們被依次儲存在該桶以及之下的桶中。 圖 6‑6 開放定址（線性探查）雜湊表的鍵值對分佈 然而，線性探查容易產生“聚集現象”。具體來說，陣列中連續被佔用的位置越長，這些連續位置發生雜湊衝 突的可能性越大，從而進一步促使該位置的聚堆積生長，形成惡性迴圈，最終導致增刪查改操作效率劣化。 值得注意的是，我們不能在開放 定的步數，而是跳過“探測次數的平方”的步數，即 1, 4, 9, … 步。 平方探測主要具有以下優勢。 ‧ 平方探測透過跳過探測次數平方的距離，試圖緩解線性探查的聚集效應。 ‧ 平方探測會跳過更大的距離來尋找空位置，有助於資料分佈得更加均勻。 然而，平方探測並不是完美的。 ‧ 仍然存在聚集現象，即某些位置比其他位置更容易被佔用。 ‧ 由於平方的增長，平方探測可能不會探測整個雜湊表，這意味著即使雜湊表中有空桶，平方探測也可能 ，以此類推，直到找到空位後插入元素。 ‧ 查詢元素：在相同的雜湊函式順序下進行查詢，直到找到目標元素時返回；若遇到空位或已嘗試所有雜 湊函式，說明雜湊表中不存在該元素，則返回 None 。 與線性探查相比，多次雜湊方法不易產生聚集，但多個雜湊函式會帶來額外的計算量。 Tip 請注意，開放定址（線性探查、平方探測和多次雜湊）雜湊表都存在“不能直接刪除元素”的問題。 6.2.3 程式語言的選擇 各種程式語言採取了不同的雜湊表實現策略，下面舉幾個例子。

result = runTransformation(repeatFun) // OK //sampleEnd println("result = $result") } 默认情况下推断出的是没有接收者的函数类型，即使变量是通过扩展函数 引用来初始化的。 如需改变这点，请显式指定变量类型。 函数类型实例调用 函数类型的值可以通过其 invoke(……) 操作符调用： f

runTransformation(repeatFun) // OK //sampleEnd lambda 表达式 566 println("result = $result") } 默认情况下推断出的是没有接收者的函数类型，即使变量是通过扩展函数引用来初始化 的。 如需改变这点，请显式指定变量类型。 函数类型实例调用 函数类型的值可以通过其 invoke(……) 操作符调用： f