<acronym id="xonnx"></acronym>
      <td id="xonnx"></td>
    1. <pre id="xonnx"></pre>

      1. 專注電子技術學習與研究
        當前位置:單片機教程網 >> MCU設計實例 >> 瀏覽文章

        散列的C語言實現

        作者:huqin   來源:本站原創   點擊數:  更新時間:2014年03月13日   【字體:

        散列是數組存儲方式的一種發展,相比數組,散列的數據訪問速度要高于數組,因為可以依據存儲數據的部分內容找到數據在數組中的存儲位置,進而能夠快速實現數據的訪問,理想的散列訪問速度是非常迅速的,而不像在數組中的遍歷過程,采用存儲數組中內容的部分元素作為映射函數的輸入,映射函數的輸出就是存儲數據的位置,這樣的訪問速度就省去了遍歷數組的實現,因此時間復雜度可以認為為O(1),而數組遍歷的時間復雜度為O(n)。

         
         

        散列是能一種快速實現訪問的存儲方式。通常作為檢索部分的數據項是整形或者字符串,當是字符串時,字符串的數量要遠遠大于數組的長度,這時候就會有多個字符串映射到一個存儲位置的情況,這就是所謂的沖突問題,而且沖突時肯定存在的,這時候如何實現數據的存儲又是需要解決的。

        目前主要的解決方式有兩大類,第一種采用鏈表的形式,將所有沖突的數據項采用鏈表的形式鏈接起來,這樣搜索數據的復雜度就包含了鏈表的遍歷問題,特別是當所有的項都鏈接到一個鏈表下時,這時候實際上就是遍歷鏈表,復雜度并不一定有很大的進步,但是這種鏈表鏈接的方式有很高的填充率。第二種就是充分利用沒有實現的存儲空間,利用探測法探測空閑的空間,進而實現數據的存儲,目前有三種探測方式:線性探測法、平方探測法,以及雙散列法,三種方式中平方探測法運用比較多,但是都存在各種各樣的優缺點,這時候的散列搜索優勢就沒有理想情況下那么明顯。有時候甚至比遍歷數組更加的慢。但是確實不失為一種處理方式。


         

        映射函數可選擇的比較多,其實完全可以定義自己的映射函數,但是有時候為了降低沖突的概率設置了一些比較好的映射函數,比如求和取余,或者乘以一定的系數再求和取余等。

         

        本文采用平方探測法解決了沖突問題,具體的實現如下所示:

        1、結構體定義

            #ifndef __HASHMAP_H_H_
            #define __HASHMAP_H_H_

            #include "list.h"

            #define TABSIZE    101

            /*狀態變量*/
            typedef enum STATE{EMPTY = 0, ACTIVE = 1, DELETED = 2} State;

            /*鍵值結構體*/
            typedef struct _pair
            {
                char *key;
                char *value;
            }Pair_t, *Pair_handle_t;

            /*每一個實際的存儲對象*/
            typedef struct _hashEntry
            {
                Pair_handle_t pair;
                State state;
            }HashEntry_t, *HashEntry_handle_t;

            /*哈希表結構體,便于創建*/
            typedef struct _hashmap
            {
                HashEntry_t *map;
                /*存儲實際的存儲量*/
                int size;
                /*容量*/
                int capacity;
            }Hashmap_t, *Hashmap_handle_t;

            /*隱射函數類型定義*/
            typedef int(*hashfunc)(const char *, int);

            #ifdef __cplusplus
            extern "C"
            {
            #endif

            bool alloc_hashmap(Hashmap_handle_t *hashmap, int capacity);
            bool init_hashmap(Hashmap_handle_t hashmap, int capacity);
            bool insert_hashnode(Hashmap_handle_t hashmap, const char *key, const char *value);
            Pair_handle_t search_hashnode(Hashmap_handle_t hashmap, const char *key);
            char *GetValue(Hashmap_handle_t hashmap, const char *key);
            bool delete_hashnode(Hashmap_handle_t hashmap, const char *key);
            int Length(Hashmap_handle_t hashmap);
            int Capacity(Hashmap_handle_t hashmap);
            void delete_hashmap(Hashmap_handle_t hashmap);
            void free_hashmap(Hashmap_handle_t *hashmap);
            char *key_pair(Pair_handle_t pair);
            char *value_pair(Pair_handle_t pair);
            Hashmap_handle_t copy_hashmap(Hashmap_handle_t hashmap);
            bool resize(Hashmap_handle_t hashmap);

            #ifdef __cplusplus
            }
            #endif
            #endif

        實現表的分配和創建,采用了動態分配的方式實現,這樣可能在性能上比不上靜態數據,但是為了實現數組大小的調整,我選擇了動態分配的實現方式。

            /*分配一個新的對象,可以實現自動分配*/
            bool alloc_hashmap(Hashmap_handle_t *hashmap, int capacity)
            {
                HashEntry_handle_t temp = NULL;
                Hashmap_t * map = NULL;

                if(*hashmap == NULL)
                {
                    /*分配一個散列對象*/
                    map = (Hashmap_handle_t)malloc(sizeof(Hashmap_t));
                    if(map == NULL)
                        return false;
                    /*指針指向當前對象*/
                    *hashmap = map;
                    map = NULL;

                    /*分配一個數組空間,大小可以控制*/
                    temp = (HashEntry_handle_t)malloc(
                        sizeof(HashEntry_t)*capacity);
                    if(temp != NULL)
                    {
                        /*散列對象的指針指向數組*/
                        (*hashmap)->map = temp;
                        temp = NULL;
                        /*設置參數*/
                        (*hashmap)->capacity = capacity;
                        (*hashmap)->size = 0;
                        /*初始化分配的數組空間*/
                        Tabinital((*hashmap)->map,capacity);
                        return true;
                    }
                }
                return false;
            }

            /*初始化一個新的對象,這個對象已經創建,只是沒有初始化而已*/
            bool init_hashmap(Hashmap_handle_t hashmap, int capacity)
            {
                HashEntry_handle_t temp = NULL;
               
                if(hashmap != NULL)
                {
                    /*分配數組空間*/
                    temp = (HashEntry_handle_t)malloc(
                            sizeof(HashEntry_t)*capacity);
                    if(temp != NULL)
                    {
                        /*完成對象的填充操作*/
                        hashmap->map = temp;
                        temp = NULL;
                        hashmap->capacity = capacity;
                        hashmap->size = 0;
                        /*初始化數組對象*/
                        Tabinital(hashmap->map,capacity);
                        return true;
                    }
                }
                return false;
            }

        關于數組中對象的創建,和釋放操作,如下所示:

            /*分配一個pair對象*/
            static bool make_pair(Pair_handle_t *pair, const char *key, const char *value)
            {
                Pair_handle_t newpair =(Pair_handle_t)malloc(sizeof(Pair_t));
                char *newstr = NULL;

                if(newpair == NULL)
                    return false;
               
                newstr = (char *)malloc(strlen(key) + 1);
                if(newstr == NULL)
                    return false;

                strcpy(newstr, key);
                newstr[strlen(key)] = '\0';
                newpair->key = newstr;
                newstr = NULL;

                newstr = (char *)malloc(strlen(value) + 1);
                if(newstr == NULL)
                    return false;

                strcpy(newstr, value);
                newstr[strlen(value)] = '\0';
                newpair->value = newstr;
                newstr = NULL;
               
                (*pair) = newpair;
                return true;
            }

            /*釋放一個對象pair*/
            static void delete_pair(Pair_handle_t *pair)
            {
                Pair_handle_t temp = NULL;
                if(*pair == NULL)
                    return ;

                temp = *pair;
                free(temp->key);
                temp->key = NULL;
                free(temp->value);
                temp->value = NULL;

                free(temp);
                temp = NULL;
                *pair = NULL;
            }

        數組元素的基本操作:

            /*完成數組對象的初始化操作*/
            static void Tabinital(HashEntry_t *tab, int size)
            {
                int i = 0;
                for(; i < size; ++ i)
                {
                    tab[i].pair = NULL;
                    tab[i].state = EMPTY;
                }   
            }

            static void delete_array(HashEntry_handle_t *array, int size)
            {
                int i = 0;

                if(*array != NULL)
                {
                    for(i = 0; i < size; ++ i)
                    {
                        if((*array)[i].state == ACTIVE)
                        {
                            delete_pair(&((*array)[i].pair));
                            (*array)[i].state = DELETED;
                        }
                    }
                    free(*array);
                    *array = NULL;
                }
            }

        插入元素的操作、有兩個函數的創建,其中一個為了便于后期大小的調整操作。

            /*插入數據到散列中,采用了二次探測的實現方式,并設置了退出條件*/
            static bool insert_data(Hashmap_handle_t hashmap,
                const char *key, const char *value, hashfunc func)
            {
                int hashval = func(key,hashmap->capacity);
                int index = 0;
                char * newstr = NULL;

                Pair_handle_t newpair = NULL;

                while(hashmap->map[hashval].state != EMPTY)
                {
                    if((hashmap->map[hashval].state == ACTIVE)
                    && (strcmp(hashmap->map[hashval].pair->key,key) == 0))
                        break;

                    index ++;
                    hashval += index * index;
                    hashval %= hashmap->capacity;
                    if(index == 200)
                        break;
                }
               
                if(hashmap->map[hashval].state == EMPTY)
                {
                    if(make_pair(&newpair,key,value))
                    {
                        hashmap->map[hashval].state = ACTIVE;
                        hashmap->map[hashval].pair = newpair;
                        newpair = NULL;
                        hashmap->size ++;
                        return true;
                    }
                }

                else if((hashmap->map[hashval].state == ACTIVE)
                    && (strcmp(hashmap->map[hashval].pair->key, key) == 0))
                {
                    newstr = (char *)malloc(strlen(value) + 1);
                    if(newstr != NULL)
                    {
                        strcpy(newstr,value);
                        newstr[strlen(value)] = '\0';
                        free(hashmap->map[hashval].pair->value);
                        hashmap->map[hashval].pair->value = newstr;
                        newstr = NULL;

                        return true;
                    }
                }
                return false;
            }

            static bool insert2map(HashEntry_handle_t map,
                const char *key, const char *value,
                hashfunc func, int size)
            {
                int hashval = func(key,size);
                int index = 0;
                char *newstr = NULL;
                Pair_handle_t newpair = NULL;

                if(map != NULL)
                {
                    while(map[hashval].state != EMPTY)
                    {
                        if((map[hashval].state == ACTIVE)
                        && (strcmp(map[hashval].pair->key, key) == 0))
                            break;
                       
                        index ++;
                        hashval += index * index;
                        hashval %= size;
                        /*防止死循環*/
                        if(index == 200)
                            break;
                    }
                   
                    if(map[hashval].state == EMPTY)
                    {
                        if(!make_pair(&newpair,key,value))
                            return false;
                        map[hashval].pair = newpair;
                        map[hashval].state = ACTIVE;
                        newpair = NULL;
                        return true;
                    }
                    else if((map[hashval].state == ACTIVE) &&
                        (strcmp(map[hashval].pair->key, key) == 0))
                    {
                        newstr = (char *)malloc(strlen(value) +1);
                        if(newstr != NULL)
                        {
                            free(map[hashval].pair->value);
                            map[hashval].pair->value = NULL;
                            strcpy(newstr, value);
                            newstr[strlen(value)] = '\0';
                            map[hashval].pair->value = newstr;
                            return true;
                        }
                    }           
                }
                return false;
            }

        調整大小和插入的實際操作。

         

            bool resize(Hashmap_handle_t hashmap)
            {
                int i = 0;
                HashEntry_handle_t newarray = NULL;   

                int size = next_prime(2*hashmap->capacity);

                if(hashmap != NULL)
                {
                    newarray = (HashEntry_handle_t)malloc(sizeof(HashEntry_t)
                                *size);
                    if(newarray == NULL)
                        return false;

                    /*這一步至關重要*/
                    Tabinital(newarray, size);
                    for(; i < hashmap->capacity ; ++ i)
                    {
                        if(hashmap->map[i].state == ACTIVE)
                        {
                            if(!insert2map(newarray,
                                hashmap->map[i].pair->key,
                                hashmap->map[i].pair->value,
                                HashFunc, size))
                                return false;
                        }
                    }
                    delete_array(&hashmap->map,hashmap->capacity);
                    hashmap->map = newarray;
                    hashmap->capacity = size;
                    return true;
                }

                return false;
            }

            bool insert_hashnode(Hashmap_handle_t hashmap,
                const char *key, const char *value)
            {
                if(hashmap->size < hashmap->capacity)
                {
                    if(insert_data(hashmap,key,value,HashFunc))
                    {
                        //hashmap->size ++;
                    }
               
                    return true;
                }
                else /*增加容量*/
                {
                    if(!resize(hashmap))
                        return false;

                    if(insert_data(hashmap,key,value,HashFunc))
                    {
                        //hashmap->size ++;
                    }
                    return true;
                }
                return false;
            }

        搜索操作

            static Pair_handle_t search_data(Hashmap_handle_t hashmap, const char *key, hashfunc func)
            {
                int hashval = func(key, hashmap->capacity);
                int index = 0;
               
                while(hashmap->map[hashval].state != EMPTY)
                {
                    if((hashmap->map[hashval].state == ACTIVE)
                    && (strcmp(hashmap->map[hashval].pair->key,key) == 0))
                        break;

                    index ++;
                    hashval += index * index;
                    hashval %= hashmap->capacity;
                    if(index == 200)
                        break;
                }

                if((hashmap->map[hashval].state == ACTIVE)
                    && (strcmp(hashmap->map[hashval].pair->key, key) == 0))
                {
                    return hashmap->map[hashval].pair;
                }
               
                return NULL;
            }

            Pair_handle_t search_hashnode(Hashmap_handle_t hashmap, const char * key)
            {
                return search_data(hashmap,key,HashFunc);
            }

        刪除操作

         

            static bool delete_node(Hashmap_handle_t hashmap,const char *key,hashfunc func)
            {
                int hashval = func(key, hashmap->capacity);
                int index = 0;
               
                /**********************************************
                  *退出循環的條件是找到空閑的單元,或者關鍵字匹配
                 *********************************************/
                while(hashmap->map[hashval].state != EMPTY)
                {
                    if((hashmap->map[hashval].state == ACTIVE)
                    && strcmp(hashmap->map[hashval].pair->key,key) == 0)
                        break;

                    index ++;
                    hashval += index * index;
                    hashval %= hashmap->capacity;
               
                    if(index == 200)
                        break;
                }

                /*判斷刪除條件*/
                if((hashmap->map[hashval].state == ACTIVE) &&
                    (strcmp(hashmap->map[hashval].pair->key, key) == 0))
                {
                    hashmap->map[hashval].state = DELETED;
                    delete_pair(&(hashmap->map[hashval].pair));
                    hashmap->map[hashval].pair = NULL;   
                   
                    return true;
                }

                return false;
            }

            bool delete_hashnode(Hashmap_handle_t hashmap, const char *key)
            {
                if(delete_node(hashmap, key, HashFunc))
                {
                    hashmap->size --;
                    return true;
                }

                return false;
            }

        參數獲取函數;

            int Length(Hashmap_t *map)
            {

                return map->size;
            }

            int Capacity(Hashmap_t *map)
            {
                return map->capacity;
            }

            void delete_hashmap(Hashmap_handle_t hashmap)
            {   
                int i = 0;
                int size = hashmap->capacity;

                if(hashmap != NULL)
                {
                    for(; i < size; ++ i)   
                    {
                        if(hashmap->map[i].state == ACTIVE)
                        {
                            delete_pair(&(hashmap->map[i].pair));
                            hashmap->map[i].state = DELETED;
                            hashmap->map[i].pair = NULL;
                            hashmap->size --;
                        }
                    }
                    free(hashmap->map);
                    hashmap->map = NULL;
                }
            }

            void free_hashmap(Hashmap_handle_t *hashmap)
            {
                delete_hashmap(*hashmap);
                free(*hashmap);
                *hashmap = NULL;
            }

            char *key_pair(Pair_handle_t pair)
            {
                if(pair != NULL)
                {
                    return pair->key;
                }
                return NULL;
            }

            char *value_pair(Pair_handle_t pair)
            {
                if(pair != NULL)
                {
                    return pair->value;
                }
                return NULL;
            }

            /*復制散列操作,相當于創建了一個新的散列對象,而不是指針復制*/
            Hashmap_handle_t copy_hashmap(Hashmap_handle_t hashmap)
            {
                Hashmap_handle_t newhashmap = NULL;
                int i = 0;
                if(hashmap == NULL)
                    return NULL;
               
                /*采用動態分配的方式實現*/
                if(!alloc_hashmap(&newhashmap,hashmap->capacity))
                    return NULL;
               
                for(; i < hashmap->capacity ; ++ i)
                {
                    if(hashmap->map[i].state == ACTIVE)
                    {
                        /*得到當前中的值實現插入操作*/
                        insert_hashnode(newhashmap,
                            hashmap->map[i].pair->key,
                            hashmap->map[i].pair->value);
                    }
                    else if(hashmap->map[i].state == DELETED)
                    {
                        newhashmap->map[i].state = DELETED;
                    }
                }

                return newhashmap;
            }


        測試函數:

            #include "hashmap.h"
            #include <time.h>

            #define CAPACITY    13

            char *keys[] = {
            "abcd",
            "defh",
            "abcd",
            "12345",
            "a1b2c3",
            "12345",
            "a1b2c3",
            "23456",
            "hijhk",
            "test1",
            "test1",
            "789123",
            "Input",
            };

            char *values[] = {
            "abcd",
            "defh",
            "abcd",
            "12345",
            "a1b2c3",
            "12345",
            "a1b2c3",
            "23456",
            "hijhk",
            "test1",
            "test1",
            "789123",
            "Input",
            };

            int myhashFunc(const char *key, int Tabsize)
            {
                    int hashVal = 0;
                    int i = 0;

                    int len = strlen(key);
                    for(; i < len ; ++ i )
                            hashVal += 37 *hashVal + key[i];
               
                    hashVal %= Tabsize;

                    if(hashVal < 0)
                            hashVal += Tabsize;

                    return hashVal;
            }
             

            int main()
            {
                int i = 0;
                char str1[13];
                char str2[13];

                Hashmap_t mymap ;
                Hashmap_handle_t map = NULL;
                Hashmap_handle_t doubmap = NULL;
               
                Pair_handle_t pair;
                /*靜態分配*/
                srand((int)time(0));

                printf("init and alloc test:\n");
                if(!init_hashmap(&mymap,13))
                {
                    return false;
                }

                /*動態分配*/
                if(!alloc_hashmap(&map,13))
                {
                    return false;
                }   
                printf("Sucessed!\n");
                /*插入測試*/
                printf("insert test:\n");
                for(i = 0; i < CAPACITY + 10; ++ i)
                {
                    sprintf(str1,"%d%d",rand()%10+1,rand()%10+1);
                    sprintf(str2,"%d%d",rand()%10+1,rand()%10+1);
                   
                    printf("%s->-f(%s)->%d->%s\n",str1,str1,
                        myhashFunc(str1,CAPACITY),str2);

                //    sprintf(str1,"%s",keys[i]);
                //    sprintf(str2,"%s",values[i]);
                    if(!insert_hashnode(&mymap,str1,str2))
                    {
                        printf("i = %d, insert to mymap failed\n", i);
                        break;
                    }
                    if(!insert_hashnode(map,str1,str2))
                    {
                        printf("i = %d, insert to map failed\n", i);
                        break;
                    }
                }   
                printf("Sucessed!\n");
                /*查找測試*/
                printf("search test:\n");
                if((pair = search_hashnode(&mymap,str1)) != NULL)
                {
                    printf("%s->%s\n",key_pair(pair),value_pair(pair));
                }
                if((pair = search_hashnode(map,str1)) != NULL)
                {
                    printf("%s->%s\n",key_pair(pair),value_pair(pair));
                }
                printf("Sucessed!\n");
               
                /*delete*/
                printf("delete test:\n");
                if(delete_hashnode(&mymap,str1))
                {
                    printf("Deleted success!!\n");
                }
                else
                {
                    printf("Sorry, Failed!!\n");
                }
                if(delete_hashnode(map,str1))
                {
                    printf("Deleted success!!\n");
                }
                else
                {
                    printf("Sorry, Failed!!\n");
                }
               
                printf("Valid length : %d, Capacity : %d\n",
                    Length(&mymap),Capacity(&mymap));
                printf("Valid length : %d, Capacity : %d\n",
                    Length(map),Capacity(map));
               
                /*改變長度*/
                printf("resize test:\n");
                if(resize(&mymap))
                    printf("Sucessed!\n");
                if(resize(map))   
                    printf("Sucessed!\n");

                /*長度*/
                printf("Valid length : %d, Capacity : %d\n",
                    Length(&mymap),Capacity(&mymap));
                printf("Valid length : %d, Capacity : %d\n",
                    Length(map),Capacity(map));

                printf("Valid length : %d, Capacity : %d\n",
                    Length(&mymap),Capacity(&mymap));
                printf("Valid length : %d, Capacity : %d\n",
                    Length(map),Capacity(map));
               
                printf("copy test:\n");
                doubmap = copy_hashmap(&mymap);
                printf("Valid length : %d, Capacity : %d\n",
                    Length(doubmap),Capacity(doubmap));
                printf("Sucessed!\n");
               
                /*釋放內存*/
                printf("free test:\n");
                delete_hashmap(&mymap);
                free_hashmap(&map);
                free_hashmap(&doubmap);
                printf("Valid length : %d, Capacity : %d\n",
                    Length(&mymap),Capacity(&mymap));
                printf("Sucessed!\n");
               
                return 0;
            }

        測試結果:

            [gong@Gong-Computer newversion]$ ./main
            init and alloc test:

            insert test:
            48->-f(48)->4->49
            108->-f(108)->5->910
            78->-f(78)->1->98
            87->-f(87)->12->73
            36->-f(36)->3->109
            59->-f(59)->4->98
            32->-f(32)->12->48
            210->-f(210)->10->91
            105->-f(105)->2->22
            41->-f(41)->10->82
            1010->-f(1010)->11->69
            19->-f(19)->8->64
            25->-f(25)->3->45
            28->-f(28)->6->104
            16->-f(16)->5->83
            44->-f(44)->0->86
            85->-f(85)->10->72
            51->-f(51)->9->27
            54->-f(54)->12->57
            107->-f(107)->4->210
            73->-f(73)->9->27
            1010->-f(1010)->11->61
            63->-f(63)->10->63

            search test:
            63->63
            63->63

            delete test:
            Deleted
            Deleted
            Valid length : 21, Capacity : 29
            Valid length : 21, Capacity : 29
            resize test:


            Valid length : 21, Capacity : 59
            Valid length : 21, Capacity : 59
            Valid length : 21, Capacity : 59
            Valid length : 21, Capacity : 59
            copy test:
            Valid length : 21, Capacity : 59

            free test:
            Valid length : 0, Capacity : 59

        從實驗效果可知,基本上實現了散列的基本操作。

        關閉窗口

        相關文章

        欧美性色欧美精品视频,99热这里只有精品mp4,日韩高清亚洲日韩精品一区二区,2020国自产拍精品高潮