#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "uthash.h"
#define N 1000
const int RUN_MAX = 100000;

struct int_hash
{
    int id;
    UT_hash_handle hh;
};

struct int_hash *hash_table = NULL;
int array[N + 1] = {0}; // 假设数组足够大，可以存储0-1000的标记

void add_to_hash(int id)
{
    struct int_hash *s;
    HASH_FIND_INT(hash_table, &id, s);
    if (!s)
    {
        s = (struct int_hash *)malloc(sizeof *s);
        s->id = id;
        HASH_ADD_INT(hash_table, id, s);
    }
}

void add_to_array(int id)
{
    array[id] = id; // 标记该数字已存在
}

struct int_hash *find_in_hash(int id)
{
    struct int_hash *s;
    HASH_FIND_INT(hash_table, &id, s);
    return s;
}

int find_in_array(int id)
{
    for (size_t i = 0; i < N; i++)
    {
        if (array[i] == id)
        {
            return array[i];
        }
    }
}

int main()
{
    srand(time(NULL));

    // 填充哈希表和数组
    for (int i = 0; i < N; i++)
    {
        int num = rand() % (N + 1); // 生成0-1000的随机数
        add_to_hash(num);
        add_to_array(num);
    }

    // 查找数字100（模拟查找200个数的场景，但这里只查找100）
    clock_t start_hash, end_hash;
    clock_t start_array, end_array;

    // 查找哈希表
    start_hash = clock();
    for (int i = 0; i < RUN_MAX; i++)
    {
        find_in_hash(N - 1);
    }
    end_hash = clock();

    // 查找数组
    start_array = clock();
    for (int i = 0; i < RUN_MAX; i++)
    {
        find_in_array(N - 1);
    }
    end_array = clock();

    printf("Hash table lookup time: %ld\n", end_hash - start_hash);
    printf("Array lookup time: %ld\n", end_array - start_array);

    // 清理哈希表
    struct int_hash *current, *tmp;
    HASH_ITER(hh, hash_table, current, tmp)
    {
        HASH_DEL(hash_table, current);
        free(current);
    }

    return 0;
}