PHP用哈希表和链表解决哈希冲突的方法

本篇文章为大家展示了PHP用哈希表和链表解决哈希冲突的方法,代码简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。

成都创新互联公司专注于阿克塞哈萨克族自治网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供阿克塞哈萨克族自治营销型网站建设,阿克塞哈萨克族自治网站制作、阿克塞哈萨克族自治网页设计、阿克塞哈萨克族自治网站官网定制、小程序制作服务,打造阿克塞哈萨克族自治网络公司原创品牌,更为您提供阿克塞哈萨克族自治网站排名全网营销落地服务。

一、哈希表

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

哈希冲突的解决方案,要么使用链接法,要么使用开放寻址法

链接法

即当不同的关键字映射到同一单元时,在同一单元内使用链表来保存这些关键字

开放寻址法

即当插入数据时,如果发现关键字被映射到的单元存在数据了,说明发生了冲突,就继续寻找下一个单元,直到找到可用单元为止

而因为开放寻址法方案属于占用其他关键字映射单元的位置,所以后续的关键字更容易出现哈希冲突,因此容易出现性能下降

二、链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作。

对于数据结构的内容,我们不过多展开,我们之后会有专门的内容去详细介绍数据结构

三、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;

上述内容就是PHP用哈希表和链表解决哈希冲突的方法,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注创新互联行业资讯频道。


网页名称:PHP用哈希表和链表解决哈希冲突的方法
标题路径:http://scyanting.com/article/jjsjec.html