时间戳

首页 > 解决方案 > 如何在哈希表中节省内存？

c - 如何在哈希表中节省内存？

问题描述

在我的结构中struct ListNode，我正在制作一个 int 类型的变量键，但有必要在struct Listnode我们制作它的内部制作它，HashTableNode因为当两个或更多项目存在时HashTableNode（即单个表节点中的冲突将更多）比我们必须创建更多的链表节点，如果我们可以在 HashTableNode 中定义它，那么每次在该节点键变量中都会消耗一些内存，而不是我们可以节省内存。

在每个列表节点中提及键是否正确，以便我们可以随时访问，因为下面的哈希表实现来自非常著名的数据结构书。

请告诉我我上面提到的是正确
的因为我是初学者如果不是那么请纠正我

#define Load_factor 20
#include<stdio.h>
#include<stdlib.h>
struct Listnode{
 int key;
 int data;
 struct Listnode* next;
};
struct HashTableNode{
 int bcount;          /// Number of elements in block
 struct Listnode* next;
 };
struct HashTable{
 int tsize;          /// Table size
 int count;
 struct HashTableNode** Table;
};
struct HashTable* createHashTable(int size){
 struct HashTable* h;
 h=(struct HashTable*)malloc(sizeof(struct HashTable));
 h->tsize=size/Load_factor;
 h->count=0;

 h->Table=(struct HashTableNode**)malloc(sizeof(struct HashTableNode*)*h->tsize);
 if(!h->Table){
 printf("Memory Error");
  return NULL;
 }
 for(int i=0;i<h->tsize;i++){
 h->Table[i]->bcount=0;
 h->Table[i]->next=NULL;
 }
   return h;
 }
int HASH(int  data,int tsize){
return(data%tsize);
}
/// Hashsearch
int HashSearch(struct HashTable* h,int data){
  struct Listnode* temp;
  temp=h->Table[HASH(data,h->tsize)]->next;
  while(temp)     ///same as temp!=NULL
  {
   if(temp->data==data)
      return 1;
    temp=temp->next;
  }
    return 0;

}

int HashDelete(struct HashTable* h,int  data)
{
 int index;
 struct Listnode *temp,*prev;
 index=HASH(data,h->tsize);
 for(temp=h->Table[index]->next,prev=NULL;temp;prev=temp,temp=temp->next)
 {
    if(temp->data==data)
    {
        if(prev!=NULL)
             prev->next=temp->next;
         free(temp);
         h->Table[index]->bcount--;
         h->count--;
         return 1;
    }
 }

 return 0;

}
int HashInsert(struct HashTable *h ,int data){
 int index;
 struct Listnode* temp,*newnode;
 if(HashSearch(h,data))
    return 0;
 index = HASH(data,h->tsize);
 temp=h->Table[index]->next;
 newnode=(struct Listnode*)malloc(sizeof(struct Listnode));
 if(!newnode)
    return -1;
 newnode->key=index;
 newnode->data;
 newnode->next=h->Table[index]->next;
 h->Table[index]->next=newnode;
 h->Table[index]->bcount++;
 h->count++;
   return 1;
}

标签： cdata-structureshash

解决方案

有必要为每个节点存储密钥，因为它用于解决冲突。请注意，冲突发生在哈希值而不是键上，这意味着Listnode同一桶 ( ) 中的每个元素 ( )HashTableNode仍将具有不同的键，因此您无法对其进行优化。

但是，在您的示例中，数据是键（通常称为 HashSet 而不是 HashMap） ，因此实际上不需要key.Listnode

推荐阅读