wordpress调用站点标题,没备案网站如何通过百度联盟审核,建设网站公司推荐,怎么做视频解析网站吗题目#xff1a;
不使用任何内建的哈希表库设计一个哈希映射#xff08;HashMap#xff09;。
实现 MyHashMap 类#xff1a;
MyHashMap() 用空映射初始化对象void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中#x…题目
不使用任何内建的哈希表库设计一个哈希映射HashMap。
实现 MyHashMap 类
MyHashMap() 用空映射初始化对象void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中则更新其对应的值 value 。int get(int key) 返回特定的 key 所映射的 value 如果映射中不包含 key 的映射返回 -1 。void remove(key) 如果映射中存在 key 的映射则移除 key 和它所对应的 value 。
示例
输入
[MyHashMap, put, put, get, get, put, get, remove, get]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出
[null, null, null, 1, -1, null, 1, null, -1]解释
MyHashMap myHashMap new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1未找到myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]更新已有的值
myHashMap.get(2); // 返回 1 myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1未找到myHashMap 现在为 [[1,1]]提示
0 key, value 106最多调用 104 次 put、get 和 remove 方法
思路
哈希函数能够将集合中任意可能的元素映射到一个固定范围的整数值并将该元素存储到整数值对应的地址上。 冲突处理由于不同元素可能映射到相同的整数值因此需要在整数值出现“冲突”时进行冲突处理。以下代码使用的解决冲突处理的方法是链地址法。
链地址法为每个哈希值维护一个链表并将具有相同哈希值的元素都放入这一链表当中。
设哈希表的大小为HSIZE则可以设计一个简单的哈希函数计算哈希值xxkey%HSIZE。
我们开辟一个大小为 HSIZE的数组数组的每个位置是一个链表。当计算出哈希值之后就插入到对应位置的链表当中。
由于我们使用整数除法作为哈希函数为了尽可能避免冲突应当将HSIZE 取为一个质数。 代码
typedef struct List
{int key;int val;struct List* next;
}List;void Insret(List* l1,int key,int val)
{if(l1NULL)return;List* p(List*)malloc(sizeof(List));p-keykey;p-valval;p-nextl1-next;l1-nextp;
}void Delete(List* l1,int key)
{if(l1NULL)return;struct List* pl1;struct List* qp-next;for(;p-next!NULL;pp-next){if(p-next-keykey){qp-next;p-nextq-next;free(q);break;//不加的话会有崩溃的风险} }
}List* Search(List* l1,int key)
{if(l1NULL)return NULL;List* pl1-next;for(;p!NULL;pp-next){if(p-keykey){return p;}}return NULL;
}void Free(List* l1)
{if(l1NULL)return;List* pl1-next;while(l1-next!NULL){pl1-next;l1-nextp-next;free(p);}
}typedef struct {List* data;
} MyHashMap;#define HSIZE 101MyHashMap* myHashMapCreate() {MyHashMap* myhash(MyHashMap*)malloc(sizeof(MyHashMap));myhash-data(List*)malloc(sizeof(List)*HSIZE);for(int i0;iHSIZE;i){myhash-data[i].nextNULL;}return myhash;
}void myHashMapPut(MyHashMap* obj, int key, int value) {if(objNULL)return;List* pSearch((obj-data[key%HSIZE]),key);if(pNULL){Insret((obj-data[key%HSIZE]),key,value);}else {p-valvalue;}
}int myHashMapGet(MyHashMap* obj, int key) {if(objNULL)return -1;List* pSearch((obj-data[key%HSIZE]),key);if(pNULL)return -1;elsereturn p-val;
}void myHashMapRemove(MyHashMap* obj, int key) {if(objNULL)return;Delete((obj-data[key%HSIZE]),key);
}void myHashMapFree(MyHashMap* obj) {if(objNULL)return;for(int i0;iHSIZE;i){Free((obj-data[i]));}free(obj-data);
}/*** Your MyHashMap struct will be instantiated and called as such:* MyHashMap* obj myHashMapCreate();* myHashMapPut(obj, key, value);* int param_2 myHashMapGet(obj, key);* myHashMapRemove(obj, key);* myHashMapFree(obj);
*/
心得 一开始编写Search函数时将其返回值设为int即int Search()返回结果为对应key值的value值但在后续编写void myHashMapPut()函数的过程中发现根据题目要求我们需要获取对应key值的节点来修改value值所以将Search函数的返回值改为List*。 在void Delete(List* l1,int key)函数中的for循环语句中需要加上break,否则如果删除的是此链表的最后一个数据时会再次执行循环语句即使用空指针NULL造成崩溃。
