# Different Data Structure Insertion and Search Time Test:
## B-tree (或B+tree)、treap、skip list、array of sorted arrays、hash table

程式碼:
---

### B+tree

// Searching on a B+ tree in C++

// Searching on a B+ tree in C++

#include <climits>
#include <fstream>
#include <iostream>
#include <sstream>
#include <random>
#include <chrono>
using namespace std;
int MAX = 3;

// BP node
class Node {
  bool IS_LEAF;
  int *key, size;
  Node **ptr;
  friend class BPTree;

   public:
  Node();
};

// BP tree
class BPTree {
  Node *root;
  void insertInternal(int, Node *, Node *);
  Node *findParent(Node *, Node *);

   public:
  BPTree();
  void search(int);
  void insert(int);
  void display(Node *);
  Node *getRoot();
};

Node::Node() {
  key = new int[MAX];
  ptr = new Node *[MAX + 1];
}

BPTree::BPTree() {
  root = NULL;
}

// Search operation
void BPTree::search(int x) {
  if (root == NULL) {
    cout << "Tree is empty\n";
  } else {
    Node *cursor = root;
    while (cursor->IS_LEAF == false) {
      for (int i = 0; i < cursor->size; i++) {
        if (x < cursor->key[i]) {
          cursor = cursor->ptr[i];
          break;
        }
        if (i == cursor->size - 1) {
          cursor = cursor->ptr[i + 1];
          break;
        }
      }
    }
    for (int i = 0; i < cursor->size; i++) {
      if (cursor->key[i] == x) {
        cout << "Found\n";
        return;
      }
    }
    cout << "Not found\n";
  }
}

// Insert Operation
void BPTree::insert(int x) {
  if (root == NULL) {
    root = new Node;
    root->key[0] = x;
    root->IS_LEAF = true;
    root->size = 1;
  } else {
    Node *cursor = root;
    Node *parent;
    while (cursor->IS_LEAF == false) {
      parent = cursor;
      for (int i = 0; i < cursor->size; i++) {
        if (x < cursor->key[i]) {
          cursor = cursor->ptr[i];
          break;
        }
        if (i == cursor->size - 1) {
          cursor = cursor->ptr[i + 1];
          break;
        }
      }
    }
    if (cursor->size < MAX) {
      int i = 0;
      while (x > cursor->key[i] && i < cursor->size)
        i++;
      for (int j = cursor->size; j > i; j--) {
        cursor->key[j] = cursor->key[j - 1];
      }
      cursor->key[i] = x;
      cursor->size++;
      cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
      cursor->ptr[cursor->size - 1] = NULL;
    } else {
      Node *newLeaf = new Node;
      int virtualNode[MAX + 1];
      for (int i = 0; i < MAX; i++) {
        virtualNode[i] = cursor->key[i];
      }
      int i = 0, j;
      while (x > virtualNode[i] && i < MAX)
        i++;
      for (int j = MAX + 1; j > i; j--) {
        virtualNode[j] = virtualNode[j - 1];
      }
      virtualNode[i] = x;
      newLeaf->IS_LEAF = true;
      cursor->size = (MAX + 1) / 2;
      newLeaf->size = MAX + 1 - (MAX + 1) / 2;
      cursor->ptr[cursor->size] = newLeaf;
      newLeaf->ptr[newLeaf->size] = cursor->ptr[MAX];
      cursor->ptr[MAX] = NULL;
      for (i = 0; i < cursor->size; i++) {
        cursor->key[i] = virtualNode[i];
      }
      for (i = 0, j = cursor->size; i < newLeaf->size; i++, j++) {
        newLeaf->key[i] = virtualNode[j];
      }
      if (cursor == root) {
        Node *newRoot = new Node;
        newRoot->key[0] = newLeaf->key[0];
        newRoot->ptr[0] = cursor;
        newRoot->ptr[1] = newLeaf;
        newRoot->IS_LEAF = false;
        newRoot->size = 1;
        root = newRoot;
      } else {
        insertInternal(newLeaf->key[0], parent, newLeaf);
      }
    }
  }
}

// Insert Operation
void BPTree::insertInternal(int x, Node *cursor, Node *child) {
  if (cursor->size < MAX) {
    int i = 0;
    while (x > cursor->key[i] && i < cursor->size)
      i++;
    for (int j = cursor->size; j > i; j--) {
      cursor->key[j] = cursor->key[j - 1];
    }
    for (int j = cursor->size + 1; j > i + 1; j--) {
      cursor->ptr[j] = cursor->ptr[j - 1];
    }
    cursor->key[i] = x;
    cursor->size++;
    cursor->ptr[i + 1] = child;
  } else {
    Node *newInternal = new Node;
    int virtualKey[MAX + 1];
    Node *virtualPtr[MAX + 2];
    for (int i = 0; i < MAX; i++) {
      virtualKey[i] = cursor->key[i];
    }
    for (int i = 0; i < MAX + 1; i++) {
      virtualPtr[i] = cursor->ptr[i];
    }
    int i = 0, j;
    while (x > virtualKey[i] && i < MAX)
      i++;
    for (int j = MAX + 1; j > i; j--) {
      virtualKey[j] = virtualKey[j - 1];
    }
    virtualKey[i] = x;
    for (int j = MAX + 2; j > i + 1; j--) {
      virtualPtr[j] = virtualPtr[j - 1];
    }
    virtualPtr[i + 1] = child;
    newInternal->IS_LEAF = false;
    cursor->size = (MAX + 1) / 2;
    newInternal->size = MAX - (MAX + 1) / 2;
    for (i = 0, j = cursor->size + 1; i < newInternal->size; i++, j++) {
      newInternal->key[i] = virtualKey[j];
    }
    for (i = 0, j = cursor->size + 1; i < newInternal->size + 1; i++, j++) {
      newInternal->ptr[i] = virtualPtr[j];
    }
    if (cursor == root) {
      Node *newRoot = new Node;
      newRoot->key[0] = cursor->key[cursor->size];
      newRoot->ptr[0] = cursor;
      newRoot->ptr[1] = newInternal;
      newRoot->IS_LEAF = false;
      newRoot->size = 1;
      root = newRoot;
    } else {
      insertInternal(cursor->key[cursor->size], findParent(root, cursor), newInternal);
    }
  }
}

// Find the parent
Node *BPTree::findParent(Node *cursor, Node *child) {
  Node *parent;
  if (cursor->IS_LEAF || (cursor->ptr[0])->IS_LEAF) {
    return NULL;
  }
  for (int i = 0; i < cursor->size + 1; i++) {
    if (cursor->ptr[i] == child) {
      parent = cursor;
      return parent;
    } else {
      parent = findParent(cursor->ptr[i], child);
      if (parent != NULL)
        return parent;
    }
  }
  return parent;
}

// Print the tree
void BPTree::display(Node *cursor) {
  if (cursor != NULL) {
    for (int i = 0; i < cursor->size; i++) {
      cout << cursor->key[i] << " ";
    }
    cout << "\n";
    if (cursor->IS_LEAF != true) {
      for (int i = 0; i < cursor->size + 1; i++) {
        display(cursor->ptr[i]);
      }
    }
  }
}

// Get the root
Node *BPTree::getRoot() {
  return root;
}

int main() {
    BPTree node;
    int num;
    std::cin>>num;

    // Measure the time it takes to insert 1<<num values
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        node.insert(rand()%2147483648);
    }
    auto end = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Insertion Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl;

    //print the data structure
    //node.display(node.getRoot());

    // Search for the number
    auto start2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        node.search(rand()%2147483647);
    }
    auto end2 = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Finding Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count() << " ms" << std::endl;

}

------

### Treap

// C++ program to demonstrate search, insert and delete in Treap
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
  
// A Treap Node
struct TreapNode
{
    int key, priority;
    TreapNode *left, *right;
};
  
/* T1, T2 and T3 are subtrees of the tree rooted with y
  (on left side) or x (on right side)
                y                               x
               / \     Right Rotation          /  \
              x   T3   – – – – – – – >        T1   y
             / \       < - - - - - - -            / \
            T1  T2     Left Rotation            T2  T3 */
  
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
TreapNode *rightRotate(TreapNode *y)
{
    TreapNode *x = y->left,  *T2 = x->right;
  
    // Perform rotation
    x->right = y;
    y->left = T2;
  
    // Return new root
    return x;
}
  
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
TreapNode *leftRotate(TreapNode *x)
{
    TreapNode *y = x->right, *T2 = y->left;
  
    // Perform rotation
    y->left = x;
    x->right = T2;
  
    // Return new root
    return y;
}
  
/* Utility function to add a new key */
TreapNode* newNode(int key)
{
    TreapNode* temp = new TreapNode;
    temp->key = key;
    temp->priority = rand()%100;
    temp->left = temp->right = NULL;
    return temp;
}
  
// C function to search a given key in a given BST
TreapNode* search(TreapNode* root, int key)
{
    // Base Cases: root is null or key is present at root
    if (root == NULL || root->key == key)
       return root;
  
    // Key is greater than root's key
    if (root->key < key)
       return search(root->right, key);
  
    // Key is smaller than root's key
    return search(root->left, key);
}
  
/* Recursive implementation of insertion in Treap */
TreapNode* insert(TreapNode* root, int key)
{
    // If root is NULL, create a new node and return it
    if (!root)
        return newNode(key);
  
    // If key is smaller than root
    if (key <= root->key)
    {
        // Insert in left subtree
        root->left = insert(root->left, key);
  
        // Fix Heap property if it is violated
        if (root->left->priority > root->priority)
            root = rightRotate(root);
    }
    else  // If key is greater
    {
        // Insert in right subtree
        root->right = insert(root->right, key);
  
        // Fix Heap property if it is violated
        if (root->right->priority > root->priority)
            root = leftRotate(root);
    }
    return root;
}
  
// A utility function to print tree
void inorder(TreapNode* root)
{
    if (root)
    {
        inorder(root->left);
        cout << "key: "<< root->key << " | priority: %d "
            << root->priority;
        if (root->left)
            cout << " | left child: " << root->left->key;
        if (root->right)
            cout << " | right child: " << root->right->key;
        cout << endl;
        inorder(root->right);
    }
}

 
// Driver Program to test above functions
int main()
{
    srand(time(NULL));
  
    struct TreapNode *root = NULL;
    
    int num;
    std::cin>>num;

    // Measure the time it takes to insert 1<<num values
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        root = insert(root, rand()%2147483648 );
    }
    auto end = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Insertion Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl;

    //print the data structure
    //ds.print();

    // Search for the number
    auto start2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        TreapNode *res = search(root, rand()%2147483647)
    }
    auto end2 = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Finding Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count() << " ms" << std::endl;

    //Search the data and get the result
    //TreapNode *res = search(root, 50);
    //(res == NULL)? cout << "\n50 Not Found ":
    //               cout << "\n50 found";

------

### Skip List

// C++ code for searching and deleting element in skip list
 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
 
// Class to implement node
class Node
{
public:
    int key;
 
    // Array to hold pointers to node of different level
    Node **forward;
    Node(int, int);
};
 
Node::Node(int key, int level)
{
    this->key = key;
 
    // Allocate memory to forward
    forward = new Node*[level+1];
 
    // Fill forward array with 0(NULL)
    memset(forward, 0, sizeof(Node*)*(level+1));
};
 
// Class for Skip list
class SkipList
{
    // Maximum level for this skip list
    int MAXLVL;
 
    // P is the fraction of the nodes with level
    // i pointers also having level i+1 pointers
    float P;
 
    // current level of skip list
    int level;
 
    // pointer to header node
    Node *header;
public:
    SkipList(int, float);
    int randomLevel();
    Node* createNode(int, int);
    void insertElement(int);
    void deleteElement(int);
    void searchElement(int);
    void displayList();
};
 
SkipList::SkipList(int MAXLVL, float P)
{
    this->MAXLVL = MAXLVL;
    this->P = P;
    level = 0;
 
    // create header node and initialize key to -1
    header = new Node(-1, MAXLVL);
};
 
