Home > Backend Development > PHP Tutorial > Array implemented using hash in PHP_PHP tutorial

Array implemented using hash in PHP_PHP tutorial

WBOY
Release: 2016-07-21 15:26:07
Original
857 people have browsed it

Array is the most used one in PHP. So how is Array implemented? Within PHP, Array is implemented through a hashtable, in which the chaining method is used to solve hash conflicts. In this way, in the worst case, the complexity of finding Array elements is O(N), and in the best case it is 1.
And its calculation The method of string hash value is as follows, extract the source code for reference:

Copy the code The code is as follows:

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) { ​ ​ ​ ​ ​ ​ ​ ​ ​ //Why is this step=8 method?
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++; << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash ) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
}
switch (nKeyLength) {
case 7: hash = ((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... */ hash << 5) + hash) + *arKey++; break;
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
return hash;//return hash value
}


ps: There are still two things unclear about the following functions:
The reason for setting hash = 5381?
Is this step=8 loop method for efficiency?


http://www.bkjia.com/PHPjc/323978.html

www.bkjia.comtruehttp: //www.bkjia.com/PHPjc/323978.htmlTechArticleArray is the most used one in PHP. So how is Array implemented? In PHP, Array is implemented through a hashtable, in which the chaining method is used to solve the problem of hash conflicts. In the worst case...
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template