C語言實現通用數據結構之通用映射(HashMap)

Posted on by

本文實例為大傢分享瞭C語言實現通用數據結構之通用映射的具體代碼，供大傢參考，具體內容如下

這是在通用鏈表的基礎上實現的映射，關於鏈表的實現參見：C語言實現通用數據結構之通用鏈表。

註意映射中隻存儲瞭key和value的指針，沒有儲存實際的數據。

對於新的key類型來說，需要自定義HashCode函數和equal函數。

在HashSet的實現中給出瞭幾個常見的hashCode函數和equal函數。參見：c語言實現通用數據結構（四）：通用集合。

頭文件：myHashMap.h

#ifndef MYHASHMAP_H_INCLUDED
#define MYHASHMAP_H_INCLUDED
#include "myList.h"
 
#define DEFAULT_INITIAL_CAPACITY 16
#define DEFAULT_LOAD_FACTOR 0.75f
 
typedef struct entry
{
    void * key;
    void * value;
} Entry;
 
typedef struct myHashMap
{
    int size;   //大小
    int initialCapacity; //初始容量
    float loadFactor;   //加載因子
    int (*hashCode)(void *key);
    int (*equal)(void *key1,void *key2);
    MyList ** entryList;
} MyHashMap;
 
typedef struct myHashMapEntryIterator
{
    int index;       //第幾個鏈表
    MyHashMap *map;
    MyNode *current;
    int count;        //第幾個數據
} MyHashMapEntryIterator;
 
//創建HashMap
MyHashMap *createMyHashMap(int (*hashCode)(void *key),int (*equal)(void *key1,void *key2));
 
//使用全部參數創建HashMap
MyHashMap *createMyHashMapForAll(int initialCapacity,float loadFactor,int (*hashCode)(void *key),int (*equal)(void *key1,void *key2));
 
//釋放HashMap
void freeMyHashMap(MyHashMap * map);
 
//是否包含某個key
int myHashMapContainsKey(MyHashMap *const map,void * const key);
 
//增加一條映射
void myHashMapPutData(MyHashMap *const map,void * const key,void * const value);
 
//通過key得到數據，如果沒有數據則返回null
void* myHashMapGetDataByKey(MyHashMap * const map,void *const key);
 
//數據的容量
int myHashMapGetSize(const MyHashMap * const map);
 
//創建Entry迭代器
MyHashMapEntryIterator* createMyHashMapEntryIterator( MyHashMap *const map);
 
//釋放Entry迭代器
void freeMyHashMapEntryIterator(MyHashMapEntryIterator* iterator);
 
//Entry迭代器是否有下一個
int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator);
 
//遍歷下一個Entry元素
Entry* myHashMapEntryIteratorNext(MyHashMapEntryIterator* iterator);
 
//刪除一條數據，返回是否刪除成功
int myHashMapRemoveDataByKey(MyHashMap *const map,void * const key);
 
//遍歷
void myHashMapOutput(MyHashMap *map, void(*pt)(Entry*));
 
#endif // MYHASHMAP_H_INCLUDED

源文件:  myHashMap.c

#include "myHashMap.h"
#include <stdlib.h>
 
//某條Entry鏈表上是否包含某個key值。
Entry* listContainsEntry(MyList * list, void * key,
  int(*equal)(void *key1, void *key2)) {
 MyListIterator* it = createMyListIterator(list);
 while (myListIteratorHasNext(it)) {
  Entry * entry = (Entry *) (myListIteratorNext(it));
  if (entry->key == key || (equal != NULL && (*equal)(entry->key, key))) {
   return entry;
  }
 }
 freeMyListIterator(it);
 return NULL;
}
 
