php内核解析:PHP中的哈希表

PHP中使用最为频繁的数据类型非字符串和数组莫属,PHP比较容易上手也得益于非常灵活的数组类型。 在开始详细介绍这些数据类型之前有必要介绍一下哈希表(HashTable)。 哈希表是PHP实现中尤为关键的数据结构。

哈希表在实践中使用的非常广泛,例如编译器通常会维护的一个符号表来保存标记,很多高级语言中也显式的支持哈希表。 哈希表通常提供查找(Search),插入(Insert),删除(Delete)等操作,这些操作在最坏的情况下和链表的性能一样为O(n)。 不过通常并不会这么坏,合理设计的哈希算法能有效的避免这类情况,通常哈希表的这些操作时间复杂度为O(1)。 这也是它被钟爱的原因。
正是因为哈希表在使用上的便利性及效率上的表现,目前大部分动态语言的实现中都使用了哈希表。

为了方便读者阅读后面的内容,这里提前列举一下HashTable实现中出现的基本概念。 哈希表是一种通过哈希函数,将特定的键映射到特定值的一种数据结构,它维护键和值之间一一对应关系。
键(key):用于操作数据的标示,例如PHP数组中的索引,或者字符串键等等。

槽(slot/bucket):哈希表中用于保存数据的一个单元,也就是数据真正存放的容器。

哈希函数(hash function):将key映射(map)到数据应该存放的slot所在位置的函数。

哈希冲突(hash collision):哈希函数将两个不同的key映射到同一个索引的情况。

哈希表可以理解为数组的扩展或者关联数组,数组使用数字下标来寻址,如果关键字(key)的范围较小且是数字的话, 我们可以直接使用数组来完成哈希表,而如果关键字范围太大,如果直接使用数组我们需要为所有可能的key申请空间。 很多情况下这是不现实的。即使空间足够,空间利用率也会很低,这并不理想。同时键也可能并不是数字, 在PHP中尤为如此,所以人们使用一种映射函数(哈希函数)来将key映射到特定的域中:

代码如下:

h(key) -> index

通过合理设计的哈希函数,我们就能将key映射到合适的范围,因为我们的key空间可以很大(例如字符串key), 在映射到一个较小的空间中时可能会出现两个不同的key映射被到同一个index上的情况, 这就是我们所说的出现了冲突。 目前解决hash冲突的方法主要有两种:链接法和开放寻址法。

冲突解决

链接法:链接法通过使用一个链表来保存slot值的方式来解决冲突,也就是当不同的key映射到一个槽中的时候使用链表来保存这些值。 所以使用链接法是在最坏的情况下,也就是所有的key都映射到同一个槽中了,操作链表的时间复杂度为O(n)。 所以选择一个合适的哈希函数是最为关键的。目前PHP中HashTable的实现就是采用这种方式来解决冲突的。
开放寻址法:通常还有另外一种解决冲突的方法:开放寻址法。使用开放寻址法是槽本身直接存放数据, 在插入数据时如果key所映射到的索引已经有数据了,这说明发生了冲突,这是会寻找下一个槽, 如果该槽也被占用了则继续寻找下一个槽,直到寻找到没有被占用的槽,在查找时也使用同样的策律来进行。

哈希表的实现

在了解到哈希表的原理之后要实现一个哈希表也很容易,主要需要完成的工作只有三点:
实现哈希函数
冲突的解决
操作接口的实现
首先我们需要一个容器来保存我们的哈希表,哈希表需要保存的内容主要是保存进来的的数据, 同时为了方便的得知哈希表中存储的元素个数,需要保存一个大小字段, 第二个需要的就是保存数据的容器了。作为实例,下面将实现一个简易的哈希表。基本的数据结构主要有两个, 一个用于保存哈希表本身,另外一个就是用于实际保存数据的单链表了,定义如下:

代码如下:

typedef struct _Bucket
{
 char *key;
 void *value;
 struct _Bucket *next;

} Bucket;

typedef struct _HashTable
{
 int size;
 Bucket* buckets;
} HashTable;