// create random level for node
int SkipList::randomLevel()
{
    float r = (float)rand()/RAND_MAX;
    int lvl = 0;
    while(r < P && lvl < MAXLVL)
    {
        lvl++;
        r = (float)rand()/RAND_MAX;
    }
    return lvl;
};
 
// create new node
Node* SkipList::createNode(int key, int level)
{
    Node *n = new Node(key, level);
    return n;
};
 
// Insert given key in skip list
void SkipList::insertElement(int key)
{
    Node *current = header;
 
    // create update array and initialize it
    Node *update[MAXLVL+1];
    memset(update, 0, sizeof(Node*)*(MAXLVL+1));
 
    /*    start from highest level of skip list
        move the current pointer forward while key
        is greater than key of node next to current
        Otherwise inserted current in update and
        move one level down and continue search
    */
    for(int i = level; i >= 0; i--)
    {
        while(current->forward[i] != NULL &&
              current->forward[i]->key < key)
            current = current->forward[i];
        update[i] = current;
    }
 
    /* reached level 0 and forward pointer to
       right, which is desired position to
       insert key.
    */
    current = current->forward[0];
 
    /* if current is NULL that means we have reached
       to end of the level or current's key is not equal
       to key to insert that means we have to insert
       node between update[0] and current node */
    if (current == NULL || current->key != key)
    {
        // Generate a random level for node
        int rlevel = randomLevel();
 
        /* If random level is greater than list's current
           level (node with highest level inserted in
           list so far), initialize update value with pointer
           to header for further use */
        if(rlevel > level)
        {
            for(int i=level+1;i<rlevel+1;i++)
                update[i] = header;
 
            // Update the list current level
            level = rlevel;
        }
 
        // create new node with random level generated
        Node* n = createNode(key, rlevel);
 
        // insert node by rearranging pointers
        for(int i=0;i<=rlevel;i++)
        {
            n->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = n;
        }
        cout<<"Successfully Inserted key "<<key<<"\n";
    }
};
 
// Delete element from skip list
void SkipList::deleteElement(int key)
{
    Node *current = header;
 
    // create update array and initialize it
    Node *update[MAXLVL+1];
    memset(update, 0, sizeof(Node*)*(MAXLVL+1));
 
    /*    start from highest level of skip list
        move the current pointer forward while key
        is greater than key of node next to current
        Otherwise inserted current in update and
        move one level down and continue search
    */
    for(int i = level; i >= 0; i--)
    {
        while(current->forward[i] != NULL  &&
              current->forward[i]->key < key)
            current = current->forward[i];
        update[i] = current;
    }
 
    /* reached level 0 and forward pointer to
       right, which is possibly our desired node.*/
    current = current->forward[0];
 
    // If current node is target node
    if(current != NULL and current->key == key)
    {
        /* start from lowest level and rearrange
           pointers just like we do in singly linked list
           to remove target node */
        for(int i=0;i<=level;i++)
        {
            /* If at level i, next node is not target
               node, break the loop, no need to move
              further level */
            if(update[i]->forward[i] != current)
                break;
 
            update[i]->forward[i] = current->forward[i];
        }
 
        // Remove levels having no elements
        while(level>0 &&
              header->forward[level] == 0)
            level--;
         cout<<"Successfully deleted key "<<key<<"\n";
    }
};
 
// Search for element in skip list
void SkipList::searchElement(int key)
{
    Node *current = header;
 
    /*    start from highest level of skip list
        move the current pointer forward while key
        is greater than key of node next to current
        Otherwise inserted current in update and
        move one level down and continue search
    */
    for(int i = level; i >= 0; i--)
    {
        while(current->forward[i] &&
               current->forward[i]->key < key)
            current = current->forward[i];
 
    }
 
    /* reached level 0 and advance pointer to
       right, which is possibly our desired node*/
    current = current->forward[0];
 
    // If current node have key equal to
    // search key, we have found our target node
    if(current and current->key == key)
        cout<<"Found key: "<<key<<"\n";
};
 