void rebuildMyHashMap(MyHashMap * map) {
 int newSize = map->initialCapacity * 2;
 MyList **newentryList = (MyList **) malloc(sizeof(MyList*) * newSize);
 for (int i = 0; i < newSize; i++) {
  newentryList[i] = createMyList();
 }
 MyHashMapEntryIterator* it = createMyHashMapEntryIterator(map);
 while (myHashMapEntryIteratorHasNext(it)) {
  Entry * entry = myHashMapEntryIteratorNext(it);
  int hasCode = (*(map->hashCode))(entry->key);
  hasCode %= newSize;
  if (hasCode < 0)
   hasCode += newSize;
  myListInsertDataAtLast(newentryList[hasCode], entry);
 }
 freeMyHashMapEntryIterator(it);
 for (int i = 0; i < map->initialCapacity; i++) {
  freeMyList(map->entryList[i]);
 }
 free(map->entryList);
 map->entryList = newentryList;
 map->initialCapacity = newSize;
}
 
//創建HashMap
MyHashMap *createMyHashMap(int(*hashCode)(void *key),
  int(*equal)(void *key1, void *key2)) {
 MyHashMap *re = (MyHashMap *) malloc(sizeof(MyHashMap));
 re->size = 0;
 re->loadFactor = DEFAULT_LOAD_FACTOR;
 re->initialCapacity = DEFAULT_INITIAL_CAPACITY;
 re->entryList = (MyList **) malloc(sizeof(MyList*) * re->initialCapacity);
 re->hashCode = hashCode;
 re->equal = equal;
 for (int i = 0; i < re->initialCapacity; i++) {
  re->entryList[i] = createMyList();
 }
 return re;
}
 
//使用全部參數創建HashMap
MyHashMap *createMyHashMapForAll(int initialCapacity, float loadFactor,
  int(*hashCode)(void *key), int(*equal)(void *key1, void *key2)) {
 MyHashMap *re = createMyHashMap(hashCode, equal);
 re->initialCapacity = initialCapacity;
 re->loadFactor = loadFactor;
 return re;
}
 
//是否包含某個key
int myHashMapContainsKey(MyHashMap * const map, void * const key) {
 int hasCode = (*(map->hashCode))(key);
 hasCode %= map->initialCapacity;
 if (hasCode < 0)
  hasCode += map->initialCapacity;
 Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
 return re != NULL;
}
 
//增加一條映射
void myHashMapPutData(MyHashMap * const map, void * const key,
  void * const value) {
 int hasCode = (*(map->hashCode))(key);
 hasCode %= map->initialCapacity;
 if (hasCode < 0)
  hasCode += map->initialCapacity;
 Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
 if (re == NULL) {
  Entry * entry = (Entry*) malloc(sizeof(Entry));
  entry->key = key;
  entry->value = value;
  myListInsertDataAtLast(map->entryList[hasCode], entry);
  (map->size)++;
  if (map->size > map->initialCapacity * map->loadFactor) {
   rebuildMyHashMap(map);
  }
 } else {
  re->value = value;
 }
}
 
//通過key得到數據，如果沒有數據則返回null
void* myHashMapGetDataByKey(MyHashMap * const map, void * const key) {
 int hasCode = (*(map->hashCode))(key);
 hasCode %= map->initialCapacity;
 if (hasCode < 0)
  hasCode += map->initialCapacity;
 Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
 if (re == NULL) {
  return NULL;
 }
 return re->value;
}
 
//數據的容量
int myHashMapGetSize(const MyHashMap * const map) {
 return map->size;
}
 
//創建Entry迭代器
MyHashMapEntryIterator* createMyHashMapEntryIterator(MyHashMap * const map) {
 MyHashMapEntryIterator* re = (MyHashMapEntryIterator*) malloc(
   sizeof(MyHashMapEntryIterator));
 re->count = 0;
 re->index = 0;
 re->map = map;
 re->current = map->entryList[0]->first;
 return re;
}
 
//釋放Entry迭代器
void freeMyHashMapEntryIterator(MyHashMapEntryIterator* iterator) {
 free(iterator);
}
 
