O PHP lida com arrays de uma forma diferentes de outras linguagens, aparentemente existe conceitos de hashtable para associar os valores. Como funciona internamente no core da linguagem os arrays?
1 Resposta
O PHP tem algo chamado array associativo e internamente é alguma forma de hashtable mesmo, portanto ele consegue ter chaves esparsas, de tipos diferentes de dados e possui complexidade O(1) para quase todas operações básicas, assim como o array normal. Na verdade essa complexidade é tipicamente O(1), ela pode ser até O(n), mas na prática nem chega perto de acontecer. Obviamente que a chave do índice é calculada por uma função hash padrão da linguagem ou especializada nos tipos primitivos dela.
Na verdade quase tudo na estrutura de dados geral e organização da memória é controla por tabelas de espalhamento (hashtable), de forma análoga com JavaScript, mas isso não é tão visível e tão linear quanto em JS que tudo é um objeto criado em cima de uma hashtable.
Há uma otimização para obter a ordem já que um objeto hashtable puro não pode mostrar dados em uma ordem específica, então há um custo extra de armazenamento para a varredura em ordem funcionar. Veja como é a estrutura atual (se já não mudou), ela tem ponteiros para conseguir manter a ordem de entrada através de uma lista ligada dos buckets:
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_DEBUG
int inconsistent;
#endif
} HashTable;
E o bucket
que mostra como é ineficiente (é quase inacreditável o tamanho do desperdício, em arquitetura 64 bits cada entrada ocupa 72 bytes só na tabela, ainda tem custo adicional em cada elemento que é próximo disso):
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;
De forma geral os valores são alocados bem ineficientemente em PHP, os arrays não poderiam ser diferentes, embora tenha tido um esforço de otimização recentemente.
Por exemplo, descobri que todo valor é armazenado assim:
typedef union _zvalue_value {
long lval; /* long value */
double dval; /* double value */
struct {
char *val;
int len;
} str;
HashTable *ht; /* hash table value */
zend_object_value obj;
} zvalue_value;
Coloquei no GitHub para referência futura.
Em 64 bits esta estrutura terá 16 bytes porque o len
está aí e não junto da string em si, então qualquer valor que não seja string desperdiçará 8 bytes por causa do alinhamento. Claramente a estrutura foi pensada para 32 bits que desperdiça nada. Então rodar PHP em 64 bits pode ter quase o dobro do consumo de memória que em 32 bits, pra zero ganho. Quem sabe um dia resolvam isso, eles demonstram vontade.
Nem dá para dar tantos detalhes justamente porque o funcionamento interno é detalhe de implementação, e nada impede de passar funcionar de forma bem diferente.
E se tudo isso é estranho para você, sugiro começar estudar um pouco mais de ciência da computação, em especial estrutura de dados. Um pouco de C ajuda entender esses códigos dos internals do PHP.