aboutsummaryrefslogtreecommitdiff
path: root/design_hashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'design_hashmap.c')
-rw-r--r--design_hashmap.c92
1 files changed, 92 insertions, 0 deletions
diff --git a/design_hashmap.c b/design_hashmap.c
new file mode 100644
index 0000000..0b3d50a
--- /dev/null
+++ b/design_hashmap.c
@@ -0,0 +1,92 @@
+// 706. Design HashMap
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ * design a hashmap without usin any built-in hash table libraries. implement
+ * the 'MyHashMap' class:
+ * - myHashMapCreate() initialises the object with an empty map
+ * - put() inserts a key, value pair into the hashmap. if the key already exists
+ * in the map, update the corresponding value
+ * - get() returns the value to which the specified key is mapped, or -1 if this
+ * map contains no mapping for the key
+ * - remove() removes the key and its corresponding value if the map contains
+ * the mapping for the key
+ */
+
+typedef struct {
+ int **map;
+ int size;
+} MyHashMap;
+
+MyHashMap *myHashMapCreate() {
+ MyHashMap *res = malloc(sizeof(MyHashMap));
+ res->size = 10000;
+ res->map = calloc((res->size), sizeof(int *));
+ return res;
+}
+
+void myHashMapPut(MyHashMap *obj, int key, int val) {
+ int d = key, n = obj->size;
+ while (1) {
+ if (!obj->map[d % n]) {
+ obj->map[d % n] = malloc(2 * sizeof(int));
+ obj->map[d % n][0] = key;
+ obj->map[d % n][1] = val;
+ break;
+ } else if (obj->map[d % n][0] == key) {
+ obj->map[d % n][1] = val;
+ break;
+ } else {
+ d++;
+ }
+ }
+}
+
+int myHashMapGet(MyHashMap *obj, int key) {
+ int d = key, n = obj->size;
+ while (1) {
+ if (!obj->map[d % n])
+ return -1;
+ else if (obj->map[d % n][0] == key)
+ return obj->map[d % n][1];
+ else
+ d++;
+ }
+ return -1;
+}
+
+void myHashMapRemove(MyHashMap *obj, int key) {
+ int d = key, n = obj->size;
+ while (1) {
+ if (!obj->map[d % n])
+ break;
+ else if (obj->map[d % n][0] == key) {
+ obj->map[d % n][0] = -1;
+ break;
+ } else {
+ d++;
+ }
+ }
+}
+
+void myHashMapFree(MyHashMap *obj) {
+ int n = obj->size;
+ for (int i = 0; i < n; i++)
+ if (obj->map[i])
+ free(obj->map[i]);
+ free(obj->map);
+ free(obj);
+}
+
+int main() {
+ MyHashMap *obj = myHashMapCreate();
+ myHashMapPut(obj, 1, 1);
+ myHashMapPut(obj, 2, 2);
+ printf("%d\n", myHashMapGet(obj, 1)); // expect: 1
+ printf("%d\n", myHashMapGet(obj, 3)); // expect: -1
+ myHashMapPut(obj, 2, 1);
+ printf("%d\n", myHashMapGet(obj, 2)); // expect: 1
+ myHashMapRemove(obj, 2);
+ printf("%d\n", myHashMapGet(obj, 2)); // expect: -1
+}