雜湊（Hashing）是一種將任意長度的輸入資料轉換為固定長度輸出的過程，通常使用一個稱為「雜湊函式」的數學演算法來實現。 這種過程生成的固定長度字串稱為「雜湊值」或「雜湊碼」，它就像是原始資料的「指紋」。 雜湊主要應用於創建高效資料結構（如雜湊表）以加快搜尋速度，以及在資訊安全領域用於驗證資料完整性（防止資料被篡改）和安全儲存密碼（因其不可逆特性）。

雜湊表（Hash Table）是一種根據「鍵」（Key）直接查詢「值」（Value）的資料結構，透過一個「雜湊函式」（Hash Function）計算出鍵在記憶體中的位置，能以平均O(1) 的時間複雜度進行快速的搜尋、插入和刪除操作。 它由鍵值對組成，並儲存在由多個「桶」（Bucket）構成的陣列中，廣泛應用於密碼儲存、資料完整性驗證等領域。

雜湊表的組成

• 鍵（Key）：: 用於識別和儲存資料的唯一標識符。
• 值（Value）：: 儲存在雜湊表中的實際資料。
• 雜湊函式（Hash Function）：: 一個將任意長度的鍵轉換為固定長度雜湊值的數學公式，用來計算出儲存位* 置的索引。
• 雜湊表（Hash Table）：: 儲存鍵值對的陣列，也稱作「桶」（Bucket）的集合。

#define MAX_NAME 256
#define TABLE_SIZE 10
#define DELETED_NODE (person *)(0xFFFFFFFFFFFFFFFFUL)

typedef struct
{
  char name[MAX_NAME];
  int age;
  // ... add other stuff later , maybe
} person;

person * hash_table[TABLE_SIZE];

unsigned int hash(char *name)
{
  int length = strnlen(name, MAX_SIZE);
  unsigned int has_value = 0;
  for (int i = 0; i < length; i++)
  {
    hash_vale += name[i];
    hash_vale = (hash_vale * name[i]) % TABLE_SIZE;
  }
  return hash_value;
}
k 
void init_hash_table()
{
  for (int i = 0; i < TABLE_SIZE; i++)
  {
    hash_table[i]  = NULL;
  }
  // table is empty
}

void print_table()
{
  print("Start\n");
  for (int i =0; i < TABLE_SIZE; i++)
  {
    if (hash_table[i] == NULL)
    {
      printf("\t%i\t---", i);
    }
    else if (hash_table[i] == DELETED_NODE)
    {
      printf("\t%i\t---<deleted>", i);  
    }
    else
    {
      printf("\t%i\t%s\n", i, hash_table[i]->name);
    }
  }
  print("End\n");
}

bool hash_table_insert(person *p)
{
  if (p == NULL) return false;
  int index = hash(p->name);
  // open addressing linear probing
  for (int i = 0; i < TABLE_SIZE; i++)
  {
    int try = (i + index) % TABLE_SIZE;
    if (hash_table[try] == NULL || hash_table[try] == DELETED_NODE)
    {
      hash_table[try] = p;
      return true;
    }
  }
  return false;
}

// find a person in the table by name
person *hash_table_look(char *name)
{
  int index  = hash(name);
  for (int i = 0; i < TABLE_SIZE; i++)
  {
    int try = (index + i) % TABLE_SIZE;
    if (hash_table[try] ==  NULL)
    {
      return NULL; // not here
    }
    if (hash_table[try] == DELETED_NODE)
    {
      continue;
    }
    if (hash_table[try] != NULL && strncmp(hash_table[try]->name, name, MAX_NAME) == 0)
    {
      return hash_table[try]; 
    }    
  }
  return NULL;
}

person *hash_table_delete(char *name)
{
  int index  = hash(name);
  for (int i = 0; i < TABLE_SIZE)
  {
    int try = (index + i) % TABLE_SIZE;
    if (hash_table[try] == NULL) return false;
    if (hash_table[try] == DELETED_NODE) continue;
    if (hash_table[try] != NULL && strncmp(hash_table[try]->name, name, MAX_NAME) == 0)
    {
      person *tmp = hash_table[try];
      hash_table[try] = DELETED_NODE; 
      return tmp;
    }  
  }
    return NULL;
}


int main()
{
  init_hash_table();
  print_table();
  
  printf("Jacob => %u\n", hash("Jacob"));
  printf("Natalie => %u\n", hash("Natalie"));
  printf("Sara => %u\n", hash("Sara"));
  printf("Mpho => %u\n", hash("Mpho"));
  printf("Tebogo => %u\n", hash("Tebogo"));
  printf("Ron => %u\n", hash("Ron"));
  printf("Jane => %u\n", hash("Jane"));
  printf("Maren => %u\n", hash("Maren"));
  printf("Bill => %u\n", hash("Bill"));
  
  person jacob = {.name = "Jacob", .age = 25};
  person kate = {.name = "kate", .age = 27};
  person mpho = {.name = "Mpho", .age = 14};
  
  hash_table_insert(&jacob);
  hash_table_insert(&kate);
  hash_table_insert(&mpho);
  
  person *tmp = hash_table_lookup("Mpho");
  
  return 0; 
}