电脑知识|欧美黑人一区二区三区|软件|欧美黑人一级爽快片淫片高清|系统|欧美黑人狂野猛交老妇|数据库|服务器|编程开发|网络运营|知识问答|技术教程文章 - 好吧啦网

您的位置:首頁技術文章
文章詳情頁

PHP哈希表實現算法原理解析

瀏覽:88日期:2022-09-08 14:38:28

在PHP內核中,其中一個很重要的數據結構就是HashTable。我們常用的數組,在內核中就是用HashTable來實現。那么,PHP的HashTable是怎么實現的呢?最近在看HashTable的數據結構,但是算法書籍里面沒有具體的實現算法,剛好最近也在閱讀PHP的源碼,于是參考PHP的HashTable的實現,自己實現了一個簡易版的HashTable,總結了一些心得,下面給大家分享一下。

HashTable的介紹

哈希表是實現字典操作的一種有效數據結構。

定義

簡單地說,HashTable(哈希表)就是一種鍵值對的數據結構。支持插入,查找,刪除等操作。在一些合理的假設下,在哈希表中的所有操作的時間復雜度是O(1)(對相關證明感興趣的可以自行查閱)。

實現哈希表的關鍵

在哈希表中,不是使用關鍵字做下標,而是通過哈希函數計算出key的哈希值作為下標,然后查找/刪除時再計算出key的哈希值,從而快速定位元素保存的位置。

在一個哈希表中,不同的關鍵字可能會計算得到相同的哈希值,這叫做“哈希沖突”,就是處理兩個或多個鍵的哈希值相同的情況。解決哈希沖突的方法有很多,開放尋址法,拉鏈法等等。

因此,實現一個好的哈希表的關鍵就是一個好的哈希函數和處理哈希沖突的方法。

Hash函數

判斷一個哈希算法的好壞有以下定義:

一致性,等價的鍵必然產生相等的哈希值; 高效性,計算簡便; 均勻性,均勻地對所有的鍵進行哈希。 哈希函數建立了關鍵值與哈希值的對應關系,即:h = hash_func(key)。對應關系見下圖:

hash-exam

設計一個完美的哈希函數就交由專家去做吧,我們只管用已有的較成熟的哈希函數就好了。PHP內核使用的哈希函數是time33函數,又叫DJBX33A,其實現如下:

static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength){ register ulong hash = 5381; /* variant with the hash unrolled eight times */ for (; nKeyLength >= 8; nKeyLength -= 8) { hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; } switch (nKeyLength) { case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 1: hash = ((hash << 5) + hash) + *arKey++; break; case 0: break; EMPTY_SWITCH_DEFAULT_CASE() } return hash;}

注:函數使用了一個8次循環+switch來實現,是對for循環的優化,減少循環的運行次數,然后在switch里面執行剩下的沒有遍歷到的元素。

拉鏈法

將所有具有相同哈希值的元素都保存在一條鏈表中的方法叫拉鏈法。查找的時候通過先計算key對應的哈希值,然后根據哈希值找到對應的鏈表,最后沿著鏈表順序查找相應的值。

PHP的HashTable結構

簡單地介紹了哈希表的數據結構之后,繼續看看PHP中是如何實現哈希表的。

PHP內核hashtable的定義:

