Commit 5d743f0

mo khan <mo.khan@gmail.com>
2020-08-03 21:29:52
Perform linear search when a collision is detected
1 parent bb8ead8
Changed files (3)
src/02/04/hash.c
@@ -17,22 +17,37 @@ int hash_index(Hash *hash, int key)
   return key % hash->size;
 }
 
+void *search(Node *list, int key)
+{
+  Node *current = list;
+
+  while (current) {
+    Tuple *t = current->data;
+    if (t->key == key)
+      return t->value;
+    current = current->next;
+  }
+
+  return NULL;
+}
+
 void *hash_get(Hash *hash, int key)
 {
   int bucket = hash_index(hash, key);
-  Node *list = hash->buckets + bucket;
-  if (list && list->data)
-    return ((Tuple *)list->data)->value;
-  else
-    return NULL;
+  Node *n = hash->buckets + bucket;
+  return (n->data) ? search(n, key) : NULL;
 }
 
 void hash_set(Hash *hash, int key, void *value)
 {
   int bucket = hash_index(hash, key);
-  Node *node = list_initialize(tuple_initialize(key, value));
-  hash->buckets[bucket] = *node;
-  hash_inspect(hash);
+  Tuple *tuple = tuple_initialize(key, value);
+  Node *n = hash->buckets + bucket;
+
+  if (n->data)
+    list_add(n, tuple);
+  else
+    hash->buckets[bucket] = *list_initialize(tuple);
 }
 
 void hash_inspect(Hash *hash)
src/02/04/hash_test.c
@@ -19,12 +19,11 @@ Ensure(HashTable, when_getting_a_value_for_a_key_that_has_not_been_inserted) {
 }
 
 Ensure(HashTable, when_getting_a_values_for_a_key_that_has_been_inserted) {
-  int key = 7;
-  int value = 100;
   Hash *hash = hash_init(13);
+  int key = 7;
 
-  hash_set(hash, key, value);
-  assert_that(hash_get(hash, key), is_equal_to(value));
+  hash_set(hash, key, (void *)100);
+  assert_that(hash_get(hash, key), is_equal_to(100));
 }
 
 Ensure(HashTable, when_a_hash_collision_occurs) {
@@ -54,5 +53,6 @@ int main(int argc, char **argv) {
   TestSuite *suite = create_test_suite();
   add_suite(suite, hash_table_tests());
   add_suite(suite, list_tests());
+  add_suite(suite, tuple_tests());
   return run_test_suite(suite, create_text_reporter());
 }
src/02/04/tuple_test.c
@@ -7,7 +7,7 @@ BeforeEach(Tuple) {}
 AfterEach(Tuple) {}
 
 Ensure(Tuple, when_initializing_a_tuple) {
-  Tuple *subject = tuple_initialize(21, 100);
+  Tuple *subject = tuple_initialize(21, (void *)100);
 
   assert_that(subject->key, is_equal_to(21));
   assert_that(subject->value, is_equal_to(100));