// Display skip list level wise
void SkipList::displayList()
{
    cout<<"\n*****Skip List*****"<<"\n";
    for(int i=0;i<=level;i++)
    {
        Node *node = header->forward[i];
        cout<<"Level "<<i<<": ";
        while(node != NULL)
        {
            cout<<node->key<<" ";
            node = node->forward[i];
        }
        cout<<"\n";
    }
};
 
// Driver to test above code
int main()
{
    // Seed random number generator
    srand((unsigned)time(0));
 
    // create SkipList object with MAXLVL and P
    SkipList lst(3, 0.5);
    
    int num;
    std::cin>>num;

    // Measure the time it takes to insert 1<<num values
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        lst.insert(rand()%2147483648 );
    }
    auto end = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Insertion Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl;

    //print the data structure
    //ds.print();

    // Search for the number
    auto start2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        lst.searchElement(rand()%2147483647);
    }
    auto end2 = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Finding Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count() << " ms" << std::endl;

    
    //print skip list
    //lst.displayList();
 
    //Search for node 19
    
 
    //Delete node 19
    //lst.deleteElement(19);
    //lst.displayList();
}

------

### Array of sorted rrays

#include <vector>
#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;

class DS {
private:
    std::vector<int> _arr;
    std::vector<std::vector<int>> _vec_vec;
    int _vec_num;

public:
    void print();
    std::pair<int, int> find(int);

public:
    DS() {
        _vec_num = 0;
    }

    void insert(int input) {
        _arr.push_back(input);

        for (int i = 0; i < _vec_vec.size(); i++) {
            if (!_vec_vec[i].empty()) {
                vector<int> merged(_arr.size() + _vec_vec[i].size());
                std:: merge(_arr.begin(), _arr.end(), _vec_vec[i].begin(), _vec_vec[i].end(), merged.begin());
                _arr = merged;
                _vec_vec[i].clear();
            } else if (!_arr.empty()) {
                // Assign _arr to _vec_vec[i] and clear _arr
                _vec_vec[i] = _arr;
                _arr.clear();
                break;
            }
        }

        if (!_arr.empty()) {
            // Push _arr to the end of _vec_vec and increment vec_num
            _vec_vec.push_back(_arr);
            _vec_num++;
            _arr.clear();
        }
    }
};

void DS::print() {
    std:: cout << "arrayOfSortedArrays: " << endl;
    for (int i = 0; i < _vec_vec.size(); ++i) {
        std:: cout << i << ": ";
        for (int j = 0; j < _vec_vec[i].size(); ++j) {
            std:: cout << _vec_vec[i][j] << ' ';
        }
        std:: cout << endl;
    }
    std:: cout << "Print end\n";
    return;
}

// Function to find a given number in the DS data structure
// and return an std::pair of integers containing the vector index
// and position of the number within the vector
std::pair<int, int>
DS:: find(int number) {
    // Loop through the vectors in _vec_of_vec
    for (int i = 0; i < _vec_vec.size(); i++) {
        // Perform binary search on the current vector
        int left = 0;
        int right = _vec_vec[i].size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (_vec_vec[i][mid] == number) {
                // Return a pair containing the vector index and position of the number
                return std::make_pair(i, mid);
            } else if (_vec_vec[i][mid] < number) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    // Return a pair with -1 as both elements if the number is not found
    return std::make_pair(-1, -1);
}

int main() {
    DS ds;

    int num;
    std::cin>>num;

    // Measure the time it takes to insert 1<<num values
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        ds.insert(rand()%2147483648 );
    }
    auto end = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Insertion Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl;

    //print the data structure
    //ds.print();

    // Search for the number
    auto start2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        std::pair<int, int> result = ds.find(rand()%2147483647);
    }
    auto end2 = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Finding Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count() << " ms" << std::endl;


    // Search for the number 32765
    //std::pair<int, int> result = ds.find(32765);
    //if (result.first != -1 && result.second != -1) {
    //    std::cout << "Number found at vector index " << result.first << " and position " << result.second << std::endl;
    //} else {
    //    std::cout << "Number not found" << std::endl;
    //}

    return 0;
}

------

### Hash Table

// C++ program to demonstrate search, insert and display in Hash Table
#include <random>
#include <chrono>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define CAPACITY 50000 // Size of the Hash Table