typedef struct _hashtable { uint nTableSize; uint nTableMask; uint nNumOfElements; ulong nNextFreeElement; Bucket *pInternalPointer; Bucket *pListHead; Bucket *pListTail; Bucket **arBuckets; dtor_func_t pDestructor; zend_bool persistent; unsigned char nApplyCount; zend_bool bApplyProtection; #if ZEND_DEBUGint inconsistent; #endif} HashTable; nTableSize,HashTable的大小,以2的倍數增長 nTableMask,用在與哈希值做與運算獲得該哈希值的索引取值,arBuckets初始化后永遠是nTableSize-1 nNumOfElements,HashTable當前擁有的元素個數,count函數直接返回這個值 nNextFreeElement,表示數字鍵值數組中下一個數字索引的位置 pInternalPointer,內部指針,指向當前成員,用于遍歷元素 pListHead,指向HashTable的第一個元素,也是數組的第一個元素 pListTail,指向HashTable的最后一個元素,也是數組的最后一個元素。與上面的指針結合,在遍歷數組時非常方便,比如reset和endAPI arBuckets,包含bucket組成的雙向鏈表的數組,索引用key的哈希值和nTableMask做與運算生成 pDestructor,刪除哈希表中的元素使用的析構函數 persistent,標識內存分配函數,如果是TRUE,則使用操作系統本身的內存分配函數,否則使用PHP的內存分配函數 nApplyCount,保存當前bucket被遞歸訪問的次數,防止多次遞歸 bApplyProtection,標識哈希表是否要使用遞歸保護,默認是1,要使用

舉一個哈希與mask結合的例子:

例如,”foo”真正的哈希值(使用DJBX33A哈希函數)是193491849。如果我們現在有64容量的哈希表,我們明顯不能使用它作為數組的下標。取而代之的是通過應用哈希表的mask,然后只取哈希表的低位。

hash | 193491849 | 0b1011100010000111001110001001& mask | & 63 | & 0b0000000000000000000000111111----------------------------------------------------------------------= index | = 9| = 0b0000000000000000000000001001

因此,在哈希表中,foo是保存在arBuckets中下標為9的bucket向量中。

bucket結構體的定義

typedef struct bucket { ulong h; uint nKeyLength; void *pData; void *pDataPtr; struct bucket *pListNext; struct bucket *pListLast; struct bucket *pNext; struct bucket *pLast; const char *arKey;} Bucket; h,哈希值(或數字鍵值的key nKeyLength,key的長度 pData,指向數據的指針 pDataPtr,指針數據 pListNext,指向HashTable中的arBuckets鏈表中的下一個元素 pListLast,指向HashTable中的arBuckets鏈表中的上一個元素 pNext,指向具有相同hash值的bucket鏈表中的下一個元素 pLast,指向具有相同hash值的bucket鏈表中的上一個元素 arKey,key的名稱

PHP中的HashTable是采用了向量加雙向鏈表的實現方式,向量在arBuckets變量保存,向量包含多個bucket的指針,每個指針指向由多個bucket組成的雙向鏈表,新元素的加入使用前插法,即新元素總是在bucket的第一個位置。由上面可以看到,PHP的哈希表實現相當復雜。這是它使用超靈活的數組類型要付出的代價。

HashTable相關API

zend_hash_init zend_hash_add_or_update zend_hash_find zend_hash_del_key_or_index

zend_hash_init

函數執行步驟

設置哈希表大小

設置結構體其他成員變量的初始值 (包括釋放內存用的析構函數pDescructor)詳細代碼注解點擊:zend_hash_init源碼

注:

1、pHashFunction在此處并沒有用到,php的哈希函數使用的是內部的zend_inline_hash_func

2、zend_hash_init執行之后并沒有真正地為arBuckets分配內存和計算出nTableMask的大小,真正分配內存和計算nTableMask是在插入元素時進行CHECK_INIT檢查初始化時進行。

zend_hash_add_or_update

函數執行步驟

檢查鍵的長度 檢查初始化 計算哈希值和下標 遍歷哈希值所在的bucket,如果找到相同的key且值需要更新,則更新數據,否則繼續指向bucket的下一個元素,直到指向bucket的最后一個位置 為新加入的元素分配bucket,設置新的bucket的屬性值,然后添加到哈希表中

如果哈希表空間滿了,則重新調整哈希表的大小

zend_hash_add_or_update

CONNECT_TO_BUCKET_DLLIST是將新元素添加到具有相同hash值的bucket鏈表。

CONNECT_TO_GLOBAL_DLLIST是將新元素添加到HashTable的雙向鏈表。

詳細代碼和注解請點擊:zend_hash_add_or_update代碼注解。

zend_hash_find

函數執行步驟

計算哈希值和下標 遍歷哈希值所在的bucket,如果找到key所在的bucket,則返回值,否則,指向下一個bucket,直到指向bucket鏈表中的最后一個位置

詳細代碼和注解請點擊:zend_hash_find代碼注解。

zend_hash_del_key_or_index

函數執行步驟

計算key的哈希值和下標 遍歷哈希值所在的bucket,如果找到key所在的bucket,則進行第三步,否則,指向下一個bucket,直到指向bucket鏈表中的最后一個位置 如果要刪除的是第一個元素,直接將arBucket[nIndex]指向第二個元素;其余的操作是將當前指針的last的next執行當前的next 調整相關指針 釋放數據內存和bucket結構體內存

詳細代碼和注解請點擊:zend_hash_del_key_or_index代碼注解。

性能分析

PHP的哈希表的優點:PHP的HashTable為數組的操作提供了很大的方便,無論是數組的創建和新增元素或刪除元素等操作,哈希表都提供了很好的性能,但其不足在數據量大的時候比較明顯,從時間復雜度和空間復雜度看看其不足。

不足如下:

保存數據的結構體zval需要單獨分配內存,需要管理這個額外的內存,每個zval占用了16bytes的內存; 在新增bucket時,bucket也是額外分配,也需要16bytes的內存; 為了能進行順序遍歷,使用雙向鏈表連接整個HashTable,多出了很多的指針,每個指針也要16bytes的內存; 在遍歷時,如果元素位于bucket鏈表的尾部,也需要遍歷完整個bucket鏈表才能找到所要查找的值

PHP的HashTable的不足主要是其雙向鏈表多出的指針及zval和bucket需要額外分配內存,因此導致占用了很多內存空間及查找時多出了不少時間的消耗。

后續

上面提到的不足,在PHP7中都很好地解決了,PHP7對內核中的數據結構做了一個大改造,使得PHP的效率高了很多,因此,推薦PHP開發者都將開發和部署版本更新吧。看看下面這段PHP代碼:

<?php$size = pow(2, 16); $startTime = microtime(true);$array = array();for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) { $array[$key] = 0;}$endTime = microtime(true);echo ’插入 ’, $size, ’ 個惡意的元素需要 ’, $endTime - $startTime, ’ 秒’, 'n'; $startTime = microtime(true);$array = array();for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) { $array[$key] = 0;}$endTime = microtime(true);echo ’插入 ’, $size, ’ 個普通元素需要 ’, $endTime - $startTime, ’ 秒’, 'n';

