存储结构typedefunionTKey{struct{TValuefields;intnext;// 下一个哈希冲突节点的索引}nk;TValue tvk;}TKey;typedefstructNode{TValue i_val;// 值TKey i_key;// 键}Node;存储示例localt{array1,-- 在数组部分索引1array2,-- 在数组部分索引2ahash1,-- 在哈希表部分bhash2,-- 在哈希表部分chash3,-- 在哈希表部分[10]array10,-- 在数组部分索引10}在内存中大致是这样数组部分: [0]:nil [1]:array1 [2]:array2 [3-9]:nil [10]:array10 哈希表部分: 桶1: ahash1 → bhash2 (a和b哈希冲突) 桶2: chash3遍历table的原理遍历字典通常是使用pairs用一段伪代码讲述一下其运行的大概逻辑functionpairs(table)locallast_keynilreturnfunction()-- 获取下一个键localnext_keyfind_next_key(table,last_key)last_keynext_keyreturnnext_key,table[next_key]endend其中find_next_key是其关键本质就是next完成寻找下一个key的工作接下来就详细讲解下next的工作机制next工作机制// 伪代码简化版intluaH_next(Table*t,constTValue*key){if(keyNULL){// 第一次调用从数组部分开始for(inti0;it-sizearray;i){if(!ttisnil(t-array[i])){push_key(i1);// Lua索引从1开始push_value(t-array[i]);return1;}}// 数组部分没有从哈希表第一个非空桶开始returnfind_first_hash_entry(t);}// 不是第一次调用if(ttisinteger(key)){// 键是整数可能在数组部分intidxivalue(key);if(idx1idxt-sizearray){// 继续在数组部分找下一个for(intiidx;it-sizearray;i){if(!ttisnil(t-array[i])){push_key(i1);push_value(t-array[i]);return1;}}}}// 在哈希表部分查找returnfind_next_hash_entry(t,key);}由上面的逻辑我们可以看出其是通过获取上一次查询的键提高遍历的效率不需要每次都从头查找某个只在哪。其中最重要的接口就是find_next_hash_entryfind_next_hash_entrystaticintfind_next_hash_entry(Table*t,constTValue*key){// 1. 找到key的主位置Node*mpluaH_mainposition(t,key);Node*nmp;// 2. 在冲突链中查找这个keywhile(n!NULL!luaV_equalobj(NULL,key,n-i_key.tvk)){ngnext(n);// 沿着next指针找}if(n!NULL){// 3. 找到了key返回冲突链中的下一个节点Node*nextgnext(n);if(next!NULL){push_key_from_node(next);push_value_from_node(next);return1;}}// 4. 没找到key或者key是冲突链的最后一个节点// 从key的主位置的下一个桶开始找intimp-t-node;// 当前桶的索引for(ii1;it-sizemask;i){Node*nodet-node[i];if(!ttisnil(gval(node))){push_key_from_node(node);push_value_from_node(node);return1;}}return0;// 没有更多元素}遍历过程中不要删除元素删除导致漏掉的具体过程localt{}t.x1-- 哈希到桶0t.y2-- 和x冲突在桶0的链表中t.z3-- 哈希到桶1内存结构桶0: [x1] → [y2] 桶1: [z3] 桶2: 空 桶3: 空fork,vinpairs(t)doprint(k,v)ifkxthent[k]nil-- 删除xendend步骤分解第一次调用 next(t, nil)找到第一个非空桶桶0返回桶0的第一个节点x1遍历器记住当前是x第二次调用 next(t, “x”)// 在find_next_hash_entry中// 1. 找到x的主位置桶0// 2. 在桶0的链表中找x// 3. 但是x已经被删除了// 4. 找不到x进入第4步逻辑// 第4步从桶0的下一个桶开始找for(i01;isizemask;i){// 检查桶1找到z3// 返回z3}结果y2 被完全跳过了输出变成了x, zy 消失了为什么找不到被删除的节点当执行 t.x nil时节点的 value 被设为 nil但节点的 key 还在然而在遍历时luaV_equalobj比较的是完整的节点由于 value 是 nil这个节点被认为是空节点在冲突链遍历时空节点会被跳过如果删除的元素较多可能触发哈希表的重建例如以下代码localt{}-- 填充很多元素fori1,1000dot[key..i]iendfork,vinpairs(t)doifv%20thent[k]nil-- 删除可能触发rehash-- 哈希表结构完全改变endend如何正确删除table中的元素functionsafe_pairs(t)localkeys{}forkinpairs(t)dotable.insert(keys,k)endlocali0returnfunction()ii1localkkeys[i]ifkthenreturnk,t[k]endendend