{"id":502,"date":"2021-12-25T10:20:19","date_gmt":"2021-12-25T02:20:19","guid":{"rendered":"https:\/\/www.ccagml.com\/?p=502"},"modified":"2022-07-06T10:21:51","modified_gmt":"2022-07-06T02:21:51","slug":"lua%e4%bb%8emain%e5%bc%80%e5%a7%8b2%e4%b9%8btable%e7%9a%84rehash","status":"publish","type":"post","link":"https:\/\/www.ccagml.com\/?p=502","title":{"rendered":"lua\u4ecemain\u5f00\u59cb2\u4e4btable\u7684rehash"},"content":{"rendered":"

\u5f53table\u63d2\u5165\u65b0\u503c\u800c\u6ca1\u6709\u7a7a\u4f4d\u7684\u65f6\u5019,\u4f1a\u89e6\u53d1rehash<\/h1>\n
static TValue *newkey(gafq_State *L, Table *t, const TValue *key)\n{\n    Node *mp = mainposition(t, key); \/\/ \u83b7\u53d6\u4e3b\u8981\u4f4d\u7f6e\n    if (!ttisnil(gval(mp)) || mp == dummynode)\n    {\n        Node *othern;\n        Node *n = getfreepos(t); \/\/ \u83b7\u53d6\u4e00\u4e2a\u7a7a\u4f4d\u7f6e\n        if (n == NULL)\n        {                               \n            rehash(L, t, key);          \/\/ \u6ca1\u6709\u627e\u5230\u7a7a\u4f4d\u7f6e\u5c31\u91cd\u65b0\u7b97hash\n            return gafqH_set(L, t, key);\n        }\n}\nstatic void rehash(gafq_State *L, Table *t, const TValue *ek)\n{\n    int nasize, na;\n    int nums[MAXBITS + 1]; \/* nums[i] = number of keys between 2^(i-1) and 2^i *\/\n    int i;\n    int totaluse;\n    for (i = 0; i <= MAXBITS; i++)\n        nums[i] = 0;                          \/\/ \u91cd\u7f6e\u6570\u7ec4\u6570\u91cf?\n    nasize = numusearray(t, nums);            \/\/ \u8ba1\u7b97\u6570\u7ec4\u90e8\u5206\u7684key\u7684\u6570\u91cf\n    totaluse = nasize;                        \/\/ \u6240\u6709\u6574\u6570\u7684key\u7684\u6570\u91cf\n    totaluse += numusehash(t, nums, &nasize); \/\/ \u54c8\u5e0c\u8868\u90e8\u5206\u7684key\u6570\u91cf\n    nasize += countint(ek, nums); \/\/ \u65b0\u52a0\u7684key \u4f1a\u4e0d\u4f1a\u52a0\u5230\u6574\u6570\u90e8\u5206\n    totaluse++;\n    na = computesizes(nums, &nasize); \/\/ \u91cd\u65b0\u8ba1\u7b97\u6570\u7ec4\u90e8\u5206\n    \/* resize the table to new computed sizes *\/\n    resize(L, t, nasize, totaluse - na);\n}\n\n\n<\/code><\/pre>\n
1. \u5728rehash\u4e2d\u9996\u5148\u8ba1\u7b97\u6570\u7ec4\u90e8\u5206\u4f7f\u7528\u7684\u6570\u91cf<\/h2>\n
\/\/ \u7edf\u8ba1array\u90e8\u5206\u6570\u91cf\nstatic int numusearray(const Table *t, int *nums)\n{\n    int lg;\n    int cur_max_lg;     \/* 2^lg *\/\n    int all_use_count = 0; \/\/ \u8ba1\u7b97\u4f7f\u7528\u7684\u6570\u5b57\u7c7b\u578b\u7684key\u6570\u91cf\n    int check_array_index = 1;    \/\/ \u904d\u5386\u6240\u6709\u6570\u5b57key\n    for (lg = 0, cur_max_lg = 1; lg <= MAXBITS; lg++, cur_max_lg *= 2)\n    {               \/* for each slice *\/\n        int lc = 0; \/\/ \u6bcf\u4e00\u5c0f\u90e8\u5206\u7684\u4f7f\u7528\u7684\u6570\u5b57\u7684\u6570\u91cf\n        int cur_limit = cur_max_lg;\n        if (cur_limit > t->sizearray)\n        {\n            cur_limit = t->sizearray; \/\/ \u6700\u591a\u76f4\u5230\u5f53\u524d\u6570\u7ec4\u7684\u5927\u5c0f\n            if (check_array_index > cur_limit)\/\/\u68c0\u67e5\u8d85\u8fc7\u4e86\n                break;\n        }\n        \/* count elements in range (2^(lg-1), 2^lg] *\/\n        for (; check_array_index <= cur_limit; check_array_index++)\n        {\n            if (!ttisnil(&t->array[check_array_index - 1]))\n                lc++;\n        }\n        nums[lg] += lc;\n        all_use_count += lc;\n    }\n    return all_use_count;\n}\n<\/code><\/pre>\n
1. \u63a5\u7740\u8ba1\u7b97hash\u90e8\u5206\u4f7f\u7528\u7684\u6570\u91cf<\/h2>\n
\/\/ \u7edf\u8ba1\u54c8\u5e0c\u90e8\u5206\u7684\u6570\u91cf\nstatic int numusehash(const Table *t, int *nums, int *pnasize)\n{\n    int totaluse = 0; \/\/ \u54c8\u5e0c\u90e8\u5206\u4f7f\u7528\u7684\u603b\u91cf\n    int all_use_count = 0;     \/\/ \u4f7f\u7528\u7684\u6570\u91cf\n    int i = sizenode(t);\n    while (i--)\n    {\n        Node *n = &t->node[i];\n        if (!ttisnil(gval(n)))\n        {\n            all_use_count += countint(key2tval(n), nums);\n            totaluse++;\n        }\n    }\n    *pnasize += all_use_count;\n    return totaluse;\n}\n<\/code><\/pre>\n
1. \u8ba1\u7b97\u6570\u7ec4\u90e8\u5206\u7684\u5927\u5c0f<\/h2>\n
static int computesizes(int nums[], int *narray)\n{\n    int i;\n    int twotoi; \/* 2^i *\/\n    int a = 0;  \/* number of elements smaller than 2^i *\/\n    int na = 0; \/* number of elements to go to array part *\/\n    int n = 0;  \/* optimal size for array part *\/\n    for (i = 0, twotoi = 1; twotoi \/ 2 < *narray; i++, twotoi *= 2)\n    {\n        if (nums[i] > 0)\n        {\n            a += nums[i];\n            if (a > twotoi \/ 2)\n            {               \/* more than half elements present? *\/\n                n = twotoi; \/* optimal size (till now) *\/\n                na = a;     \/* all elements smaller than n will go to array part *\/\n            }\n        }\n        if (a == *narray)\n            break; \/* all elements already counted *\/\n    }\n    *narray = n;\n    gafq_assert(*narray \/ 2 <= na && na <= *narray);\n    return na;\n}\n\n<\/code><\/pre>\n
1. \u91cd\u65b0\u8ba1\u7b97resize<\/h2>\n
\/\/ \u91cd\u65b0\u8ba1\u7b97 \u6839\u636e \u5f53\u524d\u6570\u7ec4\u4f7f\u7528\u6570\u91cfnasize \u548c hash\u4f7f\u7528\u6570\u91cfnhsize\nstatic void resize(gafq_State *L, Table *t, int nasize, int nhsize)\n{\n    int i;\n    int oldasize = t->sizearray;\n    int oldhsize = t->lsizenode;\n    Node *nold = t->node;  \/\/ \u65e7\u7684hash\u6570\u91cf\n    if (nasize > oldasize) \/\/ \u9700\u8981\u589e\u52a0\u6570\u7ec4\u90e8\u5206\n        setarrayvector(L, t, nasize);\n    setnodevector(L, t, nhsize); \/\/ \u521b\u5efa\u54c8\u5e0c\u4f4d\u7f6e\n    if (nasize < oldasize) \/\/ \u6570\u7ec4\u90e8\u5206\u53d8\u5c11\u4e86\n    {\n        t->sizearray = nasize;\n        for (i = nasize; i < oldasize; i++)\n        {\n            if (!ttisnil(&t->array[i]))\n                setobjt2t(L, gafqH_setnum(L, t, i + 1), &t->array[i]);\n        }\n        \/\/ \u51cf\u5c11array\n        gafqM_reallocvector(L, t->array, oldasize, nasize, TValue);\n    }\n\n   \/\/ \u91cd\u65b0\u63d2\u5165\u54c8\u5e0c\u90e8\u5206\n    for (i = twoto(oldhsize) - 1; i >= 0; i--)\n    {\n        Node *old = nold + i;\n        if (!ttisnil(gval(old)))\n            setobjt2t(L, gafqH_set(L, t, key2tval(old)), gval(old));\n    }\n    if (nold != dummynode)\n        gafqM_freearray(L, nold, twoto(oldhsize), Node); \/* free old array *\/\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u5f53table\u63d2\u5165\u65b0\u503c\u800c\u6ca1\u6709\u7a7a\u4f4d\u7684\u65f6\u5019,\u4f1a\u89e6\u53d1rehash static TValue *newkey(gafqContinue reading lua\u4ecemain\u5f00\u59cb2\u4e4btable\u7684rehash<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[32],"tags":[],"_links":{"self":[{"href":"https:\/\/www.ccagml.com\/index.php?rest_route=\/wp\/v2\/posts\/502"}],"collection":[{"href":"https:\/\/www.ccagml.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ccagml.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ccagml.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ccagml.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=502"}],"version-history":[{"count":1,"href":"https:\/\/www.ccagml.com\/index.php?rest_route=\/wp\/v2\/posts\/502\/revisions"}],"predecessor-version":[{"id":503,"href":"https:\/\/www.ccagml.com\/index.php?rest_route=\/wp\/v2\/posts\/502\/revisions\/503"}],"wp:attachment":[{"href":"https:\/\/www.ccagml.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=502"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ccagml.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=502"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ccagml.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=502"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}