首頁 php教程 php手册 PHP数组的Hash冲突实例

PHP数组的Hash冲突实例

Jun 21, 2016 am 08:52 AM
array hash key php size

  PHP数组的Hash冲突实例,你知道不知道, 插入65536个经过构造的键值的元素到PHP数组, 会需要耗时30秒以上? 而一般的这个过程仅仅需要0.1秒..

 

  请看如下的例子:

$size = pow(2, 16);

$startTime = microtime(true);

$array = array();

for ($key = 0, $maxKey = ($size - 1) * $size; $key

}$endTime = microtime(true);

echo '插入 ', $size, ' 个恶意的元素需要 ', $endTime - $startTime, ' 秒', "\n"; $startTime = microtime(true);

$array = array();

for ($key = 0, $maxKey = $size - 1;

$key

echo '插入 ', $size, ' 个普通元素需要 ', $endTime - $startTime, ' 秒', "\n";

  上面的例子, 在我的机器上的执行结果如下:

  插入 65536 个恶意的元素需要 43.1438360214 秒插入 65536 个普通元素需要 0.0210378170013 秒

  这个差别是不是很夸张?!

  我在上一篇文章中介绍过, 经过特殊构造的键值, 使得PHP每一次插入都会造成Hash冲突, 从而使得PHP中array的底层Hash表退化成链表:

  Hash collision

  这样在每次插入的时候PHP都需要遍历一遍这个链表, 大家可以想象, 第一次插入, 需要遍历0个元素, 第二次是1个, 第三次是3个, 第65536个是65535个, 那么总共就需要65534*65535/2=2147385345次遍历….

  那么, 这个键值是怎么构造的呢?

  在PHP中,如果键值是数字, 那么Hash的时候就是数字本身, 一般的时候都是, index & tableMask. 而tableMask是用来保证数字索引不会超出数组可容纳的元素个数值, 也就是数组个数-1.

  PHP的Hashtable的大小都是2的指数, 比如如果你存入10个元素的数组, 那么数组实际大小是16, 如果存入20个, 则实际大小为32, 而63个话, 实际大小为64. 当你的存入的元素个数大于了数组目前的最多元素个数的时候, PHP会对这个数组进行扩容, 并且从新Hash.

  现在, 我们假设要存入64个元素(中间可能会经过扩容, 但是我们只需要知道, 最后的数组大小是64, 并且对应的tableMask为63:0111111), 那么如果第一次我们存入的元素的键值为0, 则hash后的值为0, 第二次我们存入64, hash(1000000 & 0111111)的值也为0, 第三次我们用128, 第四次用192… 就可以使得底层的PHP数组把所有的元素都Hash到0号bucket上, 从而使得Hash表退化成链表了.

  当然, 如果键值是字符串的话, 就稍微比较麻烦一些了, 但是PHP的Hash算法是开源的, 已知的, 所以有心人也可以做到…

  本文地址: http://www.laruence.com/2011/12/30/2435.html



本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

<🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系統,解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1666
14
CakePHP 教程
1425
52
Laravel 教程
1325
25
PHP教程
1273
29
C# 教程
1252
24
PHP和Python:比較兩種流行的編程語言 PHP和Python:比較兩種流行的編程語言 Apr 14, 2025 am 12:13 AM

PHP和Python各有優勢,選擇依據項目需求。 1.PHP適合web開發,尤其快速開發和維護網站。 2.Python適用於數據科學、機器學習和人工智能,語法簡潔,適合初學者。

PHP:網絡開發的關鍵語言 PHP:網絡開發的關鍵語言 Apr 13, 2025 am 12:08 AM

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

PHP行動:現實世界中的示例和應用程序 PHP行動:現實世界中的示例和應用程序 Apr 14, 2025 am 12:19 AM

PHP在電子商務、內容管理系統和API開發中廣泛應用。 1)電子商務:用於購物車功能和支付處理。 2)內容管理系統:用於動態內容生成和用戶管理。 3)API開發:用於RESTfulAPI開發和API安全性。通過性能優化和最佳實踐,PHP應用的效率和可維護性得以提升。

PHP與Python:了解差異 PHP與Python:了解差異 Apr 11, 2025 am 12:15 AM

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

PHP的持久相關性:它還活著嗎? PHP的持久相關性:它還活著嗎? Apr 14, 2025 am 12:12 AM

PHP仍然具有活力,其在現代編程領域中依然佔據重要地位。 1)PHP的簡單易學和強大社區支持使其在Web開發中廣泛應用;2)其靈活性和穩定性使其在處理Web表單、數據庫操作和文件處理等方面表現出色;3)PHP不斷進化和優化,適用於初學者和經驗豐富的開發者。

PHP和Python:代碼示例和比較 PHP和Python:代碼示例和比較 Apr 15, 2025 am 12:07 AM

PHP和Python各有優劣,選擇取決於項目需求和個人偏好。 1.PHP適合快速開發和維護大型Web應用。 2.Python在數據科學和機器學習領域佔據主導地位。

PHP與其他語言:比較 PHP與其他語言:比較 Apr 13, 2025 am 12:19 AM

PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

PHP和Python:解釋了不同的範例 PHP和Python:解釋了不同的範例 Apr 18, 2025 am 12:26 AM

PHP主要是過程式編程,但也支持面向對象編程(OOP);Python支持多種範式,包括OOP、函數式和過程式編程。 PHP適合web開發,Python適用於多種應用,如數據分析和機器學習。

See all articles