配列はどう実装されているのか？
翻訳その1．
元ネタ：http://stackoverflow.com/questions/247467/how-are-associative-arrays-implemented-in-php （その魚拓）
質問
Can someone explain how PHP implements associative arrays? What underlying data structure does PHP use? Does PHP hash the key and store it in some kind of hash map? I am curious because I was wondering what the performance of associative arrays where when inserting and searching for keys.
asked Oct 29 '08 at 16:26
Y Pgjn
PHPの連想配列がどう実装されているのか、誰か説明してくれないかい？下層のレイヤでは、PHPはどんなデータ構造をつかっているんだろう？キーのハッシュ値を計算して、ハッシュ表に格納しているのかな？連想配列でのキーの挿入や検索の際にどんな事やってんのかずっと考えてて、興味があるんだ。
回答1
Well, for what it is worth, all PHP arrays are Associative arrays.
answered Oct 29 '08 at 16:28
EBGreen
回答2
I'll leave this link for someone else to grind through, but you can view the actual C source for PHP at
http://cvs.php.net/viewvc.cgi/php-src/
answered Oct 29 '08 at 16:48
kthejoker
回答3
It's all hash tables, according to sources in various web forums: http://www.usenet-forums.com/php-language/15348-zend-engine-array-implementation.html
If you want to be sure, read the source, then compile it, but make sure you can trust your compiler (Warning: PDF, and unrelated, but very cool).
answered Oct 29 '08 at 16:52
jakber
いくつかのフォーラム（http://www.usenet-forums.com/php-language/15348-zend-engine-array-implementation.html とか）によれば、（内部実装は）ハッシュ表だよ。
確かめたいなら、ソース読んでビルドせんとな。*1
回答4
@EBGreen is correct.
Which gives you some interesting performance problems, especially when treating an array as a list and using the [] (array add) operator. PHP doesn't seem to cache the largest numeric key and add one to it, instead it seems to traverse all of the keys to find what the next numeric key should be. I've rewritten scripts in python because of PHP's dismal array-as-a-list performance.
Associative arrays have the standard dict/hash performance overhead.
answered Oct 29 '08 at 17:14
jcoby
EBBreen氏は正解。
配列をリスト*2として扱い、[]演算子（配列に要素を追加する演算子）を使う時、興味深い性能面での問題があるんだ。PHPは連想配列に要素を追加するとき、インデックスの最大値を覚えておかないみたいなんだ。そのかわり、次のインデックスを決めるためにキーの集合を走査しているみたいなんだ。配列をリストとして使う場合のこの挙動があまりにひどいから、僕はpythonで書き直したよ。
連想配列の場合は、標準的な辞書／ハッシュ表のコストがかかるよ。
返信
Are you sure about this? I've just ran benchmarks on a test array of 1000 entries (copying to a new array, one by one), and if you don't specify the key for the new array, it's consistently 7% faster (on PHP 5.2.6)
Oct 29 '08 at 21:08
JamShady
それは確かかい？1000個の要素（1個ずつコピーして追加）を持つ配列でベンチマーク走らせてみたけど、キーを指定しなかったら、一貫して7%速かったよ（PHP 5.2.6上で）。
回答5
It's a hash table. The type declaration and hashing function are here: http://cvs.php.net/viewvc.cgi/ZendEngine2/zend_hash.h?view=markup
There is a light weight array and a linked list within the spl (standard php lib)
answered Apr 22 '10 at 18:54
chuck
（実装に使われてるのは）ハッシュ表だよ。型の宣言、ハッシュ関数は http://cvs.php.net/viewvc.cgi/ZendEngine2/zend_hash.h?view=markup にあるよ。
SPLには軽量の配列と連結リストがあるよ。