上面這個demo是有多個hash沖突時和無沖突時的時間消耗比較。筆者在PHP5.4下運行這段代碼,結果如下

插入 65536 個惡意的元素需要 43.72204709053 秒

插入 65536 個普通元素需要 0.009843111038208 秒

而在PHP7上運行的結果:

插入 65536 個惡意的元素需要 4.4028408527374 秒

插入 65536 個普通元素需要 0.0018510818481445 秒

可見不論在有沖突和無沖突的數組操作,PHP7的性能都提升了不少,當然,有沖突的性能提升更為明顯。至于為什么PHP7的性能提高了這么多,值得繼續深究。

最后再安利一下,筆者github上有一個簡易版的HashTable的實現:HashTable實現

另外,我在github有對PHP源碼更詳細的注解。感興趣的可以圍觀一下,給個star。PHP5.4源碼注解。可以通過commit記錄查看已添加的注解。

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持好吧啦網。

標簽: PHP
相關文章:
主站蜘蛛池模板: 篷房|仓储篷房|铝合金篷房|体育篷房|篷房厂家-华烨建筑科技官网 知名电动蝶阀,电动球阀,气动蝶阀,气动球阀生产厂家|价格透明-【固菲阀门官网】 | 面粉仓_储酒罐_不锈钢储酒罐厂家-泰安鑫佳机械制造有限公司 | 软文发布平台 - 云软媒网络软文直编发布营销推广平台 | 铜镍-康铜-锰铜-电阻合金-NC003 - 杭州兴宇合金有限公司 | 动物解剖台-成蚊接触筒-标本工具箱-负压实验台-北京哲成科技有限公司 | 在线浊度仪_悬浮物污泥浓度计_超声波泥位计_污泥界面仪_泥水界面仪-无锡蓝拓仪表科技有限公司 | 钢制暖气片散热器_天津钢制暖气片_卡麦罗散热器厂家 | 钢丝绳探伤仪-钢丝绳检测仪-钢丝绳探伤设备-洛阳泰斯特探伤技术有限公司 | 房车价格_依维柯/大通/东风御风/福特全顺/江铃图片_云梯搬家车厂家-程力专用汽车股份有限公司 | 广东高华家具-公寓床|学生宿舍双层铁床厂家【质保十年】 | 干洗加盟网-洗衣店品牌排行-干洗设备价格-干洗连锁加盟指南 | 河北中仪伟创试验仪器有限公司是专业生产沥青,土工,水泥,混凝土等试验仪器的厂家,咨询电话:13373070969 | 不发火防静电金属骨料_无机磨石_水泥自流平_修补砂浆厂家「圣威特」 | 纸塑分离机-纸塑分离清洗机设备-压力筛-碎浆机厂家金双联环保 | 天长市晶耀仪表有限公司 | 齿辊分级破碎机,高低压压球机,立式双动力磨粉机-郑州长城冶金设备有限公司 | 雪花制冰机(实验室雪花制冰机)百科| 实验室装修_实验室设计_实验室规划设计- 上海广建净化工程公司 | 台湾阳明固态继电器-奥托尼克斯光电传感器-接近开关-温控器-光纤传感器-编码器一级代理商江苏用之宜电气 | 热处理温控箱,热处理控制箱厂家-吴江市兴达电热设备厂 | 青岛侦探_青岛侦探事务所_青岛劝退小三_青岛婚外情取证-青岛王军侦探事务所 | 碎石机设备-欧版反击破-欧版颚式破碎机(站)厂家_山东奥凯诺机械 高低温试验箱-模拟高低温试验箱订制-北京普桑达仪器科技有限公司【官网】 | 智慧农业|农业物联网|现代农业物联网-托普云农物联网官方网站 | 振动筛,震动筛,圆形振动筛,振动筛价格,振动筛厂家-新乡巨宝机电 蒸汽热收缩机_蒸汽发生器_塑封机_包膜机_封切收缩机_热收缩包装机_真空机_全自动打包机_捆扎机_封箱机-东莞市中堡智能科技有限公司 | 螺杆泵_中成泵业 | 苏州柯瑞德货架-仓库自动化改造解决方案 | 广东健伦体育发展有限公司-体育工程配套及销售运动器材的体育用品服务商 | 一体化预制泵站-一体化提升泵站-一体化泵站厂家-山东康威环保 | 带式过滤机厂家_价格_型号规格参数-江西核威环保科技有限公司 | 电抗器-能曼电气-电抗器专业制造商 | 菲希尔X射线测厚仪-菲希尔库伦法测厚仪-无锡骏展仪器有限责任公司 | 欧美日韩国产一区二区三区不_久久久久国产精品无码不卡_亚洲欧洲美洲无码精品AV_精品一区美女视频_日韩黄色性爱一级视频_日本五十路人妻斩_国产99视频免费精品是看4_亚洲中文字幕无码一二三四区_国产小萍萍挤奶喷奶水_亚洲另类精品无码在线一区 | 激光内雕_led玻璃_发光玻璃_内雕玻璃_导光玻璃-石家庄明晨三维科技有限公司 激光内雕-内雕玻璃-发光玻璃 | 印刷人才网 印刷、包装、造纸,中国80%的印刷企业人才招聘选印刷人才网! | 苹果售后维修点查询,苹果iPhone授权售后维修服务中心 – 修果网 拼装地板,悬浮地板厂家,悬浮式拼装运动地板-石家庄博超地板科技有限公司 | 网站优化公司_北京网站优化_抖音短视频代运营_抖音关键词seo优化排名-通则达网络 | 广东护栏厂家-广州护栏网厂家-广东省安麦斯交通设施有限公司 | 苏州柯瑞德货架-仓库自动化改造解决方案 | 净化车间_洁净厂房_净化公司_净化厂房_无尘室工程_洁净工程装修|改造|施工-深圳净化公司 | 液氮罐_液氮容器_自增压液氮罐-北京君方科仪科技发展有限公司 | 顶空进样器-吹扫捕集仪-热脱附仪-二次热解吸仪-北京华盛谱信仪器 |