search
HomeBackend DevelopmentPHP TutorialHash algorithm in PHP_PHP tutorial

Hash algorithm in PHP_PHP tutorial

Jul 13, 2016 pm 05:47 PM
hashphptableassociationobjectAttributesarrayyescoreofalgorithm

Hash Table is the core of PHP, this is not an exaggeration at all.
PHP's arrays, associative arrays, object properties, function tables, symbol tables, etc. all use HashTable as a container.
PHP's HashTable uses the zipper method to resolve conflicts. Needless to say, my main focus today is PHP's Hash algorithm and some of the ideas revealed by the algorithm itself.
PHP's Hash uses the most common DJBX33A (Daniel J. Bernstein, Times 33 with Addition). This algorithm is widely used in multiple software projects, such as Apache, Perl and Berkeley DB. For strings, this is currently The best hashing algorithm known, because it is very fast and classifies very well (little collisions, even distribution).
The core idea of ​​the algorithm is:
1. hash(i) = hash(i-1) * 33 + str[i]
In zend_hash.h, we can find this algorithm in PHP:
1. static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
2. {
3. Register ulong hash = 5381;
4. 
5. /* variant with the hash unrolled eight times */
6. for (; nKeyLength >= 8; nKeyLength -= {
7.           hash = ((hash 8.           hash = ((hash 9.          hash = ((hash 10.          hash = ((hash 11.          hash = ((hash 12.          hash = ((hash 13.          hash = ((hash 14.          hash = ((hash 15. }
16. switch (nKeyLength) {
17. case 7: hash = ((hash 18. case 6: hash = ((hash 19. case 5: hash = ((hash 20.           case 4: hash = ((hash 21.           case 3: hash = ((hash 22.           case 2: hash = ((hash 23.    case 1: hash = ((hash 24. case 0: break;
25. EMPTY_SWITCH_DEFAULT_CASE()
26. }
27. Return hash;
28. }
Compared to the classic Times 33 algorithm adopted directly in Apache and Perl:
1. hashing function used in Perl 5.005:
2. # Return the hashed value of a string: $hash = perlhash("key")
3.      # (Defined by the PERL_HASH macro in hv.h)
4. sub perlhash
5. {
6.           $hash = 0;
7. foreach (split //, shift) {
8.                $hash = $hash*33 + ord($_);
9.        }
10.         return $hash;
11. }
In PHP’s hash algorithm, we can see very subtle differences.
First of all, the most different thing is that PHP does not use direct multiplication by 33, but uses:
1. hash This will of course be faster than taking a ride.
Then, the most important thing to consider is the use of unrolled. I read an article a few days ago about Discuz’s caching mechanism. One of them said that Discuz will adopt different caching strategies according to the popularity of the post. According to user habits, only Cache the first page of the post (because few people will read the post).
Similar to this idea, PHP encourages character indexes of less than 8 digits. It uses unrolled in units of 8 to improve efficiency. It must be said that this is also a very detailed and meticulous place.
In addition, there are inline and register variables... It can be seen that PHP developers have also taken great pains to optimize hash
Finally, the initial value of hash is set to 5381. Compared with the times algorithm in Apache and the Hash algorithm in Perl (both use an initial hash of 0), why choose 5381? I don’t know the specific reason, but I Discovered some features of 5381:
1. Magic Constant 5381:
2. 1. odd number
3. 2. prime number
4. 3. deficient number
5. 4. 001/010/100/000/101
After reading this, I have reason to believe that the selection of this initial value can provide better classification.
As for why Times 33 is Times 33 instead of Times other numbers, there are some explanations in the comments of the PHP Hash algorithm. I hope it will be useful to interested students:
1. DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
2. 
3. This is Daniel J. Bernstein's popular `times 33' hash function as
4. Posted by him years ago on comp.lang.c. It basically uses a function
5. Like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
6. Known hash functions for strings. Because it is both computed very
7. fast and distributes very well.
8. 
9. The magic of number 33, i.e. why it works better than many other
10. constants, prime or not, has never been adequately explained by
11. anyone. So I try an explanation: if one experimentally tests all
12. multipliers between 1 and 256 (as RSE did now) one detects that even
13. Numbers are not useable at all. The remaining 128 odd numbers
14. (except for the number 1) work more or less all equally well. They
15. all distribute in an acceptable way and this way fill a hash table
16. with an average percent of approx. 86%.
17.
18. If one compares the Chi^2 values ​​of the variants, the number 33 not
19. even has the best value. But the number 33 and a few other equally
20. Good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
21. Advantage to the remaining numbers in the large set of possible
22. Multipliers: their multiply operation can be replaced by a faster
23. Operation based on just one shift plus either a single addition
24. or subtraction operation. And because a hash function has to both
25. distribute well _and_ has to be very fast to compute, those few
26. Numbers should be preferred and seems to be the reason why Daniel J.
27. Bernstein also preferred it.
28.
29. www.2cto.com -- Ralf S. Engelschall

• Author: Laruence
• This article’s address: http://www.laruence.com/2009/07/23/994.html

www.bkjia.comtruehttp: //www.bkjia.com/PHPjc/478471.htmlTechArticleHash Table is the core of PHP. This is not an exaggeration at all. PHP arrays, associative arrays, object properties, Function tables, symbol tables, etc. all use HashTable as a container. PHP's HashTable uses zippers...
Statement
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
How does PHP type hinting work, including scalar types, return types, union types, and nullable types?How does PHP type hinting work, including scalar types, return types, union types, and nullable types?Apr 17, 2025 am 12:25 AM

PHP type prompts to improve code quality and readability. 1) Scalar type tips: Since PHP7.0, basic data types are allowed to be specified in function parameters, such as int, float, etc. 2) Return type prompt: Ensure the consistency of the function return value type. 3) Union type prompt: Since PHP8.0, multiple types are allowed to be specified in function parameters or return values. 4) Nullable type prompt: Allows to include null values ​​and handle functions that may return null values.

How does PHP handle object cloning (clone keyword) and the __clone magic method?How does PHP handle object cloning (clone keyword) and the __clone magic method?Apr 17, 2025 am 12:24 AM

In PHP, use the clone keyword to create a copy of the object and customize the cloning behavior through the \_\_clone magic method. 1. Use the clone keyword to make a shallow copy, cloning the object's properties but not the object's properties. 2. The \_\_clone method can deeply copy nested objects to avoid shallow copying problems. 3. Pay attention to avoid circular references and performance problems in cloning, and optimize cloning operations to improve efficiency.

PHP vs. Python: Use Cases and ApplicationsPHP vs. Python: Use Cases and ApplicationsApr 17, 2025 am 12:23 AM

PHP is suitable for web development and content management systems, and Python is suitable for data science, machine learning and automation scripts. 1.PHP performs well in building fast and scalable websites and applications and is commonly used in CMS such as WordPress. 2. Python has performed outstandingly in the fields of data science and machine learning, with rich libraries such as NumPy and TensorFlow.

Describe different HTTP caching headers (e.g., Cache-Control, ETag, Last-Modified).Describe different HTTP caching headers (e.g., Cache-Control, ETag, Last-Modified).Apr 17, 2025 am 12:22 AM

Key players in HTTP cache headers include Cache-Control, ETag, and Last-Modified. 1.Cache-Control is used to control caching policies. Example: Cache-Control:max-age=3600,public. 2. ETag verifies resource changes through unique identifiers, example: ETag: "686897696a7c876b7e". 3.Last-Modified indicates the resource's last modification time, example: Last-Modified:Wed,21Oct201507:28:00GMT.

Explain secure password hashing in PHP (e.g., password_hash, password_verify). Why not use MD5 or SHA1?Explain secure password hashing in PHP (e.g., password_hash, password_verify). Why not use MD5 or SHA1?Apr 17, 2025 am 12:06 AM

In PHP, password_hash and password_verify functions should be used to implement secure password hashing, and MD5 or SHA1 should not be used. 1) password_hash generates a hash containing salt values ​​to enhance security. 2) Password_verify verify password and ensure security by comparing hash values. 3) MD5 and SHA1 are vulnerable and lack salt values, and are not suitable for modern password security.

PHP: An Introduction to the Server-Side Scripting LanguagePHP: An Introduction to the Server-Side Scripting LanguageApr 16, 2025 am 12:18 AM

PHP is a server-side scripting language used for dynamic web development and server-side applications. 1.PHP is an interpreted language that does not require compilation and is suitable for rapid development. 2. PHP code is embedded in HTML, making it easy to develop web pages. 3. PHP processes server-side logic, generates HTML output, and supports user interaction and data processing. 4. PHP can interact with the database, process form submission, and execute server-side tasks.

PHP and the Web: Exploring its Long-Term ImpactPHP and the Web: Exploring its Long-Term ImpactApr 16, 2025 am 12:17 AM

PHP has shaped the network over the past few decades and will continue to play an important role in web development. 1) PHP originated in 1994 and has become the first choice for developers due to its ease of use and seamless integration with MySQL. 2) Its core functions include generating dynamic content and integrating with the database, allowing the website to be updated in real time and displayed in personalized manner. 3) The wide application and ecosystem of PHP have driven its long-term impact, but it also faces version updates and security challenges. 4) Performance improvements in recent years, such as the release of PHP7, enable it to compete with modern languages. 5) In the future, PHP needs to deal with new challenges such as containerization and microservices, but its flexibility and active community make it adaptable.

Why Use PHP? Advantages and Benefits ExplainedWhy Use PHP? Advantages and Benefits ExplainedApr 16, 2025 am 12:16 AM

The core benefits of PHP include ease of learning, strong web development support, rich libraries and frameworks, high performance and scalability, cross-platform compatibility, and cost-effectiveness. 1) Easy to learn and use, suitable for beginners; 2) Good integration with web servers and supports multiple databases; 3) Have powerful frameworks such as Laravel; 4) High performance can be achieved through optimization; 5) Support multiple operating systems; 6) Open source to reduce development costs.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Chat Commands and How to Use Them
1 months agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools