[哈希表] 290. 单词规律（哈希表实现双向映射：containsValue、两个哈希表、借助中转数字字符串）
290. 单词规律
题目分析
思路1：一个哈希表 + containsValue函数
实现遇到的问题：特殊用例
思路2：两个哈希表记录双向映射关系（推荐）
思路3：一个哈希表 + 字母、单词都转换成数字（推荐）
思路4：两个哈希表 + 字母、单词都转换成数字（对思路3的改进，推荐）

290. 单词规律
题目链接：https://leetcode-cn.com/problems/word-pattern/

分类：

哈希表，记录字母 ↔ 单词的双向映射关系的方法：

一个哈希表记录单向映射 + containsValue函数（思路1）；
两个哈希表分别记录字母→单词、单词→字母的映射关系（思路2）；
两个哈希表记录单词→数字，字母→数字，比较数字是否相等（借助中转数字字符串，思路3、思路4）





题目分析
题目要求的完全匹配，就是pattern的字母 → str的单词和str的单词 → pattern的字母这两个方向都要有且只有一个映射。
也就是说，pattern的一种字母只能唯一对应str的一种单词，同时str的一种单词也只能对应pattern的一种字母。
如果只使用一个map记录字母→单词的映射关系，则字母作为key，只能保证key不重复，value中的单词可能出现重复。
例如：
pattern="abba" s="dog dog dog dog"
pattern[0]='a',s[0]=dog，所以map={a-dog}
pattern[0]='b',s[0]=dog，因为map中的key不包含b，所以继续存入map={a-dog,b-dog}
最后会输出true，但实际是false，原因就在于一个map只维护了一个方向的映射关系，无法保证value的唯一性。

所以我们要在此基础上增加从单词 → 字母的映射关系：

思路1：使用map的containsValue函数；
思路2：使用两个哈希表分别记录字母→单词、单词→字母的映射关系;
思路3：使用一个哈希表 + 字母、单词都转换成数字；
思路4：思路3的改进，利用两个哈希表 + 字母、单词边转换成数字边比较.

思路1：一个哈希表 + containsValue函数
哈希表保存pattern每个字母 → str每个单词的映射关系：key=pattern字母，value=单词；
为了实现单词→字母的映射，对于每个单词，如果与之对应的字母在map中不存在，我们还需要进一步判断map中是否包含该单词，如果包含该单词，但当前字母又不存在，则说明单词→字母的映射和字母→单词的映射相矛盾，返回false。
实现遇到的问题：特殊用例
pattern = "aaa"  s = "aa aa aa aa"

字母个数 != 单词个数，直接返回false。
实现代码：
class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character, String> map = new HashMap<>();
        String[] words = s.split(" ");
        //特殊用例：如果字母数量和单词数量不相等，则直接返回false
        if(pattern.length() != words.length) return false;
        for(int i = 0; i < words.length; i++){
            char ch = pattern.charAt(i);
            if(!map.containsKey(ch)){
            	//如果包含该单词，但当前字母又不存在，返回false
                if(map.containsValue(words[i])) return false;
                map.put(ch, words[i]);
            }
            else{
                if(!map.get(ch).equals(words[i])) return false;
            }
        }
        return true;
    } 
}


存在的问题：代码可以AC，但调用containsValue会导致时间复杂度增加。

思路2：两个哈希表记录双向映射关系（推荐）
设置两个哈希表，分别存放pattern每个字母 → str每个单词的映射关系和str每个单词p → attern每个字母的映射关系。
如果出现不满足其中一个哈希表的映射关系，就返回false。
其中，另一个哈希表可以用HashSet来代替，用set来保存出现过的单词，使用方法和思路1的containsValue类似，只是将思路1中的containsValue替换成set.contains，可以降低时间复杂度。
实现代码：
class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character, String> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        String[] words = s.split(" ");
        //特殊用例：如果字母数量和单词数量不相等，则直接返回false
        if(pattern.length() != words.length) return false;
        for(int i = 0; i < words.length; i++){
            char ch = pattern.charAt(i);
            if(!map.containsKey(ch)){
                if(set.contains(words[i])) return false;
                map.put(ch, words[i]);
                set.add(words[i]);
            }
            else{
                if(!map.get(ch).equals(words[i])) return false;
            }
        }
        return true;
    } 
}

思路3：一个哈希表 + 字母、单词都转换成数字（推荐）
参考题解
将pattern上的每个字母都转换成相应的下标，s上的每个单词也转换成相应的下标，这些数字下标又组成两个字符串，比较这两个字符串是否相等，就能同时解决双向映射关系。
例如：pattern = "abba", str = "dog cat cat fish"
a=0,b=1,b=1,a=0，所以pattern="0110"
dog=0,cat=1,cat=1,fish=3，所以str="0113"
因为两个数字字符串不相等，所以返回false。

字母、单词转数字，采用的数字就是每个字母本身所对应的下标，转换过程同样需要哈希表的帮助，哈希表存放已经转换的键值对（需要两个哈希表分别存放key=ch,value=下标和key=word，value=下标），对于已经转换过的字母或单词，直接从map中获取对应的value，没有转换过的才取下标作为它对应的value写入map中。
最后，拿生成的两个数字字符串做equals比较。
实现代码：
class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        //特殊用例：如果字母数量和单词数量不相等，则直接返回false
        if(pattern.length() != words.length) return false;
        
        //分别生成p和s对应的数字字符串进行比较
        return getNumStr(pattern.split("")).equals(getNumStr(words));
    }
    //输入字符串数组生成对应的数字字符串（参数设置为字符串数组，所以p,s都需要先转换成字符串数组）
    public String getNumStr(String[] strs){
        StringBuilder sb = new StringBuilder();
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < strs.length; i++){
            //已经转换过的字母或单词，直接从map中获取对应的value
            if(map.containsKey(strs[i])){
                int value = map.get(strs[i]);
                sb.append(value);
            }
            //没有转换过的字母或单词，取下标作为它对应的value写入map，加入sb末尾
            else{
                map.put(strs[i], i);
                sb.append(i);
            }
        }
        return sb.toString();
    }
}

思路4：两个哈希表 + 字母、单词都转换成数字（对思路3的改进，推荐）
参考题解
思路3是把两个数字字符串都生成完毕再做比较，但实际上可以在转换过程中边转换边比较每个字母、单词对应的数字是否相等，如果不相等直接返回false。
因此需要两个哈希表，分别存放p和s的数字映射关系。
为了代码能够统一处理，在比较字母、单词转换的数字a,b时，我们对不存在于map中的key，就取默认值-1作为它的value。
实现代码：
class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");

        //特殊用例：如果字母数量和单词数量不相等，则直接返回false
        if(pattern.length() != words.length) return false;
        
        Map<String, Integer> sMap = new HashMap<>();
        Map<Character, Integer> pMap = new HashMap<>();
        for(int i = 0; i < words.length; i++){
        	//如果key不存在map中就取-1
            int sValue = sMap.getOrDefault(words[i], -1);
            int pValue = pMap.getOrDefault(pattern.charAt(i), -1);
            //每转换一个字母和一个单词，就立即比较对应的数字
            if(sValue != pValue) return false;
            else{
                sMap.put(words[i], i);
                pMap.put(pattern.charAt(i), i);
            }
        }
        return true;
    }
}

介绍了符号表的组织形式有线性组织（重插入简洁性，轻索引性能），排序组织（插入操作耗时，重索引性能），哈希表映射（以空间换取时间）。那么如下便介绍了符号表的链表实现方式和哈希表实现方式，分别对应线性组织和哈希表映射两种方式，至于排序组织方式的实现其实只需要一个动态扩展数组便可以实现，较为简单不作讨论。网上关于符号表的实现代码有很多，没有必要重复造轮子，其中个人觉得实现最好的是erhuoxifu博主的两篇文章，代码质量很高，故而在他的代码基础上做一些讨论分析。

 1. 符号表的List链表形式实现 

首先来看下接口函数的设置 list.h


#ifndef _LIST_H_
#define _LIST_H_
/*
*链表实现最大的优点便是动态插入的性能很好，故而显然每个符号表项（这里称为元素项）的具体实现方式
*采用链接节点的形式最好，这样既能实现动态扩展（不盲目扩展空间），又可以很好地实现链表关联
*所以这里分为两层结构，分别定义元素项的节点和管理链表的组织信息头结构体
*/
typedef struct ListNode
{
    char*  key;
    void*  value;
    struct  ListNode* pre;
    struct  ListNode* next; 
} ListNode;

typedef struct List 
{
    struct ListNode*  head_node;
    struct ListNode*  tail_node;
    unsigned long uiNodeLength;
} List;
typedef struct List* pList;

/*
*如果是用C++编译器编译，那么接口函数为了可以被用在C语言中，声明采用C语言的函数修饰规则，
**否则链接过程中可能会找不到正确的函数名
*/
#ifdef __cplusplus  
extern "C" {  
#endif

    pList List_new( void );  

    /*
    *这里需要讨论的问题是，元素项节点结构体中存放着指向符号名key、元素值value的指针，那么在释放时
    *符号名Key的空间释放我们是可以理解的，那么元素值value是否也需要在这里释放呢？
    *思考了一下，觉得还是不应该在List_free中释放具体的元素项的value指针，有两点考虑
    *1.不符合“谁制造，谁负责”的原则，这样容易出现模块之间功能界限模糊
    *2.元素项中存放具体元素值时，因为不知道元素值的类型，而采用通用指针void*，那么显然在不知道元素值类
    *型的情况下，是无法正确释放该元素值所占用的空间的，虽然让用户自己负责自己的值空间的分配和释放确实容易
    *出现忘记释放的情况，但是如果将该工作转移到symbol_list库中来实现，工作量和难度都会增加不少，
    *故而基于以上考虑，放弃在List_free和List_remove中对具体元素项的值空间的释放
    */
    void List_free( pList oList );

    int List_getLength( pList oList );

    /*
    *这里要讨论的是List_put如何遇到要存储元素已经存在，该如何面对，是更新，还是不更新？
    *我们知道在有些用户使用性友好的库中，这种插入操作有时是和replace混用的，但这要求库的设计者对
    *库的使用场景足够熟悉，才能做出这种果断的融合操作的
    *显然出于功能界限尽可能清晰的原则考虑，这里我还是认为不应该出现put插入和replace替换混用
    */
    int List_put( pList oList, const char* pcKey, const void* pvValue );
    /*
    *和上面List_put同样的道理，既然是replace替换，所以就应该是要替换的元素已经存在在List中，
    *不应该增加：如果要替换的元素此前不存在，那么便将该元素项作为新插入项插入List中这种功能组合的设计
    */
    void* List_replace( pList oList, const char* pcKey, const void* pvValue );

    int List_contains( pList oList, const char* pcKey );

    /*
    *出于功能安全的角度考虑，库传出来给用户的值尽可能应该是传值、传bool这类的直接量，而不应该传出
    *元素项指针，链表组织信息（如头结点地址）这类敏感的信息的指针
    *所以这里的List_get应该完成的操作是根据给定的符号名来给出元素项具体值空间，前面又说道了List库
    *是不对具体的元素值空间负责的，所以这里只能传出值空间首地址，让程序上层调用者来负责那些指针安全操作的
    *内容，List库的原则应该是自己产生的指针信息绝对不外泄
    */
    void* List_get( pList oList, const char* pcKey );

    /*参考上面关于List_free的描述*/
    void* List_remove( pList oList, const char* pcKey );

    /*
    *给List链表设计一个类似于lambda函数遍历操作的接口，结合了lambda函数+迭代器的原则，
    *功能目标是在List链表中将所有元素项调用传递的pfApply函数指针指向的函数调用一遍
    */
    void  List_map( pList oList,
                    void (*pfApply)(const char* pcKey, const void* pvValue, void* pvExtra),
                    const void* pvExtra );
#ifdef __cplusplus
}
#endif

#endif  //end of _LIST_H_

来看下具体的链表接口函数实现，我对原代码进行了一点更改，采用双向链表以加速删除这类操作的性能 
list.cpp



#include "list.h"  //“”意味着优先在当前目录下搜索库
#include <stdio.h> //<>意味着按照#include环境变量设置的绝对路径进行搜索
#include <stdlib.h>
#include <assert.h>
#include <string.h>

/* 
* Use calloc to allocate the memory, 
* because it will initialize all memory bits to zero. 
* calloc函数相比于malloc函数最大的不同便是初始化操作，前者带有分配空间全部清空的操作
*/  
static void* MyAlloc ( unsigned long size )  
{  
    void* tmp;  

    tmp = ( void* ) calloc ( size, sizeof ( char ) );  
    assert( tmp );  

    return tmp;  
}  

pList List_new( void )
{
    return (pList)MyAlloc(sizeof(List));
}

void List_free( pList oList )
{
    assert( oList );
    ListNode* temp = oList->head_node;

    while ( temp )
    {
        oList->head_node = oList->head_node->next;

        if ( temp->key )
            free( temp->key );
        //if ( temp->value )  //value的释放不应该由List内部来实现，应该遵循着谁制造，谁负责的逻辑
        //  free( temp->value );
        free( temp );

        temp = oList->head_node;
    }
    free( oList );
    oList = NULL;
}

int List_getLength( pList oList )
{
    return oList->uiNodeLength;
}

/*
*static修饰本函数仅限于本文件list.cpp内部使用，之所以加这一个函数是为了内部其他函数方便获取具体元素
*的指针信息，从而方便操作，但是该函数显然是不能向外部开放的
*/
static ListNode* List_getKey( pList oList, const char* pcKey )
{
    assert( oList );
    assert( pcKey );

    if (strlen(pcKey) == 0)
        return NULL;

    if ( oList->uiNodeLength == 0)
        return NULL;

    ListNode* temp = oList->head_node;
    while (temp)
    {
        if( strcmp( pcKey, temp->key) == 0)
            return temp;
        temp = temp->next;
    }

    return NULL;
}

//插入元素项，如果元素项存在，那就意味着本次插入不成功，返回0，成功返回1  
int List_put( pList oList, const char* pcKey, const void* pvValue )
{
    assert( oList );
    assert( pcKey );
    assert( pvValue);

    if ( strlen( pcKey) == 0)
        return 0;
    if ( List_getKey( oList, pcKey) )
        return 0;

    else
    {
        ListNode* new_node = (ListNode*)MyAlloc( sizeof(ListNode) );
        assert( new_node );

        char* key = (char*)MyAlloc( strlen(pcKey) + 1);
        if (key == NULL)
        {
            free( new_node);
            return 0;
        }

        new_node->key = key;
        strcpy( new_node->key, pcKey );
        new_node->value = (void*)pvValue;

        if (oList->uiNodeLength == 0)
        {
            oList->head_node = new_node;
            oList->tail_node = new_node;
            new_node->pre = NULL;
            new_node->next = NULL;
            oList->uiNodeLength = 1;

            return 1;
        }
        else
        {
            new_node->pre = oList->tail_node;
            new_node->next = NULL;
            oList->tail_node->next = new_node;
            oList->tail_node = new_node;
            oList->uiNodeLength += 1;

            return 1;
        }

    }
}

//根据给定的元素符号名查找该元素是否存在，如果存在返回1，否则返回0
int List_contains( pList oList, const char* pcKey )
{
    assert( oList );
    assert( pcKey );
    if ( List_getKey( oList, pcKey) )
        return 1;
    else
        return 0;
}

//元素替换接口函数的实现，替换的前提是必须列表中存在这样的元素
void* List_replace( pList oList, const char* pcKey, const void* pvValue )
{
    assert( oList );
    assert( pcKey );

    ListNode* tempListNode = List_getKey( oList, pcKey );

    if (tempListNode == NULL)
        return NULL;
    else
    {   
        void* tempP = tempListNode->value;
        tempListNode->value = (void*) pvValue;
        return tempP;
    }
}
//根据具体元素的符号名查找元素项，但是显然不能返回该元素项的指针，而只能返回值空间的首地址，
void* List_get( pList oList, const char* pcKey )
{
    assert( oList );
    assert( pcKey );

    if (strlen(pcKey) == 0)
        return NULL;
    else
    {
        ListNode* temp = List_getKey( oList, pcKey );
        return temp ? temp->value : NULL;
    }
}   

//删除指定符号名的元素项，并返回元素原值
void* List_remove( pList oList, const char* pcKey )
{
    assert( oList );
    assert( pcKey );

    if ( strlen(pcKey) == 0)
        return NULL;
    else
    {
        ListNode* temp = List_getKey( oList, pcKey );
        void* tempValue = NULL;
        if (temp)
        {
            if ((temp != oList->tail_node) && (temp != oList->head_node))
            {
                temp->pre->next = temp->next;
                temp->next->pre = temp->pre;
            }
            else if (temp == oList->head_node )
            {
                if (oList->uiNodeLength == 1)
                {
                    oList->head_node = NULL;
                    oList->tail_node = NULL;
                }
                else
                {
                    oList->head_node = temp->next;
                    temp->next->pre = NULL;
                }
            }
            else //if (temp == oList->tail_node )
            {
                if (oList->uiNodeLength == 1)
                {
                    oList->head_node = NULL;
                    oList->tail_node = NULL;
                }
                else
                {
                    oList->tail_node = temp->pre;
                    temp->pre->next = NULL;
                }
            }

            tempValue = temp->value;

            free(temp->key);
            //free(temp->value);
            free(temp);

            oList->uiNodeLength -= 1;
        }

        return tempValue;
    }
}

void  List_map( pList oList,
                void (*pfApply)(const char* pcKey, const void* pvValue, void* pvExtra),
                const void* pvExtra )
{
    assert( oList );
    assert( pvExtra );
    assert( pfApply );

    ListNode* temp = oList->head_node;
    while (temp)
    {
        assert( temp->key );
        assert( temp->value );
        pfApply( temp->key, temp->value, (void*)pvExtra);
        temp = temp->next;
    }

    return;
}


 2. 符号表的hash-table形式实现 

首先来看下接口函数的设置 hash-table.h




#ifndef _HASH_TABLE_H_
#define _HASH_TABLE_H_
/*建立三级结构，分别是具体元素项、哈希单位置链、符号表，因为符号表机制采用的是诸侯鼎力的机制
*为了因对哈希冲突，本程序实现的是同一哈希key值处用链表串联来解决，而非传统的顺移方案
*/

/*建立hash-table中的元项实现,因为每个元素项的哈希索引值可能存在冲突，所以应该在元素节点中保留
*插入冲突节点的可能性，这便是引入struct ListNode* next的原因
*/
typedef struct ListNode
{
    char* key;
    void* value;
    struct ListNode* next;
}ListNode;

/*声明该链的组织信息*/
typedef struct ListAssociation
{
    struct ListNode*   head_node;
    struct ListNode*   tail_node;
    unsigned long      uiNodeLength; //指明该链长度
}ListAssociation;

typedef struct HashTable
{
    struct ListAssociation**  bucketTable;//子表的索引入口
    unsigned long      uiBindingsCount; //保存该hash-table所有有效子表的数目
    unsigned long      uiBucketCount;   //保存当前哈希表内含的子表数目的上限
} HashTable;

typedef struct  HashTable* HashTable_t;
#ifdef __cplusplus  
extern "C" {  
#endif
    /*初始化哈希表，根据给定的容量设置BucketCount,初始化BucketCount个listAssocation*指针信息*/
    HashTable_t HashTable_new( void );

    void HashTable_free( HashTable_t oHashTable );

    int HashTable_getLength( HashTable_t oHashTable );

    /*
    *往指定哈希表插入新元素，和讨论符号表的List实现时一样，既然是插入新元素，那么如果不是新元素
    *那么显然插入新元素是不存在，即插入新元素和更改元素的功能严格分离
    */
    int HashTable_put ( HashTable_t oHashTable, const char* pcKey, const void* pvValue);

    void* HashTable_get( HashTable_t oHashTable, const char* pcKey );

    /*将哈希表原有的元素项的值替换成新值pvValue，并返回旧值，如果该元素项不存在，则返回NULL*/
    void* HashTable_replace( HashTable_t oHashTable, const char* pcKey, const void* pvValue);

    /*在哈希表中，给定元素的符号名，删除该指定元素项*/
    void* HashTable_remove( HashTable_t oHashTable, cosnt char* pcKey);

    void HashTable_map( 
        HashTable_t oHashTable,
        void (*pfApply)( const char* pcKey, const void* pvValue, void* pvExtra),
        const void* pvExtra );


hash-table.cpp



#include "hash-table.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define ARRAY_SIZE 3

static const unsigned long kBucketCount[ARRAY_SIZE] = {1024, 2048, 666666};
static int giBucketCountIndex = 0;

static void* MyAlloc( unsigned long size );

/*
*给定一个符号表组名称，和当前要查找的元素符号名key --pcKey，因为同样的符号名可能存在哈希冲突，故而应该
*返回的是一个单向链表的表头或链表信息节点
*/
static ListAssociation* HashTable_getListAssociation ( 
    HashTable_t  oHashTable,
    const char* pcKey );

/*给定一个冲突链条，在其中查找具体的元素节点*/
static ListNode* ListAssociation_getListNode (
    const ListAssociation* pListAssociation,
    const char* pcKey );

/*在哈希表中直接查找到具体元素项的首地址，注意static修饰符，该函数是该文件的内部函数，纯粹是为了方便
*其他函数的实现，对外部并不可见，之所以提到最前面给出函数声明，是因为该库要兼容C,所以才会有这些操作
*/
static ListNode* HashTable_getListNode(
    HashTable_t oHashTable,
    const char* pcKey );

/*非覆盖版插入操作，即插入和更新绝对不混用*/
static int ListAssociation_put( ListAssociation* pListAssociation, 
                                const char* pcKey,
                                const void* pvValue );

/*hash-table扩展操作，如果当前哈希表容量不足，则由1024->2048->666666递增，递增成功，则返回1，否则返回0*/
static int Rehash( HashTable_t oHashTable );

static int ListAssociation_put_help_rehash(
    ListAssociation* pListAssociation,
    ListNode*  pListNode );

/*获取当前哈希表的容量所处级别*/
static int GetBucketSizeIndex( unsigned long uiBucketCounts );

/*很简单的hash函数,该步操作返回的哈希映射后的下标*/
int HashTable_hash( const char* pcKey, int iBucketCount )
{
    int i;
    unsigned int uiHash = 0U;
    assert( pcKey != NULL);

    for (i=0; pcKey[i] != '\0'; i++)
    {
        uiHash = uiHash * 66666 + (unsigned int)pcKey[i];
    }

    return (int)( uiHash % (unsigned int)iBucketCount );
}

HashTable_t HashTable_new( void )
{
    HashTable_t temp = (HashTable_t) MyAlloc( sizeof(HashTable) );

    if(temp)
    {
        struct ListAssociation ** pListAssociation = NULL;
        temp->uiBucketCount = kBucketCount[0]; //初始将hash_table初始化为1024个节点
        pListAssociation = (ListAssociation**) MyAlloc(temp->uiBucketCount * sizeof( ListAssociation* ) );

        if (pListAssociation == NULL)
        {
            free(temp);
            return NULL;
        }
        temp->bucketTable = pListAssociation;
    }

    return temp;
}

void HashTable_free( HashTable_t oHashTable )
{
    assert( oHashTable );
    unsigned long uiBucketCount = oHashTable->uiBucketCount;

    //遍历删除子表的内容
    struct ListAssociation* pListAssociation = NULL;
    for (int i = 0; i<uiBucketCount; i++ )
    {
        pListAssociation = oHashTable->bucketTable[i];

        if( NULL == pListAssociation )
            continue;

        ListNode* temp = pListAssociation->head_node;

        while (temp)
        {
            pListAssociation->head_node = pListAssociation->head_node->next;

            if (temp->key)
            {
                free( temp->value );
                free( temp->key );
            }

            free(temp);
        }
        free( pListAssociation);
        pListAssociation = NULL;
    }

    free( oHashTable->bucketTable );
    free( oHashTable );

    oHashTable = NULL;
}

int HashTable_getLength( HashTable_t oHashTable )
{
    return oHashTable->uiBindingsCount;
}

int HashTable_put ( HashTable_t oHashTable, const char* pcKey, const void* pvValue)
{
    assert( oHashTable );
    assert( pcKey );
    assert( pvValue );
    assert( oHashTable->uiBucketCount ); //确保当前哈希表的子表数目不为0

    if (0 == strlen( pcKey) )
        return 0;

    if (oHashTable->uiBucketCount < kBucketCount[ARRAY_SIZE-1] )
    {
        if (oHashTable->uiBindingsCount >= oHashTable->uiBucketCount )
        {
            if( Rehash(ohashTable) == 0)
                return 0;
        }
    }

    ListAssociation* pListAssociation = HashTable_getListAssociation( oHashTable, pcKey );
    if (NULL == pListAssociation )
    {
        pListAssociation = ( ListAssociation* ) MyAlloc( sizeof(ListAssociation) );

        if (pListAssociation == NULL )
            return 0;

        oHashTable->bucketTable[HashTable_hash( pcKey, oHashTable->uiBucketCount)] = pListAssociation;
    }

    if (ListAssociation_put( pListAssociation, pcKey, pvValue) )
    {
        oHashTable->uiBindingsCount = oHashTable->uiBindingsCount + 1;
        return 1;
    }

    return 0;
}

int HashTable_contains( HashTable_t oHashTable, const char* pcKey )
{
    assert( oHashTable );
    assert( pcKey );

    if(HashTable_getListNode( oHashTable, pcKey) )
        return 1;
    else
        return 0;
}

void* HashTable_get( HashTable_t oHashTable, const char* pcKey )
{
    assert( oHashTable );
    assert( pcKey );

    ListNode* pListNode = HashTable_getListNode( oHashTable, pcKey );

    if(pListNode)
        return pListNode->value;

    return NULL;
}

//对哈希表中所有元素进行遍历操作，操作函数为pfApply指定的函数指针
void HashTable_map( 
    HashTable_t oHashTable,
    void (*pfApply)( const char* pcKey, const void* pvValue, void* pvExtra),
    const void* pvExtra )
{
    assert( oHashTable );
    assert( pfApply );
    assert( pvExtra );

    unsigned long uiBucketCount = oHashTable->uiBucketCount;
    int i = 0;

    if ( HashTable_getLength( oHashTable) == 0)
        return;

    for ( i = 0; i< uiBucketCount; i++)
    {
        ListAssociation* pListAssociation = oHashTable->bucketTable[i];
        if (pListAssociation == NULL)
            continue;

        ListNode* pListNode = pListAssociation->head_node;

        while (pListNode)
        {
            assert( pListNode->key);
            assert( pListNode->value);
            pfApply( pListNode->key, pListNode->value, (void*)pvExtra );
            pListNode = pListNode->next;
        }
    }

    return;
}

//将哈希表原有的元素项的值替换成新值pvValue，并返回旧值，如果该元素项不存在，则返回NULL
void* HashTable_replace( HashTable_t oHashTable, const char* pcKey, const void* pvValue)
{
    assert( oHashTable );
    assert( pcKey );

    void* value = NULL;
    ListNode* pListNode = HashTable_getListNode( oHashTable, pcKey);
    if ( pListNode )
    {
        value = pListNode->value;
        pListNode->value = (void*)pvValue;
    }

    return value;
}
//在哈希表中，给定元素的符号名，删除该指定元素项
void* HashTable_remove( HashTable_t oHashTable, cosnt char* pcKey)
{
    assert( oHashTable );
    assert( pcKey );

    ListAssociation* pListAssociation = HashTable_getListAssociation( oHashTable, pcKey);
    if (pListAssociation == NULL)
        return NULL;

    void* value = NULL;
    ListNode* temp = pListAssociation->head_node;
    ListNode* pre_node = NULL;

    //如果哈希后得到位置处没有有效信息，则可以直接返回
    if (temp = NULL)
        return NULL;

    //如果哈希后位置处有信息，则需要遍历该处的具体链表，查找到匹配的”符号名“
    //1. 链表首项就是要查找的元素项，则需要额外处理，因为涉及到pListAssociation->head_node等组织信息的更新
    if( strcmp(pcKey, temp->key) == 0)
    {
        value = temp->value;
        pListAssociation->head_node = temp->next;

        free(temp->value);
        free(temp->key);
        free(temp);

        pListAssociation->uiNodeLength = pListAssociation->uiNodeLength - 1;
        oHashTable->uiBindingsCount = oHashTable->uiBindingsCount - 1;

        return value;
    }

    while (1)
    {
        pre_node = temp;
        temp = temp->next;
        if (temp == NULL)
            return NULL;

        if ( strcmp(pcKey, temp->key) == 0 )
        {
            pre_node->next = temp->next;  //链条串起来不能断
            if ( temp == pListAssociation->tail_node )
                pListAssociation->tail_node = pre_node;

            value = temp->value;

            free( temp->key );
            free( temp->value);
            free( temp );

            pListAssociation->uiNodeLength = pListAssociation->uiNodeLength - 1;
            oHashTable->uiBindingsCount = oHashTable->uiBindingsCount - 1;

            return value;
        }
    }

    return NULL;
}

static void* MyAlloc( unsigned long size )
{
    void* temp = (void*) malloc( size*sizeof(char) );
    assert(temp);

    return temp;
}

//给定元素项的“符号名”,返回哈希后该元素项在哈希表中下表位置
static ListAssociation* HashTable_getListAssociation( HashTable_t oHashTable, const char* pcKey)
{
    assert( oHashTable);
    assert( pcKey);

    if ( strlen(pcKey) == 0)
        return NULL;

    int iHash_key = -1;

    iHash_key = HashTable_hash( pcKey, oHashTable->uiBucketCount );
    assert( iHash_key >= 0);

    return oHashTable->bucketTable[iHash_key];
}

//应对哈希冲突，如果同样的哈希值处存在多个元素项，则采用链表方式组织，故而针对具体的符号名需要二次操作
//1. 将符号名哈希后得到下标位置； 2.在下标位置上遍历链表进一步找到匹配的符号名项
static ListNode* ListAssociation_getListNode( 
    const ListAssociation* pListAssociation, 
    const char* pcKey)
{
    assert( pListAssociation );
    assert( pcKey );

    if (strlen(pcKey) == 0)
        return NULL;

    ListNode* pListNode = pListAssociation->head_node;
    while ( pListNode )
    {
        if ( strcmp( pcKey, pListNode->key ) == 0 )
            return pListNode;
        pListNode = pListNode->next;
    }

    return  NULL;
}

//在具体哈希值链条上插入元素，如果该元素原先存在，则直接返回0；如果不存在则新建项，并插入链表中，并返回1
static int ListAssociation_put(
    ListAssociation* pListAssociation,
    const char* pcKey,
    const void* pvValue )
{
    assert( pListAssociation );
    assert( pcKey );
    assert( pvValue );

    if (ListAssociation_getListNode( pListAssociation, pcKey ))
        return 0;
    else
    {
        ListNode* new_node = (ListNode*)MyAlloc( sizeof(ListNode) );
        assert(new_node);

        char* key = (char*)MyAlloc( strlen( pcKey) + 1);
        if (key == NULL)
        {
            free(new_node);
            return 0;
        }

        new_node->key = key;
        strcpy( new_node->key, pcKey );
        new_node->value = (void*)pvValue; 

        if ( pListAssociation->uiNodeLength == 0)
        {
            pListAssociation->head_node = new_node;
            pListAssociation->tail_node = new_node;
            pListAssociation->uiNodeLength = 1;

            return 1;
        }
        else
        {
            pListAssociation->tail_node->next = new_node;
            pListAssociation->tail_node = new_node;
            pListAssociation->uiNodeLength += 1;

            return 1;
        }
    }
}

static ListNode* HashTable_getListNode( HashTable_t oHashTable, const char* pcKey)
{
    assert( oHashTable );
    assert( pcKey );

    if (strlen(pcKey) == 0)
        return NULL;

    ListAssociation* pListAssociation = NULL;

    if (HashTable_getLength( oHashTable) == 0)
        return NULL;

    pListAssociation = HashTable_getListAssociation( oHashTable, pcKey);

    if (pListAssociation == NULL)
        return NULL;

    return ListAssociation_getListNode( pListAssociation, pcKey);
}

static int Rehash( HashTable_t oHashTable )
{
    assert( oHashTable );
    assert( oHashTable->uiBindingsCount >= oHashTable->uiBucketCount );

    giBucketCountIndex = GetBucketSizeIndex( oHashTable->uiBucketCount );
    assert( giBucketCountIndex >= 0);
    if ((ARRAY_SIZE-1) == giBucketCountIndex )
        return 1;

    giBucketCountIndex++;

    unsigned long uiBucketCounts = kBucketCount[giBucketCountIndex];

    struct ListAssociation** pNewListAssociation = NULL;
    pNewListAssociation = ( ListAssocaition**)MyAlloc( uiBucketCounts * sizeof( ListAssocaition*) );
    if (pNewListAssociation == NULL)
        return 0;

    //将原先哈希表中的内容进行整体搬迁,由于并无时间序上的要求，故而搬迁时对于不同节点的先入先出顺序并无特殊要求
    unsigned long uiOldBucketCount = oHashTable->uiBucketCount;
    unsigned long i = 0;
    for( ; i < uiOldBucketCount; i++ )
    {
        struct ListAssociation* pOldListAssociation = NULL;
        pOldListAssociation = oHashTable->bucketTable[i];

        if ( pOldListAssociation == NULL )
            continue;

        ListNode* pTempListNode = pOldListAssociation->head_node;
        while ( pTempListNode )
        {
            int iHash_key = -1;
            iHash_key = HashTable_hash( pTempListNode->key, uiBucketCounts );
            assert( iHash_key >= 0 );

            ListAssocaition* pListAssociation = pNewListAssociation[iHash_key];
            if ( pListAssociation == NULL)
            {
                pListAssociation = (ListAssocaition*)MyAlloc( sizeof(ListAssocaition) );
                if (pListAssociation == NULL)
                    return 0;

                pNewListAssociation[iHash_key] = pListAssociation;
            }

            pOldListAssociation->head_node = pOldListAssociation->head_node->next;
            if (ListAssociation_put_help_rehash( pListAssociation, pTempListNode )  == 0)
                return 0;

            pTempListNode = pOldListAssociation->head_node;
        }

        free( pOldListAssociation );
        pOldListAssociation = NULL;
    }

    free( oHashTable->bucketTable );

    //将哈希表的新的组织信息更新
    oHashTable->bucketTable = pNewListAssociation;
    oHashTable->uiBucketCount = uiBucketCounts;
    //oHashTable->uiBindingsCount代表当前有效链表数目，不变

    return 1;
}   

//该函数时配合rehash函数的，出于的目的主要是重复利用原有的元素项，而不需要重新分配
static int ListAssociation_put_help_rehash( 
    ListAssocaition* pListAssociation, 
    ListNode* pListNode )
{
    assert( pListAssociation );
    assert( pListNode );
    assert( pListAssociation->uiNodeLength >= 0 );

    //如果该链表已经存在该同符号名元素项，则返回
    if ( ListAssociation_getListNode( pListAssociation, pListNode->key) )
        return 0;
    else
    {
        //如果链表是空，则
        if (pListAssociation->uiNodeLength == 0)
        {
            pListAssociation->head_node = pListNode;
            pListAssociation->tail_node = pListNode;
            pListAssociation->tail_node->next = NULL;
            pListAssociation->uiNodeLength = 1;

            return 1;
        }
        else
        {
            pListAssociation->tail_node->next = pListNode;
            pListAssociation->tail_node = pListNode;
            pListNode->next = NULL;
            pListAssociation->uiNodeLength += 1;

            return 1;
        }
    }
}

static int GetBucketSizeIndex( unsigned long uiBucketCounts )
{
    int i = 0;

    for ( i=0; i < ARRAY_SIZE; i++)
    {
        if (uiBucketCounts == kBucketCount[i])
        {
            giBucketCountIndex = i;
            return giBucketCountIndex;
        }
    }

    return -1;
}

文章目录
哈希表概述
哈希函数的设计
整型
浮点型
字符串
模运算性质
复合类型
哈希冲突的处理
链地址法
开放地址法
其他哈希冲突的处理方法
哈希表的复杂度分析
完整的Java代码

哈希表概述


哈希表充分体现了算法设计领域的经典思想：空间换时间
哈希表是时间和空间之间的平衡
哈希函数的设计很重要
“键”通过哈希函数得到的“索引”分布越均匀越好



  哈希表:均摊复杂度为O(1)，牺牲了其顺序性


哈希函数的设计

  “键”通过哈希函数得到的“索引”分布越均匀越好。

整型
小范围正整型

小范围正整数直接使用
小范围负整数进行偏移   -100 ~ 100  $->$ 0 ~ 200

大范围正整型


  一个简单的解决办法： 模一个素数。


  取一个合适素数，相关素数取法链接。
浮点型

字符串
看成多少进制的整型可以自定义的。

  M：取得模，相应的数组有多大的空间。


模运算性质


 若转化成这样，取模运算的代码实现将比较简易。


复合类型


 转成整型处理 ，并不是唯一的方法，原则如下:

     1. 一致性： 如果a==b, 则hash(a) == hash(b)

    2. 高效性： 计算高效简便

    3. 均匀性： 哈希值均匀分布

哈希冲突的处理
链地址法


 查找表可以是红黑树。当数据量少，冲突比较小时查找表是链表比较好





哈希表是一个动态数组，空间随着N的改变进行自适应，需要resize。

平均每个地址承载的元素多过一定程度，即扩容 ：$N / M >= upperTol$

平均每个地址承载的元素少过一定程度，即缩容 ：$N / M <= lowerTol$

private static final int upperTol = 10;
private static final int lowerTol = 2;
private static final int initCapacity = 7;

// if (size >= upperTol * M)
//    resize(2*M);
// if (size < lowerTol*M && M/2 >= initCapacity)
//    resize(M / 2);

private void resize(int newM) {
    TreeMap<K,V>[] newHashTable = new TreeMap[newM];
    for (int i = 0; i < newM; i++)
        newHashTable[i] = new TreeMap<>();

    int oldM = M;
    this.M = newM;  //hash()函数中将M换成改变了的newM
    for (int i = 0; i < oldM; i++) {
        TreeMap<K, V> map = hashtable[i];
        for(K key: map.keySet())
            newHashTable[hash(key)].put(key, map.get(key));
    }
    this.hashtable = newHashTable;
}

开放地址法


线性探测，  遇到哈希冲突 +1
平方探测，   遇到哈希冲突 +1 +4 +9 +16
二次哈希法，   遇到哈希冲突 +hash(key)


其他哈希冲突的处理方法


再哈希法  Rehashing
Coalesced Hasing ，综合了Seperate Chaining 和 Open Addressing


哈希表的复杂度分析

  回忆动态数组的均摊复杂度分析 ，平均复杂度O(1)

 对于哈希表来说，元素数从N增加到$upperTol * N$；地址空间倍增， 平均复杂度 O(1)

每个操作在O(lowerTol) ~ O(upperTol) -> O(1)


  缩容同扩容原理一样。

扩容 $M -> 2*M$ ,但扩容的 $2*M$ 不是素数，解决方案


private final int[] capacity
        = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
        12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
private int capacityIndex = 0;

public HashTable() {
    this.M = capacity[capacityIndex];
    size = 0;
    hashtable = new TreeMap[M];
    for (int i = 0; i < M; i++) {
        hashtable[i] = new TreeMap<>();
    }
}        

//    if (size >= upperTol * M && capacityIndex+1 < capacity.length) {
//        capacityIndex ++;
//        resize(capacity[capacityIndex]);
//    }
//    if (size < lowerTol*M && capacityIndex-1 >= 0) {
//        capacityIndex --;
//        resize(capacity[capacityIndex]);
//    }



   初始时为链表，当冲突达到一定程度时转为红黑树。
完整的Java代码
import java.util.TreeMap;  //底层就是一个红黑树
public class HashTable<K,V>{

    private final int[] capacity
            = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
            12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};

    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private int capacityIndex = 0;

    private TreeMap<K, V>[] hashtable;
    private int M;    //合适的素数
    private int size;

    public HashTable() {
        this.M = capacity[capacityIndex];
        size = 0;
        hashtable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashtable[i] = new TreeMap<>();
        }
    }


    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }


    public int getSize() {
        return size;
    }

    public void add(K key, V value) {
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key))
            map.put(key,value);
        else {
            map.put(key, value);
            size++;

            if (size >= upperTol * M && capacityIndex+1 < capacity.length) {
                capacityIndex ++;
                resize(capacity[capacityIndex]);
            }
        }
    }

    public V remove(K key) {
        TreeMap<K, V> map = hashtable[hash(key)];
        V ret = null;
        if(map.containsKey(key)) {
            ret = map.remove(key);
            size --;

            if (size < lowerTol*M && capacityIndex-1 >= 0) {
                capacityIndex --;
                resize(capacity[capacityIndex]);
            }

        }
        return ret;
    }


    public void set(K key, V value) {
        TreeMap<K, V> map = hashtable[hash(key)];
        if(!map.containsKey(key))
            throw new IllegalArgumentException(key + "doesn't exist!");
        map.put(key,value);
    }

    public boolean contains(K key) {
        return hashtable[hash(key)].containsKey(key);
    }


    public V get(K key) {
        return hashtable[hash(key)].get(key);
    }

    private void resize(int newM) {
        TreeMap<K,V>[] newHashTable = new TreeMap[newM];
        for (int i = 0; i < newM; i++)
            newHashTable[i] = new TreeMap<>();

        int oldM = M;
        this.M = newM;  //hash()函数中将M换成改变了的newM
        for (int i = 0; i < oldM; i++) {
            TreeMap<K, V> map = hashtable[i];
            for(K key: map.keySet())
                newHashTable[hash(key)].put(key, map.get(key));
        }

        this.hashtable = newHashTable;
    }
}


参考链接：liuyubobobo的github

PHP的哈希实现

PHP内核中的哈希表是十分重要的数据结构，PHP的大部分的语言特性都是基于哈希表实现的， 例如：变量的作用域、函数表、类的属性、方法等，Zend引擎内部的很多数据都是保存在哈希表中的。

数据结构及说明

上一节提到PHP中的哈希表是使用拉链法来解决冲突的，具体点讲就是使用链表来存储哈希到同一个槽位的数据， Zend为了保存数据之间的关系使用了双向列表来链接元素。

哈希表结构

PHP中的哈希表实现在Zend/zend_hash.c中，还是按照上一小节的方式，先看看PHP实现中的数据结构， PHP使用如下两个数据结构来实现哈希表，HashTable结构体用于保存整个哈希表需要的基本信息， 而Bucket结构体用于保存具体的数据内容，如下：
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;

nTableSize字段用于标示哈希表的容量，哈希表的初始容量最小为8。首先看看哈希表的初始化函数:
ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction,
                    dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
    uint i = 3;
    //...
    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }
    // ...
    ht->nTableMask = ht->nTableSize - 1;
 
    /* Uses ecalloc() so that Bucket* == NULL */
    if (persistent) {
        tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
        if (!tmp) {
            return FAILURE;
        }
        ht->arBuckets = tmp;
    } else {
        tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
        if (tmp) {
            ht->arBuckets = tmp;
        }
    }
 
    return SUCCESS;
}

例如如果设置初始大小为10，则上面的算法将会将大小调整为16。也就是始终将大小调整为接近初始大小的 2的整数次方。

为什么会做这样的调整呢？我们先看看HashTable将哈希值映射到槽位的方法，上一小节我们使用了取模的方式来将哈希值 映射到槽位，例如大小为8的哈希表，哈希值为100， 则映射的槽位索引为: 100 % 8 = 4，由于索引通常从0开始， 所以槽位的索引值为3，在PHP中使用如下的方式计算索引：
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;

从上面的_zend_hash_init()函数中可知，ht->nTableMask的大小为ht->nTableSize -1。 这里使用&操作而不是使用取模，这是因为是相对来说取模操作的消耗和按位与的操作大很多。

mask的作用就是将哈希值映射到槽位所能存储的索引范围内。 例如：某个key的索引值是21， 哈希表的大小为8，则mask为7，则求与时的二进制表示为： 10101 & 111 = 101 也就是十进制的5。 因为2的整数次方-1的二进制比较特殊：后面N位的值都是1，这样比较容易能将值进行映射， 如果是普通数字进行了二进制与之后会影响哈希值的结果。那么哈希函数计算的值的平均分布就可能出现影响。


设置好哈希表大小之后就需要为哈希表申请存储数据的空间了，如上面初始化的代码， 根据是否需要持久保存而调用了不同的内存申请方法。如前面PHP生命周期里介绍的,是否需要持久保存体现在：持久内容能在多个请求之间访问，而非持久存储是会在请求结束时释放占用的空间。 具体内容将在内存管理章节中进行介绍。

HashTable中的nNumOfElements字段很好理解，每插入一个元素或者unset删掉元素时会更新这个字段。 这样在进行count()函数统计数组元素个数时就能快速的返回。

nNextFreeElement字段非常有用。先看一段PHP代码：
<?php
$a = array(10 => 'Hello');
$a[] = 'TIPI';
var_dump($a);
 
// ouput
array(2) {
  [10]=>
  string(5) "Hello"
  [11]=>
  string(5) "TIPI"
}

PHP中可以不指定索引值向数组中添加元素，这时将默认使用数字作为索引， 和C语言中的枚举类似， 而这个元素的索引到底是多少就由nNextFreeElement字段决定了。 如果数组中存在了数字key，则会默认使用最新使用的key + 1，例如上例中已经存在了10作为key的元素， 这样新插入的默认索引就为11了。

数据容器：槽位

下面看看保存哈希表数据的槽位数据结构体：
typedef struct bucket {
    ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值
    uint nKeyLength;    // hash关键字的长度，如果数组索引为数字，此值为0
    void *pData;        // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
    void *pDataPtr;     //如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
    struct bucket *pListNext;   // 整个hash表的下一元素
    struct bucket *pListLast;   // 整个哈希表该元素的上一个元素
    struct bucket *pNext;       // 存放在同一个hash Bucket内的下一个元素
    struct bucket *pLast;       // 同一个哈希bucket的上一个元素
    // 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
    char arKey[1];              
} Bucket;

如上面各字段的注释。h字段保存哈希表key哈希后的值。这里保存的哈希值而不是在哈希表中的索引值， 这是因为索引值和哈希表的容量有直接关系，如果哈希表扩容了，那么这些索引还得重新进行哈希在进行索引映射， 这也是一种优化手段。 在PHP中可以使用字符串或者数字作为数组的索引。 数字索引直接就可以作为哈希表的索引，数字也无需进行哈希处理。h字段后面的nKeyLength字段是作为key长度的标示， 如果索引是数字的话，则nKeyLength为0。在PHP数组中如果索引字符串可以被转换成数字也会被转换成数字索引。 所以在PHP中例如'10'，'11'这类的字符索引和数字索引10，
 11没有区别。

上面结构体的最后一个字段用来保存key的字符串，而这个字段却申明为只有一个字符的数组， 其实这里是一种长见的变长结构体，主要的目的是增加灵活性。 以下为哈希表插入新元素时申请空间的代码
p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
if (!p) {
    return FAILURE;
}
memcpy(p->arKey, arKey, nKeyLength);

如代码，申请的空间大小加上了字符串key的长度，然后把key拷贝到新申请的空间里。 在后面比如需要进行hash查找的时候就需要对比key这样就可以通过对比p->arKey和查找的key是否一样来进行数据的 查找。申请空间的大小-1是因为结构体内本身的那个字节还是可以使用的。

在PHP5.4中将这个字段定义成const char* arKey类型了。




Zend引擎哈希表结构和关系




上图来源于网络。
Bucket结构体维护了两个双向链表，pNext和pLast指针分别指向本槽位所在的链表的关系。
而pListNext和pListLast指针指向的则是整个哈希表所有的数据之间的链接关系。 HashTable结构体中的pListHead和pListTail则维护整个哈希表的头元素指针和最后一个元素的指针。

PHP中数组的操作函数非常多，例如：array_shift()和array_pop()函数，分别从数组的头部和尾部弹出元素。 哈希表中保存了头部和尾部指针，这样在执行这些操作时就能在常数时间内找到目标。 PHP中还有一些使用的相对不那么多的数组操作函数：next()，prev()等的循环中， 哈希表的另外一个指针就能发挥作用了：pInternalPointer，这个用于保存当前哈希表内部的指针。 这在循环时就非常有用。


如图中左下角的假设，假设依次插入了Bucket1，Bucket2，Bucket3三个元素：
插入Bucket1时，哈希表为空，经过哈希后定位到索引为1的槽位。此时的1槽位只有一个元素Bucket1。 其中Bucket1的pData或者pDataPtr指向的是Bucket1所存储的数据。此时由于没有链接关系。pNext， pLast，pListNext，pListLast指针均为空。同时在HashTable结构体中也保存了整个哈希表的第一个元素指针， 和最后一个元素指针，此时HashTable的pListHead和pListTail指针均指向Bucket1。
插入Bucket2时，由于Bucket2的key和Bucket1的key出现冲突，此时将Bucket2放在双链表的前面。 由于Bucket2后插入并置于链表的前端，此时Bucket2.pNext指向Bucket1，由于Bucket2后插入。 Bucket1.pListNext指向Bucket2，这时Bucket2就是哈希表的最后一个元素，这是HashTable.pListTail指向Bucket2。
插入Bucket3，该key没有哈希到槽位1，这时Bucket2.pListNext指向Bucket3，因为Bucket3后插入。 同时HashTable.pListTail改为指向Bucket3。

简单来说就是哈希表的Bucket结构维护了哈希表中插入元素的先后顺序，哈希表结构维护了整个哈希表的头和尾。 在操作哈希表的过程中始终保持预算之间的关系。

哈希表的操作接口

和上一节类似，将简单介绍PHP哈希表的操作接口实现。提供了如下几类操作接口：
初始化操作，例如zend_hash_init()函数，用于初始化哈希表接口，分配空间等。
查找，插入，删除和更新操作接口，这是比较常规的操作。
迭代和循环，这类的接口用于循环对哈希表进行操作。
复制，排序，倒置和销毁等操作。

本小节选取其中的插入操作进行介绍。 在PHP中不管是对数组的添加操作（zend_hash_add），还是对数组的更新操作（zend_hash_update）， 其最终都是调用_zend_hash_add_or_update函数完成，这在面向对象编程中相当于两个公有方法和一个公共的私有方法的结构， 以实现一定程度上的代码复用。
 
ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
     //...省略变量初始化和nKeyLength <=0 的异常处理
 
    h = zend_inline_hash_func(arKey, nKeyLength);
    nIndex = h & ht->nTableMask;
 
    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
            if (!memcmp(p->arKey, arKey, nKeyLength)) { //  更新操作
                if (flag & HASH_ADD) {
                    return FAILURE;
                }
                HANDLE_BLOCK_INTERRUPTIONS();
 
                //..省略debug输出
                if (ht->pDestructor) {
                    ht->pDestructor(p->pData);
                }
                UPDATE_DATA(ht, p, pData, nDataSize);
                if (pDest) {
                    *pDest = p->pData;
                }
                HANDLE_UNBLOCK_INTERRUPTIONS();
                return SUCCESS;
            }
        }
        p = p->pNext;
    }
 
    p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
    if (!p) {
        return FAILURE;
    }
    memcpy(p->arKey, arKey, nKeyLength);
    p->nKeyLength = nKeyLength;
    INIT_DATA(ht, p, pData, nDataSize);
    p->h = h;
    CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); //Bucket双向链表操作
    if (pDest) {
        *pDest = p->pData;
    }
 
    HANDLE_BLOCK_INTERRUPTIONS();
    CONNECT_TO_GLOBAL_DLLIST(p, ht);    // 将新的Bucket元素添加到数组的链接表的最后面
    ht->arBuckets[nIndex] = p;
    HANDLE_UNBLOCK_INTERRUPTIONS();
 
    ht->nNumOfElements++;
    ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /*  如果此时数组的容量满了，则对其进行扩容。*/
    return SUCCESS;
}

整个写入或更新的操作流程如下：
生成hash值，通过与nTableMask执行与操作，获取在arBuckets数组中的Bucket。
如果Bucket中已经存在元素，则遍历整个Bucket，查找是否存在相同的key值元素，如果有并且是update调用，则执行update数据操作。
创建新的Bucket元素，初始化数据，并将新元素添加到当前hash值对应的Bucket链表的最前面（CONNECT_TO_BUCKET_DLLIST）。
将新的Bucket元素添加到数组的链接表的最后面（CONNECT_TO_GLOBAL_DLLIST）。
将元素个数加1，如果此时数组的容量满了，则对其进行扩容。这里的判断是依据nNumOfElements和nTableSize的大小。 如果nNumOfElements > nTableSize则会调用zend_hash_do_resize以2X的方式扩容（nTableSize << 1）。