上面的定义和PHP中的实现类似,为了便于理解裁剪了大部分无关的细节,在本节中为了简化, key的数据类型为字符串,而存储的数据类型可以为任意类型。
Bucket结构体是一个单链表,这是为了解决多个key哈希冲突的问题,也就是前面所提到的的链接法。 当多个key映射到同一个index的时候将冲突的元素链接起来。
哈希函数需要尽可能的将不同的key映射到不同的槽(slot或者bucket)中,首先我们采用一种最为简单的哈希算法实现: 将key字符串的所有字符加起来,然后以结果对哈希表的大小取模,这样索引就能落在数组索引的范围之内了。

代码如下:

static int hash_str(char *key)
{
 int hash = 0;

char *cur = key;

while(*(cur++) != '\0') {
 hash += *cur;
 }

return hash;
}

// 使用这个宏来求得key在哈希表中的索引
#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)

这个哈希算法比较简单,它的效果并不好,在实际场景下不会使用这种哈希算法, 例如PHP中使用的是称为DJBX33A算法, 这里列举了Mysql,OpenSSL等开源软件使用的哈希算法, 有兴趣的读者可以前往参考。
操作接口的实现
为了操作哈希表,实现了如下几个操作函数:

代码如下:

int hash_init(HashTable *ht); // 初始化哈希表
int hash_lookup(HashTable *ht, char *key, void **result); // 根据key查找内容
int hash_insert(HashTable *ht, char *key, void *value); // 将内容插入到哈希表中
int hash_remove(HashTable *ht, char *key); // 删除key所指向的内容
int hash_destroy(HashTable *ht);

下面以插入和获取操作函数为例:

代码如下:

int hash_insert(HashTable *ht, char *key, void *value)
 {
 // check if we need to resize the hashtable
 resize_hash_table_if_needed(ht); // 哈希表不固定大小,当插入的内容快占满哈表的存储空间
 // 将对哈希表进行扩容, 以便容纳所有的元素

int index = HASH_INDEX(ht, key); // 找到key所映射到的索引

Bucket *org_bucket = ht->buckets[index];
 Bucket *bucket = (Bucket *)malloc(sizeof(Bucket)); // 为新元素申请空间

bucket->key = strdup(key);
 // 将值内容保存进来, 这里只是简单的将指针指向要存储的内容,而没有将内容复制。
 bucket->value = value;

LOG_MSG("Insert data p: %p\n", value);

ht->elem_num += 1; // 记录一下现在哈希表中的元素个数

if(org_bucket != NULL) { // 发生了碰撞,将新元素放置在链表的头部
 LOG_MSG("Index collision found with org hashtable: %p\n", org_bucket);
 bucket->next = org_bucket;
 }

ht->buckets[index]= bucket;

LOG_MSG("Element inserted at index %i, now we have: %i elements\n",
 index, ht->elem_num);

return SUCCESS;
 }

上面这个哈希表的插入操作比较简单,简单的以key做哈希,找到元素应该存储的位置,并检查该位置是否已经有了内容, 如果发生碰撞则将新元素链接到原有元素链表头部。在查找时也按照同样的策略,找到元素所在的位置,如果存在元素, 则将该链表的所有元素的key和要查找的key依次对比, 直到找到一致的元素,否则说明该值没有匹配的内容。

代码如下:

int hash_lookup(HashTable *ht, char *key, void **result)
{
 int index = HASH_INDEX(ht, key);
 Bucket *bucket = ht->buckets[index];

if(bucket == NULL) return FAILED;

// 查找这个链表以便找到正确的元素,通常这个链表应该是只有一个元素的,也就不用多次
 // 循环。要保证这一点需要有一个合适的哈希算法,见前面相关哈希函数的链接。
 while(bucket)
 {
 if(strcmp(bucket->key, key) == 0)
 {
 LOG_MSG("HashTable found key in index: %i with key: %s value: %p\n",
 index, key, bucket->value);
 *result = bucket->value;
 return SUCCESS;
 }

bucket = bucket->next;
 }

LOG_MSG("HashTable lookup missed the key: %s\n", key);
 return FAILED;
}

PHP中数组是基于哈希表实现的,依次给数组添加元素时,元素之间是有先后顺序的,而这里的哈希表在物理位置上显然是接近平均分布的, 这样是无法根据插入的先后顺序获取到这些元素的,在PHP的实现中Bucket结构体还维护了另一个指针字段来维护元素之间的关系。 具体内容在后一小节PHP中的HashTable中进行详细说明。上面的例子就是PHP中实现的一个精简版。