unsigned long hash_function(char* str) {
    unsigned long i = 0;
    for (int j=0; str[j]; j++)
        i += str[j];
    return i % CAPACITY;
}

typedef struct Ht_item Ht_item;

// Define the Hash Table Item here
struct Ht_item {
    char* key;
    char* value;
};

typedef struct HashTable HashTable;

// Define the Hash Table here
struct HashTable {
    // Contains an array of pointers
    // to items
    Ht_item** items;
    int size;
    int count;
};

Ht_item* create_item(char* key, char* value) {
    // Creates a pointer to a new hash table item
    Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item));
    item->key = (char*) malloc (strlen(key) + 1);
    item->value = (char*) malloc (strlen(value) + 1);
    
    strcpy(item->key, key);
    strcpy(item->value, value);

    return item;
}

HashTable* create_table(int size) {
    // Creates a new HashTable
    HashTable* table = (HashTable*) malloc (sizeof(HashTable));
    table->size = size;
    table->count = 0;
    table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*));
    for (int i=0; i<table->size; i++)
        table->items[i] = NULL;

    return table;
}

void free_item(Ht_item* item) {
    // Frees an item
    free(item->key);
    free(item->value);
    free(item);
}

void free_table(HashTable* table) {
    // Frees the table
    for (int i=0; i<table->size; i++) {
        Ht_item* item = table->items[i];
        if (item != NULL)
            free_item(item);
    }

    free(table->items);
    free(table);
}

void handle_collision(HashTable* table, unsigned long index, Ht_item* item) {
}

void ht_insert(HashTable* table, char* key, char* value) {
    // Create the item
    Ht_item* item = create_item(key, value);

    // Compute the index
    unsigned long index = hash_function(key);

    Ht_item* current_item = table->items[index];
    
    if (current_item == NULL) {
        // Key does not exist.
        if (table->count == table->size) {
            // Hash Table Full
            printf("Insert Error: Hash Table is full\n");
            // Remove the create item
            free_item(item);
            return;
        }
        
        // Insert directly
        table->items[index] = item; 
        table->count++;
    }

    else {
            // Scenario 1: We only need to update value
            if (strcmp(current_item->key, key) == 0) {
                strcpy(table->items[index]->value, value);
                return;
            }
    
        else {
            // Scenario 2: Collision
            // We will handle case this a bit later
            handle_collision(table, index, item);
            return;
        }
    }
}

char* ht_search(HashTable* table, char* key) {
    // Searches the key in the hashtable
    // and returns NULL if it doesn't exist
    int index = hash_function(key);
    Ht_item* item = table->items[index];

    // Ensure that we move to a non NULL item
    if (item != NULL) {
        if (strcmp(item->key, key) == 0)
            return item->value;
    }
    return NULL;
}

void print_search(HashTable* table, char* key) {
    char* val;
    if ((val = ht_search(table, key)) == NULL) {
        printf("Key:%s does not exist\n", key);
        return;
    }
    else {
        printf("Key:%s, Value:%s\n", key, val);
    }
}

void print_table(HashTable* table) {
    printf("\nHash Table\n-------------------\n");
    for (int i=0; i<table->size; i++) {
        if (table->items[i]) {
            printf("Index:%d, Key:%s, Value:%s\n", i, table->items[i]->key, table->items[i]->value);
        }
    }
    printf("-------------------\n\n");
}

int main() {
    //create a hash table
    HashTable* ht = create_table(CAPACITY);
    
    
    //print_search(ht, "2");
    
    int num;
    std::cin>>num;

    // Measure the time it takes to insert 1<<num values
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        ht_insert(ht, char(i), char(rand()%2147483647));
    }
    auto end = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Insertion Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl;

    // Search for the number
    auto start2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < num; ++i) {
        ht_search(ht, char(rand()%2147483647) 
    }
    auto end2 = std::chrono::high_resolution_clock::now();

    // Print the elapsed time in milliseconds
    std::cout << "Finding Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count() << " ms" << std::endl;


    
    //display search and the table
    //print_search(ht, "3");
    //print_table(ht);
    
    //free the hash table
    free_table(ht);
    return 0;
}