ホームページ >バックエンド開発 >PHPチュートリアル >PHP カーネルで調べる変数 (3) - ハッシュ テーブル_PHP チュートリアル
PHP カーネルで調べる変数 (3) - ハッシュ テーブル_PHP チュートリアル
- WBOYオリジナル
- 2016-07-13 10:11:20867ブラウズ
PHP カーネル探索変数 (3) - ハッシュ テーブル
PHP では、zval に加えて、もう 1 つの重要なデータ構造がハッシュ テーブルです。たとえば、最も一般的な配列は下部のハッシュ テーブルです。配列に加えて、スレッド セーフ (TSRM)、GC、リソース管理、グローバル変数、および ini 構成管理にもハッシュ テーブルの痕跡がほとんどあります (シンボル テーブルもハッシュ テーブルを使用して実装されていることも前回触れました)。では、PHP におけるこの種のデータの何が特別で、その構造はどのように実装されているのでしょうか? これらの質問をもとに、カーネル探索の旅を始めます。この記事の主な内容:
ハッシュテーブルの基本入門
PHPの基礎となるハッシュテーブルの構造と実装
Zend ハッシュ テーブル API
1. ハッシュテーブルの基本的な概要と予備知識
1. 基本的な定義
ハッシュ テーブル、ハッシュ テーブル、ハッシュ テーブル、ハッシュ テーブルとも呼ばれます。Wikipedia でのハッシュ テーブルの定義は次のとおりです。「ハッシュ テーブルは、キーワード (キー値) に基づいてメモリの格納場所に直接アクセスするデータ構造です。つまり、たとえば、関数の計算によってキー値をテーブル内の位置にマッピングすることでレコードにアクセスします。このマッピング関数は検索を高速化します。このマッピング関数はハッシュ関数と呼ばれ、レコードを格納する配列はハッシュ テーブルと呼ばれます。 。記事の主幹を抽出すると、次の情報が得られます:
(1).ハッシュテーブルはデータ構造です。
(2)。このデータ構造は通常の配列の拡張です。
(3). このデータ構造により、キーと値のマッピング関係により、挿入と検索が非常に効率的になります (配列は直接アドレス指定でき、どの要素にも O(1) 時間でアクセスできます)。
一般的な配列、線形テーブル、およびツリーでは、構造内のレコードの位置が比較的ランダムである、つまり、レコードとキーワードの間に直接的かつ明確な対応関係がないことがわかっています。これらの構造では、キーワードを検索して挿入するために一連の比較が必要になることが多く、検索効率は通常 O(n) または O(lgn) です。ハッシュ テーブルは、ハッシュ関数によってキーワードとレコードの対応関係を確立するため、通常の検索と挿入操作を O(1) (平均時間計算量) の時間で完了できます。これは明らかに最も理想的な検索方法です。
2.ハッシュ関数
前述したように、ハッシュ関数はキーワードとレコード間の対応関係を確立します。つまり、レコード = ハッシュ(キー) この対応関係は次のとおりです。
/* ハッシュテーブルの最大サイズ */
プライベート $max = 2048;
プライベート $マスク = 0;
パブリック関数 __construct($size){
$this->_init_hash($size);
}
/* ハッシュテーブルの初期化 */
プライベート関数 _init_hash($size){
if($size > $this->max){
$size = $this->max;
}
$this->size = $size;
$this->マスク = $this->サイズ - 1;
// サイズがわかっている場合、SplFixedArray は高速になります
// http://php.net/manual/en/class.splfixedarray.php を参照してください
$this->buckets = new SplFixedArray($this->size);
}
パブリック関数ハッシュ( $key ){
$result = 0;
$len = strlen($key);
for($i = 0;$i
ハッシュ = ((ハッシュ
ハッシュ = ((ハッシュ
} $result += ord($key{$i}) * ((1
二、PHP中のハッシュテーブルの基本構造と实现
1. 基本データベース结构
（1） HashTableの基本構造
定义如下（zend_hash.h）：
typedef struct _hashtable {
nNextFreeElement このフィールドは、スクリプトで $array[] = 'key' を使用する場合、nNextFreeElement (zend_hash.c) で指定されたインデックス値を使用します。
typedef struct _zend_hash_key {
const char *arKey;
uint nKeyLength;
うろんh;
} zend_hash_key;
ハッシュテーブル内の配列要素の位置は、h&ht->nTableMask によって決定されます:
memcpy((p)->pData,pData,nDataSize);
pListNext と pListLast、pNext と pLast は以前に導入されました。pListNext と pListLast は、トラバーサル用の二重リンク リスト全体を構成します。 pNext と pLast は、ハッシュの競合が発生した場合に、同じハッシュ値を持つバケットをリンクするために使用されます。これら 2 つの二重リンクリストの構造は以下に示すとおりです:
a. ハッシュ競合が発生した場合の二重リンクリスト:
b. グローバルで使用するための二重リンクリスト:
これら 2 つの二重リンクリスト構造は単独で存在するのではなく、相互に関連していることに注意してください。 HashTable の関連操作では、次の 2 つのリンクされたリストを同時に維持する必要があります:
PHP の hashTable は非常に複雑であることがわかります。この複雑さが PHP の配列操作を非常に柔軟にしています (PHP の配列は配列、スタック、キューとして使用でき、非常に便利です)。
(2).CONNECT_TO_GLOBAL_DLLIST(要素、ht)
上記とは異なり、これはグローバルに走査される二重リンクリストの末尾に要素を挿入します。この二重リンクリストはキューのように機能し、配列を走査するときに正しい順序を保証します。このマクロの定義は次のとおりです:
1 #define CONNECT_TO_GLOBAL_DLLIST(element, ht)
2 (要素)->pListLast = (ht)->pListTail;
9 if (!(ht)->pListHead) {
(3).HASH_PROTECT_RECURSION(ht)
このマクロは主に、ハッシュテーブルが再帰的に走査されるときに深すぎるのを防ぐために使用されます
#define HASH_PROTECT_RECURSION(ht)
if ((ht)->bApplyProtection) {
if ((ht)->nApplyCount++ >= 3) {
zend_error(E_ERROR, "ネストレベルが深すぎます - 再帰的な依存関係?");
}
}
(4).ZEND_HASH_IF_FULL_DO_RESIZE(ht)
HashTable のサイズは固定されていません。nNumOfElements > nTableSize の場合、より多くの要素を収容できるように HashTable が拡張されます (実際には、zend_hash_do_resize を呼び出すことで実現されます)。マクロは次のように定義されます:
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht)
if ((ht)->nNumOfElements > (ht)->nTableSize) {
zend_hash_do_resize(ht);
if (nDataSize == sizeof(void*)) {
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
(p)->pData = &(p)->pDataPtr;
}
pefree_rel((p)->pData, (ht)->persistent);
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
(6).UPDATE_DATA(ht, p, pData, nDataSize)
#define UPDATE_DATA(ht, p, pData, nDataSize)
(p)->pData = (void *) perrealloc_rel((p)->pData, nDataSize, (ht)->persistent);
(7).CHECK_INIT(ht)
_zend_hash_init() を呼び出してハッシュ テーブルを初期化した後、arBuckets は実際にはメモリ領域を割り当てず、nTableMask の値は設定されません。 CHECK_INIT は、arBuckets が初期化されているかどうかを確認します (nTableMask==0 は初期化されていないことを意味します)。初期化されていない場合は、arBuckets にメモリ領域を割り当て、nTableMask の値を nTableSize - 1 に設定します。マクロは次のように定義されます。
(ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent
for (; nKeyLength >= 8; nKeyLength -= 8) {
ハッシュ = ((ハッシュ
ハッシュ = ((ハッシュ
ハッシュ = ((ハッシュ
ハッシュ = ((ハッシュ
ハッシュ = ((ハッシュ
ハッシュ = ((ハッシュ
}
$result % ($this->size);
}
/* 拉链法 */
public function insert( $key, $val ){
$h = $this->hash($key);
if(!isset($this->buckets[$h])){
$next = NULL;
}その他{
$next = $this->bucket[$h];
}
$this->buckets[$h] = new Node($key, $val, $next);
}
/* 拉链法 */
パブリック関数 lookup( $key ){
$h = $this->hash($key);
$cur = $this->buckets[$h];
while($cur !== NULL){
if( $cur->key == $key){
$cur->value;
}
$cur = $cur->next;
}
NULL を返す;
}
}
クラスノード{
public $key;
public $value;
public $next = null;
public function __construct($key, $value, $next = null){
$this->key = $key;
$this->value = $value;
$this->next = $next;
}
}
$hash = 新しいハッシュテーブル(200);
$hash->insert('リンゴ','これはリンゴです');
$hash->insert('オレンジ','これはオレンジです');
$hash->insert('バナナ','これはバナナです');
echo $hash->lookup('apple');
私が知っていることですが、PHP では、数値集合は k->v のような関連数値集合をサポートしており、通常の数値集合もサポートしています。ハッシュ テーブルは、この強力なダイナミックなデータ構造として機能します。
PHP の最下層では、ハッシュ テーブルに関連する構造と計算法の実装が、Zend/zend_hash.c と Zend/zend_hash.h の両方のファイル内にあります。 、もう 1 つはバケットです。前者はハッシュ テーブルの本体、後者はテーブルを構成する各「ポイント」、つまり真のデータが格納されるコンテナです。
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer; /* 要素の走査に使用されます */
バケット *pListHead;
バケット *pListTail;
バケット **arBuckets;
dtor_func_t pDestructor;
zend_bool 永続的;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
一貫性がありません;
#endif
}ハッシュテーブル;
これは、いくつかの重要なメンバーを含む構造です:
nTableSize このメンバーは、ハッシュ テーブルの初期化操作中に、nTableSize のサイズが設定され、それに応じてこの値のサイズも調整されます。この値はハッシュ テーブル内の要素の数ではないことに注意してください。
nTableMask は「マスク」で、主に要素のインデックス (nIndex = h & ht->nTableMask) を迅速に計算するために使用されます。一般的なハッシュ関数では、インデックスはモジュロ演算を通じて決定されますが、明らかにビット演算の方が効率的です。モジュラー操作より)、arBuckets が初期化された後、この値はデフォルトで nTableSize – 1 に固定されます。
nNumOfElements このメンバーは、ハッシュテーブルに保存される要素の数を保存します。通常、この結果と一致するように PHP スクリプトで count($arr) を使用します (ext/standard/array.c を参照)。
if (フラグ & HASH_NEXT_INSERT) {
h = ht->nNextFreeElement;
}
pInternalPointer これはポインタです。 PHP スクリプトでは、current、next、key、end、およびその他の配列関連の操作を使用する場合、pInternalPointer ポインターを使用して操作を完了します。
pListHead と pListTail PHP の最下層は、実際には 2 つの重要なデータ構造を維持しています。ハッシュ テーブル (および競合を解決するために使用される二重リンク リスト) に加えて、ハッシュ テーブル要素の線形スキャンに使用される二重リンク リストもあります。 pListHead と pListTail は、この二重リンク リストの先頭と末尾を指します。
arBuckets これは、bucket * 型の配列です。配列内の各要素は、bucket* ポインタです。同じハッシュ値を持つ要素は、バケットの pNext ポインタと pLast ポインタを介して二重リンク リストに接続されます (この二重リンク リストは、前のものと同じ) 線形トラバーサルの二重リンク リストは同じものではありません)。したがって、バケットは実際にデータを保存するコンテナーです。
nApplyCount と bApplyProtection は、主に循環参照によって引き起こされる無限再帰を防ぐために使用される保護メカニズムを提供します。
persistent これは、メモリの割り当て方法に影響するブール変数です。これには、PHP のメモリ管理に関する知識が必要です。詳細については、
を参照してください。
(2) もう一つのデータ構造はバケットです
構造は次のように定義されます:
typedef 構造体バケット {
うろんh;
uint nKeyLength;
void *pData;
void *pDataPtr;
構造体バケット *pListNext;
構造体バケット *pListLast;
構造体バケット *pNext;
構造体バケット *pLast;
const char *arKey;
}バケツ;
その中に:
h ,arKey,nKeyLength PHP 配列には 2 つの異なるタイプのインデックスがあります。1 つは数値インデックスで、C の配列 ($arr = array(1=>'cont') など) によく似ています。もう 1 つは数値インデックスです。クラスは文字列インデックスです。つまり、配列項目のインデックスとしてキーワードを使用します ($arr = array('index'=>'cont'); など)。これら 2 種類のインデックスは、異なるメカニズムによって区別されます。 PHP の下部: 数値インデックスの場合、h はハッシュ値として直接使用されます。同時に、arKey=NULL および nKeyLength=0 は文字列インデックスの場合、arKey は文字列キーを保存し、nKeyLength はキーの長さを保存します。ハッシュ関数によって計算されたハッシュ値によって渡される文字列です。このように、PHP では、h、arKey、nKeyLength は配列内の要素を一意に決定するために実際に使用されます。これは、zend_hash_key 構造体の定義からもわかります。
/* 文字列インデックス */
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
/* 数値インデックスを追加 $arr[] = 'test' このフォーム */
;
if (フラグ & HASH_NEXT_INSERT) {
h = ht->nNextFreeElement;
}
/* 数値インデックスを指定する場合は h を直接使用します */
nIndex = h & ht->nTableMask;
pData と pDataPtr 通常、Bucket 内のデータは、pData ポインタが指すメモリ空間に格納されます。ただし、ポインターの保存などの例外もあります。このとき、pDataPtrはこのポインタを指し、pDataはpDataPtrを指します。これは、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); pefree_rel(p, (ht)->persistent);
F 返品失敗
(p)->pDataPtr=NULL;
}3.ハッシュテーブルの実装
1. HashTable関連のマクロ定義
HashTable の操作を容易にするために、PHP は最下位レベルで多くのマクロを定義します。
(1). CONNECT_TO_BUCKET_DLLIST(要素、リストヘッド)
このマクロは、バケットの二重リンク リストの先頭に要素を挿入するために使用されます。つまり、競合が発生した場合、新しく挿入された要素は常にバケットのリンク リストの先頭に配置されます。このマクロの定義は次のとおりです:
#define CONNECT_TO_BUCKET_DLLIST(要素, list_head)
(要素)->pNext = (list_head);
(要素)->pLast = NULL;
if ((要素)->pNext) {
(要素)->pNext->pLast = (要素);
} 3 (ht)->pListTail = (要素);
4 (要素)->pListNext = NULL;
5 if ((要素)->pListLast != NULL) {
6 (要素)->pListLast->pListNext = (要素);
7 }
810 (ht)->pListHead = (要素);
11 }
12
13 if ((ht)->pInternalPointer == NULL) {
14 (ht)->pInternalPointer = (要素);
15 }。
}
(5).INIT_DATA(ht、p、pData、nDataSize)
ここには実際には 2 つの状況があります。保存されるデータ自体がポインターである場合、pDataPtr はポインターを保存し、pData を pDataPtr のアドレスにポイントします。
それ以外の通常のデータを保存する場合は、nDataSize バイトのメモリ割り当てを申請し、pData が指す内容を p->pData のメモリにコピーします。ここで、コピーは memcpy を通じて実行されます。その src ポインターと dest ポインターが両方とも void * であるため、ほぼすべてのタイプのデータをコピーできます。
その他 {
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
if (!(p)->pData) {
pefree_rel(p, (ht)->persistent);
返品失敗;
}
memcpy((p)->pData, pData, nDataSize);
(p)->pDataPtr=NULL;
}
マクロ全体は次のように定義されます:
#define UPDATE_DATA(ht, p, pData, nDataSize)
if (nDataSize == sizeof(void*)) {
を使用
(p)->pDataPtr=NULL;
(p)->pData = (void *) perrealloc_rel((p)->pData, nDataSize, (ht)->persistent);
/* (p)->pDataPtr はすでに NULL なので初期化する必要はありません */
memcpy((p)->pData, pData, nDataSize);
} INIT_DATA と同様、違いは、前のメモリ ブロックでさらに処理を行う必要があることです (たとえば、実際のデータは以前に pData によって保存されましたが、ポインタは更新後に保存され、元々適用されていたメモリは解放される必要があり、そうでない場合)逆に、ポインタデータが以前に保存され、通常のデータが更新後に保存される場合は、pDataPtr を NULL に設定し、pData に新しいメモリ領域を割り当てる必要があります。このマクロの定義は次のとおりです。
if (nDataSize == sizeof(void*)) {
pefree_rel((p)->pData, (ht)->persistent);
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
を使用
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
(p)->pDataPtr=NULL;
/* (p)->pDataPtr はすでに NULL なので初期化する必要はありません */
memcpy((p)->pData, pData, nDataSize);
}#define CHECK_INIT(ht) do {
if (UNEXPECTED((ht)->nTableMask == 0)) {
& (ht)-& gt; ntableMask = (ht)-& gt;
}
} しながら (0)
2.ハッシュ関数
この記事を書いているときに、Niao 兄弟がすでに「PHP のハッシュ アルゴリズム」という記事を書いていることに気づきました。この記事では、ハッシュ アルゴリズムとアイデアについてより詳細な回答が得られました。ここではあまり説明しません。 ：展開された状態。アンロール自体は展開を意味します。nKeyLength の長さのキーの場合、PHP のハッシュ アルゴリズムは次の形式で 8 単位で展開されます。
を登録します
ケース 2: ハッシュ = ((ハッシュ << 5) + ハッシュ) + *arKey++; /* フォールスルー... */
ケース 1: ハッシュ = ((ハッシュ << 5) + ハッシュ) + *arKey++;
ケース 0: ブレーク;
EMPTY_SWITCH_DEFAULT_CASE()
}
/* 5. 返されたハッシュ値はモジュロ演算を受けていません */
ハッシュを返す;
}
3. 初期化、追加/更新、検索、削除などのAPI
(1).初期化
_zend_hash_init は、ハッシュテーブルの初期化操作(主にhashTable構造体のデータメンバーへの初期値の代入など)に使用されます。 _zend_hash_init を呼び出した後、nTableMask はデフォルトで 0 (後で CHECK_INIT 時に nTableSize-1 に割り当てられます)、nTableSize は nSize より大きい 2 の最小の整数乗に割り当てられ、nTableSize の最小値は 8、最大値は 0x80000000 です。 , arBuckets はメモリ空間を割り当てません (CHECK_INIT 中にも割り当てられます)。 nTableMask は、nTableMask = 2^n – 1 という特性を持っているため、ハッシュ値に対応するインデックスを高速に計算するために使用されます。バイナリに展開すると、すべてのビットが 1 になるため、インデックスの位置を高速に取得できます。 nIndex = h & nTableMask。この関数の実装ソース コード (バージョンごとに具体的な実装は異なります。この記事の PHP バージョンは 5.4.24 です):
ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool 永続的 ZEND_FILE_LINE_DC)
{
/* hashTable の最小サイズは 1<<3 = 8 */
uint i = 3;
SET_INCONSISTENT(HT_OK);
if (nSize >= 0x80000000) {
/* オーバーフローを防止 */
ht->nTableSize = 0x80000000;
} 他 {
while ((1U << i) < nSize) {
i++;
}
ht->nTableSize = 1 <
/* 文字列インデックスを検索 */
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)
{
/* 文字列インデックスであるため、インデックス キーを空にすることはできません。nKeyLength は >0 でなければなりません */
if (nKeyLength
失敗を返す;
}
/* ht が初期化されているかどうか、初期化されていない場合は arBuckets のメモリ空間を割り当て、nTableMask を設定します */
CHECK_INIT(ht);
/* ハッシュテーブルのインデックスを計算します */
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
/* バケット リストをスキャンして要素が存在するかどうかを確認し、存在する場合は更新して */
while (p != NULL) {
if (p->arKey == arKey ||
((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
/* 競合しているため追加できません */
if (フラグ & HASH_ADD) {
失敗を返す;
}
HANDLE_BLOCK_INTERRUPTIONS();
if (ht->pDestructor) {
ht->pDestructor(p->pData);
}
/* 更新操作を実行します */
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p->pData;
}
HANDLE_UNBLOCK_INTERRUPTIONS();
成功を返します;
}
ht->nTableMask = 0; /* 0 は ht->arBuckets が初期化されていないことを意味します */
ht->pDestructor = pDestructor;
ht->arBuckets = (バケット**)&uninitialized_bucket;
ht->pListHead = NULL;
ht->pListTail = NULL;
ht->nNumOfElements = 0;
ht->nNextFreeElement = 0;
ht->pInternalPointer = NULL;
ht->persistent = 永続的;
ht->nApplyCount = 0;
ht->bApplyProtection = 1;
成功を返します;
}
(2). 要素を見つけます。
文字列インデックスと数値インデックスの場合、それぞれ zend_hash_find と zend_hash_index_find の 2 つの検索メソッドが提供されます。これら 2 つのメソッドには本質的な違いはありません。どちらも、ハッシュ値を計算した後に、対応するバケット内の要素の位置を見つけます。文字列インデックスの場合、同じことを決定する条件は次のとおりです: p->arKey == arKey ||((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p- > ;arKey, arKey, nKeyLength))、つまり、arKey と p->arKey が同じメモリを指すか、h、nKeyLength、および arKey が指す内容がまったく同じであるため、それらは次のように判断できます。同じ。数値インデックスの場合、(p->h == h) && (p->nKeyLength == 0) のみが必要です。これら 2 つの検索の実装は次のとおりです:
/* 数値インデックスを検索 */
ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
{
uint nIndex;
バケツ *p;
IS_CONSISTENT(ht);
/* インデックスを計算 */
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
/* 二重リンクリストを走査し、見つかったらすぐに戻ります */
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == 0)) {
*pData = p->pData;
成功を返す;
}
p = p->pNext;
}
/* 二重リンクリストを走査しても何も見つからない場合、検索は失敗します */
失敗を返す;
}
/* 文字列インデックスを検索 */
ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
{
うろんh;
uint nIndex;
バケツ *p;
IS_CONSISTENT(ht);
/* 文字列インデックスは最初に文字列のハッシュ値を計算する必要があります */
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
/* バケットの二重リンクリストを検索します。見つかったら、すぐに検索に戻ります。 */
while (p != NULL) {
if (p->arKey == arKey ||
((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
*pData = p->pData;
成功を返す;
}
p = p->pNext;
}
/* 検索に失敗しました */
失敗を返す;
}
(3).要素の挿入
PHP スクリプトでは、現在の配列に要素を挿入するための次の 3 つの形式があります。
$arr = 配列();
$arr['index'] = 'cont';
$arr[2] = 'テスト';
$arr[] = 10;
3 つの挿入方法は、「文字列インデックスの挿入」、「数値インデックスの挿入」、および「次の利用可能な位置の挿入」です。実装では、「文字列インデックスの挿入」は _zend_hash_add_or_update に対応し、後の 2 つは _zend_hash_index_update_or_next_insert に対応します。例として、operation $arr['index'] = 'cont' は、対応するデータを最初に更新しようとします。対応する Bucket が見つからない場合は、これが新しい要素であることを意味するため、挿入操作が実行されます。これは、_zend_hash_add_or_update で次のように実装されます (重要でない手順は省略しています)。
を返します。
p = ht->arBuckets[nIndex]; }
p = p->pNext;
}
/* 不存在元素，则挿入 */
if (IS_INTERNED(arKey)) {
p = (バケット *) pemalloc(sizeof(バケット), ht->persistent);
if (!p) {
失敗を返す;
}
p->arKey = arKey;
} else {
p = (バケット *) pemalloc(sizeof(バケット) + nKeyLength, ht->persistent);
if (!p) {
失敗を返す;
}
p->arKey = (const char*)(p + 1);
memcpy((char*)p->arKey, arKey, nKeyLength);
}
p->nKeyLength = nKeyLength;
INIT_DATA(ht, p, pData, nDataSize);
p->h = h;
/* バケット链表の头部に插入 */
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
/* 插入到全局的双链表，用到遍历，是个逻辑队列 */
CONNECT_TO_GLOBAL_DLLIST(p, ht);
ht->arBuckets[nIndex] = p;
/* 增加元素个数 */
ht->nNumOfElements++;
/* 如果nNumOfElements > nTableSize，必要对HashTable扩容 */
ZEND_HASH_IF_FULL_DO_RESIZE(ht);
}
HashTable のその他の操作たとえば、zend_hash_do_resize（扩容）、zend_hash_rehash（扩容の後に原来hashTable の要素再新ハッシュが必要）、zend_hash_del_key_or_index（HashTable 中删除元素）、zend_hash_destroy（销毁ハッシュ表）、zend_hash_copy（ハッシュ表贝），这里不さらに興味のあるものは、ソースコードを翻訳してご覧いただけます。
上一篇http://www.Bkjia.com/kf/201411/356800.html
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。