(0)

相关推荐

  • java中哈希表及其应用详解

    哈希表也称为散列表,是用来存储群体对象的集合类结构. 什么是哈希表 数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系.当要查找一个对象时,只能以某种顺序(如顺序查找或二分查找)与各个元素进行比较,当数组或向量中的元素数量很多时,查找的效率会明显的降低. 一种有效的存储方式,是不与其他元素进行比较,一次存取便能得到所需要的记录.这就需要在对象的存储位置和对象的关键属性(设为 k)之间建立一个特定的对应关系(设为 f),使每个对象与一个唯一的存储位置

  • js中哈希表的几种用法总结

    1. 复制代码 代码如下: <html><head><script type="text/javascript">// by Go_Rush(我们)  from http://www.jb51.net/ var hash={    "百度"            :"http://www.baidu.com/",    "Google"        :"http://www.go

  • JavaScript中实现键值对应的字典与哈希表结构的示例

    字典(Dictionary)的javascript实现 编程思路: 使用了裸对象datastore来进行元素存储: 实现了两种得到字典长度的方法,一种为变量跟踪,一种为实时计算. 代码: function(){ "use strict"; function Dictionary(){ this._size = 0; this.datastore = Object.create(null); } Dictionary.prototype.isEmpty = function(){ ret

  • python实现哈希表

    复制代码 代码如下: #! /usr/bin/env python#coding=utf-8#实现哈希表(线性地址再散列) def ChangeKey(key,m,di):    key01=(key+di) % m    return key01 a=raw_input("Please entry the numbers:\n").split()m=len(a)dict01={}for i in a:    key=int(i)%m    if "%s"%key

  • C++ 实现哈希表的实例

    C++ 实现哈希表的实例 该散列表的散列函数采用了除法散列函数.乘法散列函数.全域散列函数,每一个槽都是使用有序单向链表实现. 实现代码: LinkNode.h #include<iostream> using namespace std; class Link; class LinkNode { private: int key; LinkNode* next; friend Link; public: LinkNode():key(-1),next(NULL){} LinkNode(int

  • C++中使用哈希表(unordered_map)的一些常用操作方法

    目录 1.建立基本数据类型的哈希表 2.向哈希表中添加元素 1).insert函数 2).用数组方法直接添加 3.成员函数 begin(),end()函数 find()查找函数 count()查找函数 size()函数 empty()函数 clear()函数 swap()函数 哈希表的遍历 第一种遍历 第二种遍历 补充:实际应用 总结 1.建立基本数据类型的哈希表 unordered_map<int,int> m; //<string,string>,<char,char&g

  • php内核解析:PHP中的哈希表

    PHP中使用最为频繁的数据类型非字符串和数组莫属,PHP比较容易上手也得益于非常灵活的数组类型. 在开始详细介绍这些数据类型之前有必要介绍一下哈希表(HashTable). 哈希表是PHP实现中尤为关键的数据结构. 哈希表在实践中使用的非常广泛,例如编译器通常会维护的一个符号表来保存标记,很多高级语言中也显式的支持哈希表. 哈希表通常提供查找(Search),插入(Insert),删除(Delete)等操作,这些操作在最坏的情况下和链表的性能一样为O(n). 不过通常并不会这么坏,合理设计的哈希

  • PHP内核探索:哈希表碰撞攻击原理

    下面通过图文并茂的方式给大家展示PHP内核探索:哈希表碰撞攻击原理. 最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷纷中招.本文结合PHP内核源码,聊一聊这种攻击的原理及实现.  哈希表碰撞攻击的基本原理 哈希表是一种查找效率极高的数据结构,很多语言都在内部实现了哈希表.PHP中的哈希表是一种极为重要的数据结构,不但用于表示Array数据类型,还在Zend虚拟机内部用于存储上下文环境信息(执行上下文的变量及函数均使用哈希表结

  • 全面解析Java中的引用类型

    如果一个内存中的对象没有任何引用的话,就说明这个对象已经不再被使用了,从而可以成为被垃圾回收的候选.不过由于垃圾回收器的运行时间不确定,可被垃圾回收的对象的实际被回收时间是不确定的.对于一个对象来说,只要有引用的存在,它就会一直存在于内存中.如果这样的对象越来越多,超出了JVM中的内存总数,JVM就会抛出OutOfMemory错误.虽然垃圾回收的具体运行是由JVM来控制的,但是开发人员仍然可以在一定程度上与垃圾回收器进行交互,其目的在于更好的帮助垃圾回收器管理好应用的内存.这种交互方式就是使用J

  • C++中的数组、链表与哈希表

    目录 数组和链表 数组 链表 什么是链表? 链表的操作 双向链表(list) list的成员函数 哈希表 什么是哈希表? 哈希碰撞 哈希表应用场景 构建哈希表 哈希表基本使用 Leetcode对应题目 前缀和 差分数组 滑动窗口 二分查找 数组和链表 C++的数组和链表分别是什么?分别有什么种类?它们都有什么特性?针对这些特征,使用情形是什么? 数组 什么是数组? 一个数组就像是一个变量,它可以存储一组值,但是所有值都是相同的数据类型. 一个int数组定义:int hours [6] 该数组类型

  • JS模拟实现哈希表及应用详解

    本文实例讲述了JS模拟实现哈希表及应用.分享给大家供大家参考,具体如下: 在算法中,尤其是有关数组的算法中,哈希表的使用可以很好的解决问题,所以这篇文章会记录一些有关js实现哈希表并给出解决实际问题的例子. 说明: 这篇文章所写并不是真正意义的哈希表,只是与哈希表的使用有相似之处. 第一部分:相关知识点 属性的枚举: var person = { name: "zzw", sex: "Male", age: 21 }; for (var prop in person

  • python如何解析复杂sql,实现数据库和表的提取的实例剖析

    需求: 公司的数据分析师,提交一个sql, 一般都三四百行.由于数据安全的需要,不能开放所有的数据库和数据表给数据分析师查询,所以需要解析sql中的数据库和表,与权限管理系统中记录的数据库和表权限信息比对,实现非法查询的拦截. 解决办法: 在解决这个问题前,现在github找了一下轮子,发现python下面除了sql parse没什么好的解析数据库和表的轮轮.到是在java里面找到presto-parser解析的比较准.于是自己结合sql parse源码写了个类,供大家参考,测试了一下,检测还是

  • Java 集合框架掌握 Map 和 Set 的使用(内含哈希表源码解读及面试常考题)

    目录 1. 搜索 1.1 场景引入 1.2 模型 2. Map 2.1 关于 Map 的介绍 2.2 关于 Map.Entry<K, V> 的介绍 2.3 Map 的常用方法说明 2.4 关于 HashMap 的介绍 2.5 关于 TreeMap 的介绍 2.6 HashMap 和 TreeMap 的区别 2.7 Map 使用示例代码 3. Set 3.1 关于 Set 的介绍 3.1 Set 的常用方法说明 3.3 关于 TreeSet 的介绍 3.4 关于 HashSet 的介绍 3.5

  • 解析HashMap中的put方法执行流程

    目录 引言 HashMap底层数据结构 put方法的执行流程 总结 引言 在Java集合中,HashMap的重要性不言而喻,作为一种存储键值对的数据结构,它在日常开发中有着非常多的应用场景,也是面试中的高频考点,本篇文章就来分析一下HashMap集合中的put方法. HashMap底层数据结构 先来了解一下HashMap底层的数据结构,它实质上是一个散列表,在数据结构课程中,我们应该都学习过散列表,它是通过关键码值而直接进行访问的一种数据结构,比如存储这样的一个序列:5,12,7,6,1,3.我

  • Perl哈希表用法解析

    本文和大家重点讨论一下Perl哈希表的概念,Perl语言和其他编程语言各有各的特点,这里和大家分享一下Perl哈希表的概念,其实Perl哈希表是一种结构. Perl哈希表Perl哈希表是一种结构.key/value.访问Perl哈希表元素$Perl哈希表{$some_key}当给Perl哈希表选择名字时,最好这样思考:Perl哈希表元素的名字和key之间可以用for来连接.如thefamily_nameforfredisflintstone. 要引用整个Perl哈希表,使用百分号(%)作为前缀.

随机推荐