search
HomeBackend DevelopmentPHP TutorialVariables explored in PHP kernel (3) - hash table_PHP tutorial
Variables explored in PHP kernel (3) - hash table_PHP tutorialJul 13, 2016 am 10:11 AM
web developmentEnterprise securityinformation Technologysecurity softwaredatabasemobile developmentsystem securityWebsite securitycyber securitynetwork technologysoftware development

PHP kernel exploration variables (3) - hash table

In PHP, in addition to zval, another important data structure is the hash table. For example, our most common array is the hash table at the bottom. In addition to arrays, there are almost traces of Hash tables in thread safety (TSRM), GC, resource management, Global variables, and ini configuration management (we also mentioned last time that symbol tables are also implemented using Hash tables). So, what is special about this kind of data in PHP, and how is the structure implemented? With these questions, we begin this journey of kernel exploration.
Main content of this article:
Basic introduction to Hash table
The structure and implementation of PHP’s underlying Hash table
Zend Hash table API
1. Basic introduction and background knowledge of Hash table
1. Basic definition
Hash table, also called hash table, hash table, Hash table, the definition of hash table on Wikipedia is: "Hash table is a data that directly accesses the data stored in the memory location based on the keyword (Key value) Structure. That is, it accesses records by mapping the key value to a location in the table through the calculation of a function, which speeds up the search. This mapping function is called a hash function, and the array storing the records is called a hash table. ." Extracting the main stem of the article, we can get the following information:
(1).Hash table is a data structure.
(2). This data structure is an extension of ordinary array.
(3). This data structure makes insertion and search very efficient through the key->value mapping relationship (the array can be directly addressed and any element can be accessed in O(1) time).
We know that in general arrays, linear tables, and trees, the position of records in the structure is relatively random, that is, there is no direct and definite correspondence between records and keywords. In these structures, to find and insert keywords, a series of comparisons are often required, and the search efficiency is usually O(n) or O(lgn). The Hash table establishes the corresponding relationship between keywords and records through the Hash function, so that ordinary search and insertion operations can be completed in O(1) (average time complexity) time. This is obviously the most ideal search method. .
2. Hash function
As mentioned above, the Hash function establishes the correspondence between keywords and records, namely: Record = Hash(key). This correspondence is as follows:
Theoretically, the hash function can be any function such as Crc32, unique_id, MD5, SHA1 or user-defined function. The quality of this function is directly related to the performance of the Hash table (considering the performance of conflicts and searches). Here are several common Hash functions and corresponding implementations. Interested children can take a look. A typical string Hash algorithm is as follows:
function hash( $key ){
$result = 0;
$len = strlen($key);
for($i = 0;$i
$result += ord($key{$i}) * ((1
}
return $result;
}
3.Conflict resolution
In an ideal situation, we expect that the Hash value calculated by any keyword is unique, so that we can directly locate the record we are looking for through Hash(key). But unfortunately, there is almost no Hash function that can satisfy such characteristics (even if there is such a Hash function, it may be too complicated to be used in practice). In other words, even with a well-designed Hash function, key1 != key2 but hash(key1) = hash(key2) often occurs. This is a Hash conflict (Hash collision). There are many main methods to resolve Hash collisions (see here). As an example, we will only briefly discuss the chaining method to resolve conflicts. The basic idea of ​​this method is: when a conflict occurs in the hash table, all records with the same hash value are linked in the form of a linked list, and only the head pointer of the linked list is stored in the hash table. The underlying Hash table of PHP uses linked lists (double linked lists) to resolve hash conflicts.
The implementation of a simple Hash table is as follows:
Class HashTable{
private $buckets = null;
/* current size */
private $size = 0;
/* max hashtable size */
private $max = 2048;
private $mask = 0;
    public function __construct($size){
        $this->_init_hash($size);
    }
     
    /* hashtable init */
    private function _init_hash($size){
        if($size > $this->max){
            $size = $this->max;
        }
 
        $this->size     = $size;
        $this->mask    = $this->size - 1;
     
        // SplFixedArray is faster when the size is known
        // see http://php.net/manual/en/class.splfixedarray.php
        $this->buckets = new SplFixedArray($this->size);
    }
 
    public function hash( $key ){
        $result = 0;
        $len  = strlen($key);
  
        for($i = 0;$i
            $result += ord($key{$i}) * ((1
        }
        return $result % ($this->size);
    }
 
    /* 拉链法 */
    public function insert( $key, $val ){
        $h = $this->hash($key);
        if(!isset($this->buckets[$h])){
            $next = NULL;
        }else{
            $next = $this->bucket[$h];
        }
        $this->buckets[$h] = new Node($key, $val, $next);
    }
   
    /* 拉链法 */
    public function lookup( $key ){
        $h   = $this->hash($key);
        $cur = $this->buckets[$h];
  
        while($cur !== NULL){
            if( $cur->key == $key){
                return $cur->value;
            }
            $cur = $cur->next;
        }
        return NULL;
    }
}
 
Class Node{
    public $key;
    public $value;
    public $next = null;
  
    public function __construct($key, $value, $next = null){
        $this->key   = $key;
        $this->value = $value;
        $this->next  = $next;
    }
}
 
$hash = new HashTable(200);
$hash->insert('apple','this is apple');
$hash->insert('orange','this is orange');
$hash->insert('banana','this is banana');
echo $hash->lookup('apple');
       我们知道,在PHP中,数组支持k->v这样的关联数组,也支持普通的数组。不仅支持直接寻址(根据关键字直接定位),而且支持线性遍历(foreach等)。这都要归功于Hash table这一强大和灵活的数据结构。那么,在PHP底层,Hash table究竟是如何实现的呢?我们一步步来看。
 
二、PHP中Hash table的基本结构和实现
 
1.   基本数据结构
 
在PHP底层,与Hash table相关的结构定义、算法实现都位于Zend/zend_hash.c和Zend/zend_hash.h这两个文件中。PHP 的hash table实现包括两个重要的数据结构,一个是HashTable,另一个是bucket.前者是hash table的主体,后者则是构成链表的每个“结点”,是真正数据存储的容器。
 
(1)   HashTable的基本结构
 
定义如下(zend_hash.h):
 
typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer; /* Used for element traversal */
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;
This is a structure, with several important members:
nTableSize This member is used to indicate the size of the Hash table. When the hash table is initialized, the size of nTableSize will be set. When the hash table is expanded, the size of this value will also be adjusted accordingly. Note that this value is not the number of elements in the hash table.
nTableMask is a "mask", mainly used to quickly calculate the index of an element (nIndex = h & ht->nTableMask. In the general Hash function, the index is determined through modulo operation, but obviously, Bit operations are more efficient than modular operations), after arBuckets is initialized, this value is fixed to nTableSize – 1 by default;
nNumOfElements This member saves the number of elements saved in the hashtable. Normally, we use count($arr) in PHP scripts to be consistent with this result (see ext/standard/array.c)
nNextFreeElement This field records the next available index position. When we use $array[] = 'key' in the script, we use the index value given by nNextFreeElement (zend_hash.c):
if (flag & HASH_NEXT_INSERT) {
h = ht->nNextFreeElement;
}
pInternalPointer This is a pointer. In PHP scripts, when we use current, next, key, end and other array-related operations, we use the pInternalPointer pointer to complete it.
pListHead and pListTail The bottom layer of PHP actually maintains two important data structures. In addition to the hash table (and the doubly linked list used to resolve conflicts), there is also a doubly linked list for linear scanning of hash table elements. pListHead and pListTail point to the head and tail of this double linked list.
arBuckets This is an array of bucket * type. Each element in the array is a bucket* pointer. Elements with the same hash value are connected into a double linked list through the pNext and pLast pointers of the bucket (this double linked list is the same as the previous one). The double linked list used for linear traversal is not the same thing). Therefore, the bucket is the container that actually stores the data.
nApplyCount and bApplyProtection provide a protection mechanism, mainly used to prevent infinite recursion caused by circular references.
persistent This is a Boolean variable that will affect the way memory is allocated. This involves some knowledge of PHP memory management. We will not explain more for the time being. For details, please refer to
(2) Another data structure is Bucket
The structure is defined as:
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;
Among them:
h ,arKey,nKeyLength In PHP arrays, there are two different types of indexes, one is numeric index, which is very similar to arrays in C (such as $arr = array(1=>'cont')), The other type is string index, which uses keywords as the index of array items (such as $arr = array('index'=>'cont');). These two types of indexes use different mechanisms at the bottom of PHP To distinguish: for numeric indexes, h is used directly as the hash value. At the same time, arKey=NULL and nKeyLength=0. For string indexes, arKey saves the string key, nKeyLength saves the length of the key, and h is the character. The hash value of the string calculated by the hash function. In this way, in PHP, h, arKey, nKeyLength are actually used to uniquely determine an element in the array. This can also be seen from the definition of the zend_hash_key structure:
typedef struct _zend_hash_key {
const char *arKey;
uint nKeyLength;
ulong h;
} zend_hash_key;
The position of the array element in the hashtable is determined through h & ht->nTableMask:
/* String index */
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
/* Numeric index-append $arr[] = 'test'; this form */
if (flag & HASH_NEXT_INSERT) {
h = ht->nNextFreeElement;
}
/* Use h directly when specifying a numerical index */
nIndex = h & ht->nTableMask;
pData and pDataPtr Normally, the data in the Bucket is stored in the memory space pointed to by the pData pointer. But there are exceptions, such as saving a pointer. At this time, pDataPtr points to this pointer, and pData points to pDataPtr. This can be seen from the macro definition of INIT_DATA:
#define INIT_DATA(ht, p, pData, nDataSize);
if (nDataSize == sizeof(void*)) {                                                                                      
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
(p)->pData=&(p)->pDataPtr;
}else{                                                                                                         
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
if(!(p)->pData){
pefree_rel(p, (ht)->persistent);
return FAILURE;
                                                                            
memcpy((p)->pData,pData,nDataSize);
(p)->pDataPtr=NULL;
}
pListNext and pListLast, pNext and pLast have been introduced before, pListNext and pListLast constitute the entire double linked list for traversal. pNext and pLast are used to link Buckets with the same hash value when a hash conflict occurs. The structures of these two doubly linked lists are as shown below:
a. Double linked list when hash conflict occurs:
b. Double linked list for global use:
It should be noted that these two double linked list structures do not exist alone, but are related to each other. In related operations of HashTable, these two linked lists need to be maintained at the same time:
It can be seen that PHP's hashTable is quite complex. It is this complexity that makes PHP's array operations very flexible (arrays in PHP can be used as arrays, stacks, and queues, which can be said to be very convenient)
3. Implementation of HashTable
1. HashTable related macro definitions
In order to facilitate the operation of HashTable, PHP defines a lot of macros at the bottom level. These macros include:
(1). CONNECT_TO_BUCKET_DLLIST(element, list_head)
This macro is used to insert elements into the head of the Bucket's double-linked list. That is to say, when a conflict occurs, the newly inserted element is always located at the head of the Bucket's linked list. The definition of this macro is:
#define CONNECT_TO_BUCKET_DLLIST(element, list_head)
(element)->pNext = (list_head);
(element)->pLast = NULL;
if ((element)->pNext) {                                                                                                                                
(element)->pNext->pLast = (element);
}
(2). CONNECT_TO_GLOBAL_DLLIST(element, ht)
Different from the above, this one inserts elements to the end of the globally traversed double-linked list. This double-linked list acts like a queue, and it ensures the correct order when we traverse the array. The definition of this macro is:
1 #define CONNECT_TO_GLOBAL_DLLIST(element, ht)
2 (element)->pListLast = (ht)->pListTail;
3 (ht)->pListTail = (element);
4 (element)->pListNext = NULL;
5 if ((element)->pListLast != NULL) {                                                                        
6 (element)->pListLast->pListNext = (element);
7 }                                                                                                  
8
9 if (!(ht)->pListHead) {                                                                       
10 (ht)->pListHead = (element);
11 }                                                                                           
12
13 if ((ht)->pInternalPointer == NULL) {                                                                  
14 (ht)->pInternalPointer = (element);
15 }
(3). HASH_PROTECT_RECURSION(ht)
This macro is mainly used to prevent the HashTable from being too deep when it is recursively traversed. It is a protection mechanism
#define HASH_PROTECT_RECURSION(ht)
if ((ht)->bApplyProtection) {
if ((ht)->nApplyCount++ >= 3) {
zend_error(E_ERROR, "Nesting level too deep - recursive dependency?");
} }
}
(4).ZEND_HASH_IF_FULL_DO_RESIZE(ht)
The size of the HashTable is not fixed. When nNumOfElements > nTableSize, the HashTable will be expanded to accommodate more elements. This is achieved through this macro (actually, it is achieved by calling zend_hash_do_resize of). The macro is defined as:
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht)                                              
if ((ht)->nNumOfElements > (ht)->nTableSize) {
zend_hash_do_resize(ht);
}
(5). INIT_DATA(ht, p, pData, nDataSize)
There are actually two situations here. If the data to be saved itself is a pointer, then pDataPtr saves the pointer and points pData to the address of pDataPtr:
if (nDataSize == sizeof(void*)) {
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
(p)->pData = &(p)->pDataPtr;
}
Otherwise, if ordinary data is saved, apply for allocation of memory of nDataSize bytes, and copy the content pointed to by pData to the memory of p->pData. Here, copying is performed through memcpy, because its src and dest pointers are both void *, so almost any type of data can be copied:
else {
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
if (!(p)->pData) {
pefree_rel(p, (ht)->persistent);
return FAILURE;
}
memcpy((p)->pData, pData, nDataSize);
(p)->pDataPtr=NULL;
}
The entire macro is defined as:
#define UPDATE_DATA(ht, p, pData, nDataSize)                                                                              
if (nDataSize == sizeof(void*)) {                                                                                  
if ((p)->pData != &(p)->pDataPtr) {
pefree_rel((p)->pData, (ht)->persistent);
                                                                          
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
(p)->pData = &(p)->pDataPtr;
} else {                                                                                       
                                                                                  
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
(p)->pDataPtr=NULL;
                                                                                                 
          (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);
                                                                                                                                                                                                                                         
                                                                          
memcpy((p)->pData, pData, nDataSize);
}
(6). UPDATE_DATA(ht, p, pData, nDataSize)
Similar to INIT_DATA, the difference is that more processing needs to be done on the previous memory block (for example, the actual data saved by pData before, but the pointer saved after update, the originally applied for memory needs to be released, otherwise It will cause a memory leak. On the contrary, if the pointer data was saved before and ordinary data is saved after update, pDataPtr should be set to NULL and new memory space should be allocated for pData). The definition of this macro is:
#define UPDATE_DATA(ht, p, pData, nDataSize)                                                                              
if (nDataSize == sizeof(void*)) {                                                                                  
if ((p)->pData != &(p)->pDataPtr) {
pefree_rel((p)->pData, (ht)->persistent);
                                                                          
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
(p)->pData = &(p)->pDataPtr;
} else {                                                                                       
                                                                                  
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
(p)->pDataPtr=NULL;
                                                                                                 
(p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);
                                                                                                                                                                                                                                         
                                                                          
memcpy((p)->pData, pData, nDataSize);
}
(7). CHECK_INIT(ht)
After calling _zend_hash_init() to initialize the hash table, arBuckets does not actually allocate memory space, and the value of nTableMask is not set. CHECK_INIT will check whether arBuckets has been initialized (nTableMask==0 means not initialized). If not initialized, allocate memory space for arBuckets and set the value of nTableMask to nTableSize – 1. The macro is defined as:
#define CHECK_INIT(ht) do {                                                                                     
if (UNEXPECTED((ht)->nTableMask == 0)) {                                                                      
(ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent);
(ht)->nTableMask = (ht)->nTableSize - 1;
}                                                                                     
} while (0)
2. Hash function
When I was writing this article, I found that Brother Niao had already written an article "Hash Algorithm in PHP", which gave a more detailed answer to the hash algorithm and ideas, so I won't explain too much here. , just say one thing: unrolled. Unrolled itself means expansion. For keys with nKeyLength length, PHP’s hash algorithm will unroll in units of 8, which is in the form:
for (; nKeyLength >= 8; nKeyLength -= 8) {
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
}
Then why not just use a loop?
For example:
for(;nKeyLength > 0; nKeyLength--){
hash = ((hash
}
There is actually no problem with this, and the reason for unrolling is naturally more efficient: for the CPU, generally sequential instructions are faster than loops (the latter is represented by JMP, JNZ and other jumps in assembly instructions. and the comparison before the loop). At the same time, there will be better efficiency for string indexes below 8 bits.
By the way, the implementation source code of the hash function is posted:
/*
* 1. Inline static is to improve efficiency
* 2. Const qualifies arKey, indicating that the content of arKey should not be modified in the function
*/
static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
/* 3. Register variables, also to improve efficiency */
register ulong hash = 5381;
/* 4. variant with the hash unrolled eight times */
for (; nKeyLength >= 8; nKeyLength -= 8) {
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
hash = ((hash
}
switch (nKeyLength) {
case 7: hash = ((hash
case 6: hash = ((hash
case 5: hash = ((hash
case 4: hash = ((hash
case 3: hash = ((hash
case 2: hash = ((hash
case 1: hash = ((hash
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
/* 5. The returned hash value has not undergone modulo operation */
return hash;
}
3. Initialization, add/update, search, delete, etc. API
(1). Initialization
_zend_hash_init is used for the initialization operation of hash table (mainly including assigning initial values ​​to the data members of the hashTable structure). After calling _zend_hash_init, nTableMask defaults to 0 (later assigned to nTableSize-1 when CHECK_INIT), nTableSize is assigned to the smallest integer power of 2 greater than nSize, and the minimum nTableSize is 8, the maximum is 0x80000000, and in _ After zend_hash_init, arBuckets does not allocate memory space (it is also allocated during CHECK_INIT). nTableMask is used to quickly calculate the index corresponding to the hash value, because it has a characteristic, that is, nTableMask = 2^n – 1. After expanding into binary, all bits are 1, so the index position can be quickly obtained through nIndex = h & nTableMask. The implementation source code of this function (the specific implementation of different versions is different, the PHP version of this article is 5.4.24):
ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
/* The minimum size of hashTable is 1
uint i = 3;
SET_INCONSISTENT(HT_OK);
if (nSize >= 0x80000000) {
/* prevent overflow */
ht->nTableSize = 0x80000000;
} else {
while ((1U
i++;
}
ht->nTableSize = 1
}
ht->nTableMask = 0; /* 0 means that ht->arBuckets is uninitialized */
ht->pDestructor = pDestructor;
ht->arBuckets = (Bucket**)&uninitialized_bucket;
ht->pListHead = NULL;
ht->pListTail = NULL;
ht->nNumOfElements = 0;
ht->nNextFreeElement = 0;
ht->pInternalPointer = NULL;
ht->persistent = persistent;
ht->nApplyCount = 0;
ht->bApplyProtection = 1;
return SUCCESS;
}
(2). Find elements.
For string index and numeric index, two search methods, zend_hash_find and zend_hash_index_find, are provided respectively. There is no essential difference between these two methods. They both find the position of the element in the corresponding Bucket after calculating the hash value. For string indexes, the condition to determine the same is: p->arKey == arKey ||((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p-> ;arKey, arKey, nKeyLength)), that is, either arKey and p->arKey point to the same memory, or the contents pointed to by h, nKeyLength and arKey are exactly the same, so that they can be determined to be the same. For numeric indexes, only (p->h == h) && (p->nKeyLength == 0) is required. The implementation of these two searches is as follows:
/* Search for numeric index */
ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
{
uint nIndex;
Bucket *p;
IS_CONSISTENT(ht);
/* Calculate index */
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
/* Traverse the double linked list and return immediately once found */
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == 0)) {
*pData = p->pData;
return SUCCESS;
}
p = p->pNext;
}
/* If nothing is found after traversing the double linked list, the search fails */
return FAILURE;
}

/* Search for string index */
ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
{
ulong h;
uint nIndex;
Bucket *p;
IS_CONSISTENT(ht);
/* String index needs to calculate the hash value of the string first */
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
/* Search in the Bucket double-linked list. Once found, return immediately. Pay attention to the conditions for successful search */
while (p != NULL) {
if (p->arKey == arKey ||
         ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
*pData = p->pData;
return SUCCESS;
}
p = p->pNext;
}
/* Search failed */
return FAILURE;
}
(3).Insert element
In PHP script, there are three ways to insert elements into the current array, such as:
$arr = array();
$arr['index'] = 'cont';
$arr[2] = 'test';
$arr[] = 10;
The three insertion methods are: "String index insertion", "Number index insertion", "Next available position insertion". In the implementation, "String index insertion" corresponds to _zend_hash_add_or_update, and the latter two correspond to _zend_hash_index_update_or_next_insert. Taking the operation $arr['index'] = 'cont' as an example, PHP will try to update the corresponding data first. If the corresponding Bucket is not found, it means that this is a new element, so insert will be executed. Operation, this is implemented in _zend_hash_add_or_update as follows (non-critical steps omitted):
ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pD est, int flag ZEND_FILE_LINE_DC)
{
/* Since it is a string index, the index key cannot be empty, nKeyLength must be >0 */
if (nKeyLength
return FAILURE;
}
/* Whether ht is initialized, if not, allocate the memory space of arBuckets and set nTableMask */
CHECK_INIT(ht);
/* Calculate the index in the hash table */
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
/* Scan the Bucket list to see if the element exists. If it exists, update it and return */
p = ht->arBuckets[nIndex];
while (p != NULL) {
 if (p->arKey == arKey ||
((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
/* Conflict, cannot be added */
       if (flag & HASH_ADD) {
return FAILURE;
      }
HANDLE_BLOCK_INTERRUPTIONS();
if (ht->pDestructor) {
ht->pDestructor(p->pData);
      }
          /* Perform update operations */
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p->pData;
      }
HANDLE_UNBLOCK_INTERRUPTIONS();
return SUCCESS;
}
p = p->pNext;
}
/* If the element does not exist, insert */
if (IS_INTERNED(arKey)) {
p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
if (!p) {
return FAILURE;
}
p->arKey = arKey;
} else {
p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
if (!p) {
return FAILURE;
}
p->arKey = (const char*)(p + 1);
memcpy((char*)p->arKey, arKey, nKeyLength);
}
p->nKeyLength = nKeyLength;
INIT_DATA(ht, p, pData, nDataSize);
p->h = h;
 /* Insert into the head of the Buckets list */
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
/* Insert into the global double-linked list for traversal, which is a logical queue */
CONNECT_TO_GLOBAL_DLLIST(p, ht);
ht->arBuckets[nIndex] = p;
/* Increase the number of elements */
ht->nNumOfElements++;
 /* If nNumOfElements > nTableSize, you need to expand the HashTable */
ZEND_HASH_IF_FULL_DO_RESIZE(ht);
}
More operations of HashTable such as zend_hash_do_resize (expansion), zend_hash_rehash (the elements of the original hashTable need to be re-hashed after expansion), zend_hash_del_key_or_index (delete elements in HashTable), zend_hash_destroy (destroy the Hash table), zend_hash_copy (hash table copy), I won’t list them one by one here. Interested students can check the source code.
Previous articlehttp://www.Bkjia.com/kf/201411/356800.html

www.bkjia.comtruehttp: //www.bkjia.com/PHPjc/929773.htmlTechArticlePHP kernel exploration variables (3) - hash table In PHP, in addition to zval, another important data The structure is none other than hash table. For example, our most common array is hash t at the bottom...
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
如何在 Windows 11 上创建移动热点如何在 Windows 11 上创建移动热点Apr 17, 2023 pm 06:22 PM

当然,在Android智能手机和Windows11PC之间共享移动互联网可能很有用,尤其是在Wi-Fi不可用时。因此,当其他选项刚刚出现时,知道如何与Windows设备共享移动互联网会非常方便。就像没有Wi-Fi时iPhone可以连接到Mac一样,Android设备也允许用户通过USB和蓝牙将智能手机的互联网连接与任何Windows笔记本电脑连接。对于我们许多人来说,通过电缆连接手机和PC不是一种选择,而通过蓝牙连接互联网可能会很慢。因此,使用智能手机创建W

实用Word技巧分享:2招轻松解决多图片排版!实用Word技巧分享:2招轻松解决多图片排版!Apr 01, 2023 am 10:57 AM

多图片排版,是Word编辑文档时常见场景之一,几乎每个人都会碰到,对很多人来说仍然是一大难题。当图片数量一多,很多人都不知道图片该怎么摆放,如何快速高效地搞定一组图片? 因为没有掌握系统的套路技巧,每次制作都花费大量时间,做不出满意的效果。今天我就教大家2 招,轻松解决多图片排版!

如何在网络安全中使用AI如何在网络安全中使用AIApr 14, 2023 pm 02:10 PM

Cybersecurity Ventures的报告显示,2021年全球网络犯罪带来的损失为6万亿美元,并预计打击网络犯罪的全球支出在2025年将增至10.5万亿美元,是2015年的三倍之多(3万亿美元)。人工智能,几乎是唯一应对方案。另一家研究机构Statista认为,2020年网络安全领域的人工智能价值已超过100亿美元,并预计到2027年将达到450亿美元。IBM则认为,缺乏人工智能安全的企业,在抵御网络攻击方面的成本是部署了AI自动化防御系统的企业的三倍。来自Meticulous的研究数据

Microsoft Edge 102.0.1245.41 带来安全修复和 PDF 打印错误解决方案Microsoft Edge 102.0.1245.41 带来安全修复和 PDF 打印错误解决方案May 06, 2023 pm 07:37 PM

微软在周末为其Edge浏览器发布了两个小更新。该公司在周五和今天发布了另一个安全更新。虽然周五的更新修复了影响Edge浏览器的安全问题,但今天的更新解决了影响所有基于Chromium的网络浏览器的安全问题。此外,该更新似乎解决了通过Edge浏览器访问PDF文件时无法打印的问题。稳定版本通道的Edge102.0.1245.41被标记为修复了多个漏洞的维护更新。Microsoft尚未更新发行说明。不过,该公司此前已告知Chromium和Edge浏览器存在以下漏洞:

从“微软安全的下一步”数字活动中可以期待什么从“微软安全的下一步”数字活动中可以期待什么Apr 19, 2023 am 10:46 AM

Microsoft数字活动的下一步安全计划将于太平洋时间(UTC-8)时间2月24日上午9:00至上午10:30举行。随着无处不在的威胁不断增长,为他们的公司寻找有效安全解决方案的各种组织希望在这次活动中找到一些有价值的技巧和知识。Microsoft的安全下一步计划将强调全面的安全方法对业务增长的重要性。它将欢迎不同的安全专家讨论最新的创新和技术,以减少最新的威胁风险。一些演讲者包括VasuJakkal(微软公司安全、合规和身份副总裁)和JeffPollard(F

人工智能聊天机器人在网络安全领域的发展趋势如何?人工智能聊天机器人在网络安全领域的发展趋势如何?Apr 22, 2023 pm 11:13 PM

OpenAI公司推出的聊天机器人ChatGPT有很多很好的用途,但就像任何新技术一样,有些人会利用ChatGPT用于罪恶的目的。从编写电子邮件等相对简单的任务,到撰写论文或编译代码等更复杂的工作,OpenAI公司的人工智能驱动的自然语言处理工具ChatGPT自从推出以来就引起了人们的极大兴趣。当然,ChatGPT并不完美——众所周知,当它误解了从中学习的信息时就会犯错,但许多人将它和其他人工智能工具视为互联网的未来。OpenAI公司在ChatGPT的服务条款中加入了禁止生成恶意软件的条目,其中包

Zerodium 宣布为 Microsoft Outlook 零点击 RCE 安全漏洞支付 400,000 美元Zerodium 宣布为 Microsoft Outlook 零点击 RCE 安全漏洞支付 400,000 美元Apr 29, 2023 pm 09:28 PM

<ul><li><strong>点击进入:</strong>ChatGPT工具插件导航大全</li></ul><figureclass="imageimage--expandable"><imgsrc="/uploads/2023041

微软在 Windows 10 和 11 上的 Windows Defender 中引入了易受攻击的驱动程序阻止列表微软在 Windows 10 和 11 上的 Windows Defender 中引入了易受攻击的驱动程序阻止列表Apr 17, 2023 am 11:52 AM

MicrosoftWindowsDefender收到的升级将使Windows10、Windows11和WindowsServer2016或更高版本受益。引入到Defender的Microsoft易受攻击的驱动程序阻止列表功能将允许阻止具有安全漏洞的驱动程序在设备上运行。微软操作系统安全和企业副总裁大卫韦斯顿于3月27日发布了更新公告。Defender的Microsoft易受攻击的驱动程序阻止列表功能对于用户来说是可选的,因为它可以打开和关闭,并且它对于每个人来说都是

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)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)