PHP内核解析：PHP中的哈希表

最常用的数据类型，在PHP中是非字符串和数组，和PHP很容易利用一个非常灵活的数组类型，有必要引入哈希表（HashTable）开始之前，这些数据类型的详细介绍，哈希表是在PHP实现一个特别关键的数据结构。

哈希表在实践中被广泛使用，例如，通常由编译器维护的符号表来存储标记。在许多高级语言，明确的哈希表也明确支持。哈希表通常提供诸如搜索，插入，和删除操作，而在最坏的情况下，为O（N）作为链接列表的性能。但是，它通常不是很坏，一个设计合理的Hash算法有效的避免这种情况，通常这些操作的时间复杂度为O的哈希表（1）。这也是为什么它是爱。
由于哈希表的方便性和效率，大多数动态语言实现都使用哈希表。

为了便于读者阅读下面的内容，这里是一个列表，哈希表中的实施出现的基本概念。哈希表是一个数据结构映射特定键通过一个哈希函数的一个特定值，而保持键和值之间的一个一一对应。
键（键）：操作数据的指示，如PHP数组中的索引或字符串键等。

槽/桶：用于存储数据的哈希表中的一个单元，即由数据真正存储的容器。

散列函数（散列函数）：一种将键（map）映射到存储数据的槽位置的函数。

哈希冲突（哈希冲突）：散列函数将两个不同的键映射到同一索引。

哈希表可以被理解为一个数组或关联数组扩展，使用数字处理数组下标，如果关键字（key）范围小、人数多的话，我们可以直接使用数组完成哈希表，如果关键字范围太大，如果直接使用我们需要申请所有可能的密钥空间的阵列。在许多情况下，这是不现实的。即使有足够空间，空间利用率很低，这是不理想的。相同的密钥可能不多，特别是在PHP，所以人们用一个映射函数（散列函数）图的关键成特定领域：

复制代码代码如下所示：
h（键）-索引

通过哈希函数的合理设计，我们可以映射到适当的范围的关键，因为我们的密钥空间可以很大（例如，字符串键）可以被映射到两个不同的密钥被映射到同一指标在一个小空间，这就是我们所说的有冲突出现。是目前解决哈希冲突的两种主要方法：联系法和开放定址法。

冲突的解决

连接方法：连接方法采用链表来保存槽值解决冲突，也就是说，当不同的键映射到一个槽，用链表来保存这些值。所以使用链接的方法是在最坏的情况下，即所有的键映射到同一个槽，和操作链的时间复杂度为O（n），因此选择一个合适的哈希函数最重要。目前，PHP中的哈希表的实现是用这种方法来解决冲突。
开放寻址：通常有另一种方式来解决冲突：开放寻址法。开放寻址使用插槽本身直接存储数据，当数据如果关键指标已被映射到数据的插入，这表明冲突，它正在寻找下一个槽，如果插槽占将继续寻找下一个槽，直到我找到不占据搜索的插槽，使用相同的政策法。

哈希表的实现

在了解哈希表的原理之后，也很容易实现哈希表。要完成的主要工作只有三分：
实现哈希函数
冲突的解决
操作界面的实现
首先我们需要一个容器来存放哈希表，将存储的哈希表是数据保护的主要内容，同时对哈希表，方便存储单元需要保存规模场数，第二需要保存数据的容器，作为一个例子，一个简单的哈希表将实施以下。有两个基本的数据结构，一个是节省哈希表本身，另一个是单链表用于保存数据。它的定义如下：

复制代码代码如下所示：
typedef struct _bucket
{
字符*键；
空*值；
结构_bucket *下；

桶}；

typedef struct _hashtable
{
数组的大小；
桶*桶；
哈希表}；

上面的定义类似于PHP中的实现。为了理解和剪裁大多数不相关的细节，在这一节中，为了简化，键的数据类型是一个字符串，存储的数据类型可以是任意类型。
桶结构是一种单链表，它解决了多键哈希冲突问题，即前面提到的链接方法，当多个键映射到同一索引时，冲突元素被链接起来。
哈希函数要求尽可能多地将不同的密钥映射到不同的时隙（槽或桶），我们使用了一种最简单的散列算法：将密钥串的所有字符相加，然后哈希表模型的大小结果，这个索引就可以在数组索引的范围内。

复制代码代码如下所示：
静态变量hash_str（char *键）
{
int散列= 0；

字符集；

当（*（+ +））！=0）{
哈希=当前；
}

返回哈希；
}

使用此宏获取哈希表索引中的键
#定义hash_index（HT，关键）（hash_str（（关键））%（HT）->大小）

哈希算法比较简单，其效果不好，不在实际场景中使用哈希算法，如在使用PHP为djbx33a算法，这里是一个名单，MySQL，使用哈希算法OpenSSL等开源软件，有兴趣的读者可以参考。
操作界面的实现
为了操作哈希表，实现以下操作功能：

复制代码代码如下所示：
国际hash_init（哈希表* HT）； / /初始化哈希表
国际hash_lookup（哈希表* HT，char *键，void * *结果）； / /关键根据搜索内容
国际hash_insert（哈希表* HT，char *键，void*值）； / /内容为哈希表
国际hash_remove（哈希表* HT，char *键）； / /删除键指向的内容
国际hash_destroy（哈希表* HT）；

下面是一个操作函数的插入和获取示例。

复制代码代码如下所示：
国际hash_insert（哈希表* HT，char *键，void*值）
{
检查我们是否需要调整 /哈希表
resize_hash_table_if_needed（HT）； / /哈希表是不是固定大小，当插入的内容迅速占领哈萨克斯坦表存储空间
将扩展哈希表的容量，以容纳所有元素。

指数= hash_index（HT，键）； / /找到索引的键映射

斗* org_bucket = HT ->桶{指数}；
桶桶（桶* = * malloc）（sizeof（桶））； / /应用新的元素空间

斗>键= strdup（关键）；
内容存储在 / 值中，这里只是指向存储内容的指针，而不是复制内容。
桶>值=值；

log_msg（插入数据：% P P

HT—> elem_num + = 1； / /现在记录在哈希表中元素的个数

如果（org_bucket！= NULL）碰撞，将被放置在新的头的列表中。
log_msg（指数碰撞发现org哈希表：% P
斗>下= org_bucket；
}

桶；

log_msg（元素插入指数%的我，现在我们有：%我元素
指数，HT -> elem_num）；

返回成功；
}

哈希表的插入操作相对简单。只需用键进行散列，找到存储元素的位置，并检查位置是否是内容。如果发生冲突，将新元素链接到原始元素列表的头部。在搜索时，它也会根据相同的策略查找元素的位置。如果有一个元素，那么列表中所有元素的键都将与要搜索的键进行比较，直到找到一致的元素，否则，该值将不匹配。

复制代码代码如下所示：
国际hash_lookup（哈希表* HT，char *键，void * *结果）
{
指数= hash_index（HT，关键）；
桶*；

如果（桶= NULL）返回失败；

为了找到正确的元素，查找这个列表，通常这个列表应该只有一个元素，也没有很多次。
循环。为了确保需要有合适的散列算法，请参见前面相关散列函数的链接。
当（桶）
{
如果（StrCmp（斗>键，键）= = 0）
{
log_msg（哈希表发现关键索引：%我关键：%s值：% P
索引、键、桶>值）；
*结果；
返回成功；
}

桶=下一个；
}

log_msg（哈希表查找错过的关键：%s
返回失败；
}

PHP数组是基于哈希表的实现，为了添加元素的数组，元素之间的顺序，和哈希表在物理位置接近平均分配，这是无法插入序列来获得这些元素，在斗结构实现由PHP保持指针到另一个领域保持元素之间的关系，详细阐述了在哈希表在PHP的后段。上面的例子是一个简化版本的PHP中的实现。