php 實作Hash表功能
Hash表作為最重要的資料結構之一,也稱為散列表。使用PHP實作Hash表的功能。 PHP可以模擬實作Hash表的增刪改查。透過對key的映射到數組中的一個位置來存取。映射函數叫做Hash函數,存放記錄的陣列稱為Hash表。
Hash函數把任意長度的和類型的key轉換成固定長度輸出。不同的key可能擁有相同的hash。
Hash表的時間複雜度為O(1)
<?php class HashTable{ private $arr = array(); private $size = 10; public function __construct(){ //SplFixedArray创建的数组比一般的Array()效率更高,因为更接近C的数组。创建时需要指定尺寸 $this->arr = new SplFixedArray($this->size); } /** * Description: 简单hash算法。输入key,输出hash后的整数 * @param $key * @return int */ private function simpleHash($key){ $len = strlen($key); //key中每个字符所对应的ASCII的值 $asciiTotal = 0; for($i=0; $i<$len; $i++){ $asciiTotal += ord($key[$i]); } return $asciiTotal % $this->size; } /** * Description: 赋值 * @param $key * @param $value * @return bool */ public function set($key, $value){ $hash = $this->simpleHash($key); $this->arr[$hash] = $value; return true; } /** * Description: 取值 * @param $key * @return mixed */ public function get($key){ $hash = $this->simpleHash($key); return $this->arr[$hash]; } public function getList(){ return $this->arr; } public function editSize($size){ $this->size = $size; $this->arr->setSize($size); } } ?>
下面對我們的HashTable進行測試。
<?php //测试1 $arr = new HashTable(); for($i=0; $i<15; $i++){ $arr->set('key'.$i, 'value'.$i); } print_r($arr->getList()); //测试2 $arr->editSize(15); for($i=0; $i<15; $i++){ $arr->set('key'.$i, 'value'.$i); } print_r($arr->getList()); ?>
改變了值之後可以存放更多的元素。但是仍然存在不同的key可能產生相同的hash值,那麼賦值的時候後操作會覆寫前運算的問題。這種衝突的問題我們來用拉鍊法來解決。
拉鍊法解決衝突。拉鍊法解決衝突的做法是將所有的相同Hash值的key放在一個鍊錶中,例如key3和key14在hash之後都是0,那麼在數組的鍵為0的地方存儲這兩個值,形式是鍊錶。如果無法理解我的文字,請看下面的範例,看一下列印資訊就明白了。拉鍊法是什麼,就是鍊錶。
建立一個HashNode類,用來儲存key和value的值,並且儲存相同hash的另一個元素。在同一條鏈上,找出越後的元素越費時。時間複雜度為O(n).
<?php class HashNode{ public $key; public $value; public $nextNode; public function __construct($key, $value, $nextNode=Null){ $this->key = $key; $this->value = $value; $this->nextNode = $nextNode; } } class NewHashTable{ private $arr; private $size = 10; public function __construct(){ $this->arr = new SplFixedArray($this->size); } private function simpleHash($key){ $asciiTotal = 0; $len = strlen($key); for($i=0; $i<$len; $i++){ $asciiTotal += ord($key[$i]); } return $asciiTotal % $this->size; } public function set($key, $value){ $hash = $this->simpleHash($key); if(isset($this->arr[$hash])){ $newNode = new HashNode($key, $value, $this->arr[$hash]); }else{ $newNode = new HashNode($key, $value, null); } $this->arr[$hash] = $newNode; return true; } public function get($key){ $hash = $this->simpleHash($key); $current = $this->arr[$hash]; while(!empty($current)){ if($current->key == $key){ return $current->value; } $current = $current->nextNode; } return NULL; } public function getList(){ return $this->arr; } } ?>
對我們新的HashTable進行測試
<?php //测试1 $newArr = new NewHashTable(); for($i=0; $i<30; $i++){ $newArr->set('key'.$i, 'value'.$i); } print_r($newArr->getList()); var_dump($newArr->get('key3')); ?>
以上就是php 實作Hash表功能實例詳解 的內容,更多相關內容請關注PHP中文網(www.php.cn)!

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

方法:1、用“str_replace(" ","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\ \;||\xc2\xa0)/","其他字符",$str)”语句。

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

查找方法:1、用strpos(),语法“strpos("字符串值","查找子串")+1”;2、用stripos(),语法“strpos("字符串值","查找子串")+1”。因为字符串是从0开始计数的,因此两个函数获取的位置需要进行加1处理。


熱AI工具

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

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

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

Safe Exam Browser
Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

DVWA
Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

SublimeText3 英文版
推薦:為Win版本,支援程式碼提示!

EditPlus 中文破解版
體積小,語法高亮,不支援程式碼提示功能

SublimeText3 Linux新版
SublimeText3 Linux最新版