//Entry迭代器是否有下一個
int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator) {
 return iterator->count < iterator->map->size;
}
 
//遍歷下一個Entry元素
Entry* myHashMapEntryIteratorNext(MyHashMapEntryIterator* iterator) {
 (iterator->count)++;
 while (!(iterator->current)) {
  (iterator->index)++;
  iterator->current = iterator->map->entryList[iterator->index]->first;
 }
 Entry * re = (Entry *) iterator->current->data;
 iterator->current = iterator->current->next;
 return re;
}
 
//刪除一條數據，返回是否刪除成功
int myHashMapRemoveDataByKey(MyHashMap * const map, void * const key) {
 int hasCode = (*(map->hashCode))(key);
 hasCode %= map->initialCapacity;
 if (hasCode < 0)
  hasCode += map->initialCapacity;
 MyListIterator* it = createMyListIterator(map->entryList[hasCode]);
 int re = 0;
 while (myListIteratorHasNext(it)) {
  Entry * entry = (Entry *) (myListIteratorNext(it));
  if ((*(map->equal))(entry->key, key)) {
   myListRemoveDataAt(map->entryList[hasCode], it->count - 1);
   re = 1;
   (map->size)--;
   break;
  }
 }
 freeMyListIterator(it);
 return re;
}
 
void myFree(Entry * p){
    free(p);
}
 
//釋放HashMap
void freeMyHashMap(MyHashMap * map) {
 myHashMapOutput(map, myFree);
 for (int i = 0; i < map->initialCapacity; i++) {
  freeMyList(map->entryList[i]);
 }
 free(map->entryList);
 free(map);
}
 
//遍歷
void myHashMapOutput(MyHashMap *map, void(*pt)(Entry*)) {
 MyHashMapEntryIterator* iterator = createMyHashMapEntryIterator(map);
 while (myHashMapEntryIteratorHasNext(iterator)) {
  pt(myHashMapEntryIteratorNext(iterator));
 }
 freeMyHashMapEntryIterator(iterator);
}

測試文件

/*************************
*** File main.c
*** test for MyHashMap
**************************/
#include <stdio.h>
#include <stdlib.h>
#include "myEqual.h"
#include "myHashCode.h"
#include "myHashMap.h"
 
#define S 10
 
char* strs[S]=
{
    "abc",
    "qq",
    "hello",
    "abc",
    "lmy",
    "ab",
    "qq",
    "lqw",
    "sww",
    "lqw"
};
 
 
int main()
{
 
    int*  data = malloc(sizeof(int)* S);
    for (int i=0; i<S; i++)
    {
        data[i]=i;
    }
 
    //創建映射需要指定兩個函數，hashCode函數和equal函數。
    MyHashMap * map = createMyHashMap(myHashCodeString, myEqualString);
 
    //插入數據
    for (int i=0; i<S; i++)
    {
        myHashMapPutData(map, strs[i], &data[i]);
    }
 
    //輸出大小
    printf("size=%d\n",myHashMapGetSize(map));
 
    //測試刪除
    myHashMapRemoveDataByKey(map,"qq");
    myHashMapRemoveDataByKey(map,"ab");
    myHashMapRemoveDataByKey(map,"qwert");
 
    //輸出大小
    printf("after remove size=%d\n",myHashMapGetSize(map));
 
    //遍歷
    MyHashMapEntryIterator * it = createMyHashMapEntryIterator(map);
    while(myHashMapEntryIteratorHasNext(it))
    {
        Entry * pp= myHashMapEntryIteratorNext(it);
        char * key = pp-> key;
        int * value = pp->value;
        printf("%s(%d)\n", key, *value);
    }
    //釋放遍歷器
    freeMyHashMapEntryIterator(it);
 
    //釋放映射
    freeMyHashMap(map);
 
    //釋放數據
    free(data);
    return 0;
}

以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。

推薦閱讀：