PHP 해시 테이블 및 배열 소개(코드 포함)
- 不言앞으로
- 2019-04-02 11:49:303692검색
이 기사는 PHP 해시 테이블 및 배열(코드 포함)에 대한 소개를 제공합니다. 이는 특정 참조 가치가 있습니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.
배열은 PHPer에서 가장 일반적으로 사용되는 데이터 유형입니다. 동시에 PHP는 강력한 배열 덕분에 사용하기 쉽습니다. 그런데 PHP에서 배열은 어떻게 구현됩니까?
우선, 다음 콘텐츠의 탄탄한 기반을 마련하기 위해 해당 데이터 구조를 먼저 이해합시다
해시 테이블
哈希表
哈希表，顾名思义，即将不同的关键字映射到不同单元的一种数据结构。而将不同关键字映射到不同单元的方法就叫做哈希函数
理想情况下，经过哈希函数处理，关键字和单元是会进行一一对应的；但是如果关键字值足够多的情况下，就容易出现多个关键字映射到同一单元的情况，即出现哈希冲突
哈希冲突的解决方案，要么使用链接法，要么使用开放寻址法
链接法
即当不同的关键字映射到同一单元时，在同一单元内使用链表来保存这些关键字
开放寻址法
即当插入数据时，如果发现关键字被映射到的单元存在数据了，说明发生了冲突，就继续寻找下一个单元，直到找到可用单元为止
而因为开放寻址法方案属于占用其他关键字映射单元的位置，所以后续的关键字更容易出现哈希冲突，因此容易出现性能下降
链表
既然上面提到了链表，这里我们简单聊一下链表的基础知识。链表分为很多种类型，常用的数据结构包括：队列，栈，双向链表等
链表，就是由不同的链表节点组成的一种数据结构。链表节点一般由元素+指向下一节点的指针组成。而双向链表，顾名思义，则是由指向上一节点的指针+元素+指向下一节点的指针组成
对于数据结构的内容，我们不过多展开，我们之后会有专门的内容去详细介绍数据结构
php数组
php解决哈希冲突的方式是使用了链接法，所以php数组是由哈希表+链表实现，准确来说，是由哈希表+双向链表实现
内部结构-哈希表
HashTable结构体主要用来存放哈希表的基本信息
typedef struct _hashtable {
uint nTableSize; // hash Bucket的大小，即哈希表的容量，最小为8，以2x增长。
uint nTableMask; // nTableSize-1 ， 索引取值的优化
uint nNumOfElements; // hash Bucket中当前存在的元素个数，count()函数会直接返回此值
ulong nNextFreeElement; // 下一个可使用的数字键值
Bucket *pInternalPointer; // 当前遍历的指针（foreach比for快的原因之一）
Bucket *pListHead; // 存储整个哈希表的头元素指针
Bucket *pListTail; // 存储整个哈希表的尾元素指针
Bucket **arBuckets; // 存储hash数组
dtor_func_t pDestructor; // 在删除元素时执行的回调函数，用于资源的释放
zend_bool persistent; //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
Bucket结构体则用于保存数据的具体内容
typedef struct bucket {
ulong h; // 对char *key进行hash后的值，或者是用户指定的数字索引值
uint nKeyLength; // hash关键字的长度，如果数组索引为数字，此值为0
void *pData; // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
void *pDataPtr; // 如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
struct bucket *pListNext; // 指向整个哈希表的该单元的下一个元素
struct bucket *pListLast; // 指向整个哈希表的该单元的上一个元素
struct bucket *pNext; // 指向由于哈希冲突导致存放在同一个单元的链表中的下一个元素
struct bucket *pLast; // 指向由于哈希冲突导致存放在同一个单元的链表中的上一个元素
// 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
char arKey[1];
} Bucket;
其中Bucket结构体内有指向用户数据的pData元素，其实是指向了之前我们介绍的变量zval结构体，这也是为什么当创建数组时，会出现数组元素+1的变量容器。
哈希表内部结构关系图
注：图片来源于网络
从上图我们可以看出，Bucket在存放数据的时候，如果存在哈希冲突，则将多个关键字映射到链表中，由此组成了双向链表
总结
今天，我们以数组作为切入点，简单了解了下基本的数据结构：哈希表和链表；并且了解了数组的底层实现，即哈希表+双向链表
해시 테이블해시 함수<br><p class="mb20">이상적으로는 해시로 처리한 후 함수에서는 키워드와 단위 사이에 일대일 대응이 있습니다. 그러나 키워드 값이 충분하면 여러 키워드가 동일한 단위에 매핑되기 쉽습니다. 즉, <code> 해시 충돌 code><a href="http://www.php.cn/course/list/29.html" target="_blank"></a>해시 충돌에 대한 해결책은 <code>체인 방법 또는 공개 주소 지정 방법
체인 방법을 사용하는 것입니다.
즉, 서로 다른 키워드가 동일한 단위에 매핑되는 경우 연결된 목록을 사용하여 이러한 키워드를 동일한 단위에 저장합니다
즉, 데이터를 삽입할 때, 키워드가 매핑된 유닛에 데이터가 있다는 것은 충돌이 발생했다는 의미이며, 사용 가능한 유닛을 찾을 때까지 계속해서 다음 유닛을 탐색한다🎜🎜그리고 오픈 어드레싱 방식 방식이 차지하기 때문에 다른 키워드 매핑 단위의 위치가 다르기 때문에 후속 키워드는 해시 충돌이 발생할 가능성이 높으므로 성능 저하가 발생하기 쉽습니다🎜
연결 목록🎜🎜 위에서 연결리스트에 대해 언급하였으니 여기서는 간략하게 이야기하고 연결리스트의 기본에 대해 알아보도록 하겠습니다. 연결 목록은 여러 유형으로 구분됩니다. 일반적으로 사용되는 데이터 구조에는 큐, 스택, 양방향 연결 목록 등이 있습니다. 연결 목록은 서로 다른 연결 목록 노드로 구성된 데이터 구조입니다. 연결된 목록 노드는 일반적으로 요소 + 다음 노드에 대한 포인터로 구성됩니다. 이중 연결 목록은 이름에서 알 수 있듯이 이전 노드에 대한 포인터+요소+다음 노드에 대한 포인터🎜🎜로 구성됩니다. data 구조의 내용을 확장하지는 않겠습니다. 나중에 데이터 구조를 자세히 소개하는 특별한 내용을 준비하겠습니다🎜
php 배열🎜🎜 php는 해싱을 해결한다. 충돌의 방법은 연결방식을 사용하는 것이므로 PHP 배열은 해시테이블 + 연결리스트로 구현한다. code>해시 테이블+이중 연결 목록 구현🎜
내부 구조-해시 테이블🎜🎜HashTable 구조 주로 해시를 저장하는 데 사용됩니다. 테이블의 기본 정보🎜rrreee🎜Bucket 구조는 데이터의 특정 내용을 저장하는 데 사용됩니다.🎜rrreee🎜Bucket 구조에는 사용자 데이터를 가리키는 pData 요소가 포함되어 있으며 실제로는 zval 변수를 가리킵니다. 앞서 소개한 구조이기 때문에 배열을 생성할 때 배열 요소 + 1의 변수 컨테이너가 나타납니다. 🎜🎜해시 테이블 내부 구조 다이어그램🎜🎜🎜🎜참고: 사진은 인터넷에서 가져온 것입니다🎜🎜위 그림에서 버킷이 데이터를 저장할 때 해시 충돌이 있는 경우 여러 키워드가 연결 목록에 매핑되어 이중 연결 목록을 형성합니다🎜🎜요약🎜오늘 우리는 배열을 시작점으로 사용하여 기본 데이터 구조인 해시 테이블과 연결 목록을 간략하게 이해하고 배열의 기능을 이해합니다. 구현은 해시 테이블 + 이중 연결 목록입니다. 실제로 해시 테이블은 PHP에서 가장 중요한 데이터 구조이며 다양한 용도로 사용됩니다. 🎜🎜【관련 추천: 🎜PHP 비디오 튜토리얼🎜】🎜🎜🎜
위 내용은 PHP 해시 테이블 및 배열 소개(코드 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!