Zákeřné pole

Školení, která pořádám

PHP pro uložení polí používá hashovací tabulky. Ty fungují tak, že při uložení každého prvku spočítají hash jeho klíče a prvek uloží do tabulky na základě této hodnoty (kromě toho se udržuje ještě spojový seznam prvků, aby se prvky daly procházet v tom pořadí, v jakém byly vloženy). Hashovací tabulky mají řadu užitečných vlastností, především dokážou prvek uložit a vyhledat v průměrném případě v konstantním čase (při přepočtu na jeden prvek). To znamená, že ať je pole jak chce veliké, tak základní operace s ním budou vždy rychlé.

<?php
/** Vytvoření zákeřného pole
* @param int hloubka zanoření ovlivňující počet vytvořených prvků
* @param string předpona klíčů
* @return array pole s prvky se stejným hašem klíčů
*/
function zakerne_pole($depth, $prefix = "", $i = 7) {
    if (!$depth) {
        return array($prefix => true);
    }
    $return = array();
    for ($j=0; $j <= 7; $j++) {
        $b = 33 * (7 - $i) + $j;
        $return += zakerne_pole($depth - 1, $prefix . chr($b), $j);
    }
    return $return;
}
?>

Jak je tedy možné, že je tato funkce tak příšerně pomalá a přitom se při změně konstanty 33 zázračně zrychlí? Důvodem je, že hash všech vytvořených klíčů je stejný – PHP pro výpočet hashe používá jednoduchou funkci Times 33, která pracuje tak, že hash nejprve nastaví na 5381 a pak postupuje po bajtech klíče, starý hash vždy vynásobí číslem 33 a přičte hodnotu bajtu. Možná si říkáte, proč není použitá nějaká osvědčená hashovací funkce jako třeba md5, u které by se pro nalezení kolize hodilo mít ve jméně W a G? Důvodem je rychlost – ostatně podívejte se do funkce zend_inline_hash_func, jak se jednoduchý algoritmus dá kvůli optimalizaci popsat složitě.

Jakub Vrána, Ze zákulisí, 14.11.2008, diskuse: 16 (nové: 0)

Diskuse

ikona David Grudl:

Jakube, nechtěl bys to W a G rozvést? Slyším o tom poprvé a docela by mě to zajímalo.

ikona Jakub Vrána OpenID:

To byl jen takový vtípek: http://en.wikipedia.org/wiki/Xiaoyun_Wang

ikona david@grudl.com:

Taktos mě dostal ;)

Ale ať taky přispěju s troškou do mlýna zákeřních polí. Zkuste si v libovolné verzi PHP od 5.0.0 do 5.1.2 spustit tento kód:

<?php
$arr
= array();
$arr['XB@'] = 'La';
$arr[2089710047] = 'Trine';
unset(
$arr['XB@']);
?>

Unset překvapivě odstraní prvek arr[2089710047]. Také to souvisí s hashovací funkcí.

ikona v6ak:

Nějak jim chybí použití kolizní funkce...

Karel:

Znamená to, že PHP je v případě polí nespolehlivé?
(A btw. existuje k tomuhle nějaký white-paper nebo bug report?)

ikona spaze:

Není, bylo. A to ve verzích 5.0.0 do 5.1.2, jak je psáno. Ale v těch verzích toho bylo špatně asi více ;)

Miloslav Ponkrác:

Já, když jsem psal svůj padesátidílný seriál o PHP na zive.cz, kde jsem tehdejší tuším ještě 5.0.2 po testech doporučil nepoužívat jako nespolehlivé a zatím zůstat u PHP 4. A jak se do mě pan Vrána pustil, co si to dovoluji tvrdit.

ikona Jakub Vrána OpenID:

Napsal jsem „autor … by to měl podložit nějakými argumenty“. To se mi nezdá úplně jako „puštění se“. Já PHP 5 používám od celkem raných verzí a problémy s ním jsem nikdy neměl větší než s PHP 4. http://www.zive.cz/Clanky/PHP--50-dil--budoucnost-…#ITEM_366001

Navíc konkrétně tato chyba se projevovala i do PHP 4.4.2: http://latrine.dgx.cz/php-surprise, takže to není příliš pádný argument o kvalitě PHP 4 ve srovnání PHP 5…

PHX:

Nejak mi nejde do hlavy, proc dane funkci vadi stejne hase. Spise bych cekal, ze to nebude fungovat, kdyz si to prepisuje prvky pole.

Dale mi prijde ze hash funcek Times33 musi dle tveho popisu vracet s rostoucim klicem roustouci cislo. Pri dlouhem klici se cislo hase bude blizit "nekonecnu". Osobne mam o hash predstavu, ze vraci vzdy konstantni delku vyledku.

ikona Jakub Vrána OpenID:

Protože dva prvky se stejným hashem se zapíšou do tabulky na stejné místo. Toto místo je pak potřeba prohledat ručně, takže složitost přidání prvku není konstantní, ale lineární.

Ano, číslo se neustále zvětšuje, ale pracuje se jen s posledními 32 bity.

ikona Jakub Vrána OpenID:

Jak objevil David Grudl, funkce správně funguje jen v PHP 5, protože PHP 4 používá jinou hashovací funkci (místo plus provádí xor).

pmg:

Děkuji za pěkný článek. Podle jakého vzorce stanoví PHP velikost hašovací tabulky, aby to bylo tak akorát?

ikona Jakub Vrána OpenID:

Při inicializaci se velikost tabulky nastaví na nejbližší ne-menší mocninu dvojky vzhledem k počtu prvků v poli. Když počet prvků v poli přesáhne velikost tabulky, tak se tabulka zdvojnásobí. Tabulka se nikdy nezmenšuje.

Bohdan:

Tomuto problému lze předejít tak, že se funkce vybere náhodně z nějaké 2-universální množiny (to jsou takové množiny hashovacích funkcí, že při náhodném výběru funkce z té množiny je pro každé dvě různé položky, které chceme zahashovat, pravděpodobnost kolize menší než 1/(velikost hashovací tabulky) – což zaručuje průměrné konstantní časy základních operací).

Vlastní hashovací funkce jsou potom pořád velmi rychlé a náhodný výběr funkce (v praxi většinou vygenerování dvou celých čísel) se nemusí provádět pro každé pole, stačilo by jednou pro skript nebo dokonce spuštění php.

Docela by mě zajímalo, proč to dělají takhle...

ikona Jakub Vrána OpenID:

Řekl bych, že PHP jde cestou nejmenšího odporu. Na reálných datech ke kolizím prakticky nedochází, takže nikdo neměl potřebu se tím zabývat. A nakonec může být výhodou i rychlejší průměrný případ (byť jen konstanta-krát) proti pomalejšímu nejhoršímu (přestože řádově).

kuba:

prosim vas...jak mam udelat v php text ze ktereho se vykresly tabulka??

Vložit komentář

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL:

avatar © 2005-2018 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.