哈希表开散列法(拉链法)

2018-03-02 08:27:46来源:cnblogs.com作者:你好,十二人点击

分享

开散列法又叫链地址法(开链法)。
开散列法:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

设元素的关键码为37, 25, 14, 36, 49, 68, 57, 11, 散列表为HT[12],表的大小为12,散列函数为Hash(x) = x % 11
Hash(37)=4
Hash(25)=3
Hash(14)=3
Hash(36)=3
Hash(49)=5
Hash(68)=2
Hash(57)=2
Hash(11)=0
使用哈希函数计算出每个元素所在的桶号,同一个桶的链表中存放哈希冲突的元素。
开散列
通常,每个桶对应的链表结点都很少,将n个关键码通过某一个散列函数,存放到散列表中的m个桶中,那么每一个桶中链表的平均长度为。以搜索平均长度为的链表代替了搜索长度为 n 的顺序表,搜索效率快的多。
应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上:
由于开地址法必须保持大量的空闲空间以确保搜索效率,如二次探查法要求装载因子a <= 0.7,而表项所占空间又比指针大的多,所以使用链地址法反而比开地址法节省存储空间。

哈希拉链相关代码如下:

使用素数表对齐做哈希表的容量,降低哈希冲突。

size_t HashTableKPrime(size_t N) //获取素数{  int i = 0;  const int _PrimeSize = 28;  static const unsigned long _PrimeList [] =  {      53ul, 97ul, 193ul, 389ul, 769ul,      1543ul, 3079ul, 6151ul, 12289ul, 24593ul,      49157ul, 98317ul, 196613ul, 393241ul, 786433ul,      1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,      50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,      1610612741ul, 3221225473ul, 4294967291ul  };  for (i=0; i<_PrimeSize; i++)  {      if (_PrimeList[i] > N)          return _PrimeList[i];  }  return _PrimeList[_PrimeSize-1];}

开辟拉链的链式节点

HashNode* BuyHashKNode(KeyType key,ValueType value) //开辟新节点{  HashNode *tmp = (HashNode *)malloc(sizeof(HashNode));  assert(tmp);  tmp->_key = key;  tmp->_value = value;  tmp->_next = NULL;  return tmp;}

哈希函数

KeyType HashKFunc(KeyType key,size_t n){    return key%n;}

哈希拉链表的初始化

void HashTableKInit(HashTable *ht,size_t N)//初始化{  assert(ht);  ht->_N = N;  ht->_size = 0;  **这里要特别注意开辟空间是给指针数组**  ht->_tables = (HashNode **)malloc(sizeof(HashNode*)*ht->_N);  assert(ht->_tables);  memset(ht->_tables,0,sizeof(HashNode*)*ht->_N);}

插入时扩容这块很关键,要重新开辟一块数组空间,把原先的表中数据映射过来,但是拉链节点不用重新开辟,直接把原先的节点拿过来。

int HashTableKInsert(HashTable* ht, KeyType key, ValueType value) //插入{    KeyType index;    HashNode *node = BuyHashKNode(key,value);    assert(ht);    if (ht->_N == ht->_size) //扩容    {     size_t i = 0;     HashTable newht;     HashTableKInit(&newht,HashTableKPrime(ht->_N));     for (i=0; i<ht->_N; i++)     {         if (ht->_tables[i])         {             KeyType index;             HashNode *cur = ht->_tables[i];             while (cur)             {                 HashNode *next = cur->_next;                 index = HashKFunc(cur->_key,newht._N);                 cur->_next = newht._tables[index];                 newht._tables[index] = cur;                 cur = next;             }         }     }     free(ht->_tables);     ht->_tables = newht._tables;     ht->_N = newht._N;    }    index = HashKFunc(key,ht->_N);    if (ht->_tables[index])    {        HashNode *cur = ht->_tables[index];        while (cur)        {            if (cur->_key == key)                return -1;            cur = cur->_next;        }    }    node->_next = ht->_tables[index];    ht->_tables[index] = node;    ht->_size++;    return 0;}

查找函数

HashNode* HashTableKFind(HashTable* ht, KeyType key) //查找{    ValueType index = HashKFunc(key,ht->_N);    assert(ht);    if (ht->_tables[index])    {        if (ht->_tables[index]->_key == key)            return ht->_tables[index];        else        {            HashNode *cur = ht->_tables[index];            while (cur)            {                if (cur->_key == key)                    return cur;                cur = cur->_next;            }            return NULL;        }    }    else        return NULL;    }

删除函数

int HashTableKRemove(HashTable* ht, KeyType key) //删除{    KeyType index = HashKFunc(key,ht->_N);    assert(ht);        if (ht->_tables[index])    {        HashNode *prev = ht->_tables[index];        HashNode *cur = ht->_tables[index];        while (cur)        {            if (cur == prev && cur->_key == key)            {                ht->_tables[index] = cur->_next;                free(cur);                cur = NULL;                ht->_size--;                return 0;            }            else if(cur->_key == key)            {                prev-> = cur->_next;                free(cur);                cur = NULL;                ht->_size--;                return 0;            }            prev = cur;            cur = cur->_next;        }        return -1;    }    else        return -1;}
void HashTableKDestory(HashTable* ht) //销毁{    size_t i = 0;    assert(ht);    for (i=0; i<ht->_N;++i)    {        if (ht->_tables[i])        {            HashNode *cur = ht->_tables[i];            while (cur)            {                HashNode *tmp = cur;                cur = cur->_next;                free(tmp);                tmp = NULL;            }        }    }    free(ht->_tables);    ht->_tables = NULL;    ht->_size = 0;    ht->_N = 0;}

测试函数

void TestHashTableK(){    HashTable ht;    HashTableKInit(&ht,3);    HashTableKInsert(&ht,10,0);    HashTableKInsert(&ht,11,0);    HashTableKInsert(&ht,12,0);    HashTableKInsert(&ht,106,0);    HashTableKInsert(&ht,53,0);    HashTableKInsert(&ht,1,0);    HashTableKInsert(&ht,15,0);    HashTableKInsert(&ht,0,0);    HashTableKInsert(&ht,53,0);    HashTableKInsert(&ht,52,0);    HashTableKInsert(&ht,104,0);    HashTableKInsert(&ht,2,0);    HashTableKInsert(&ht,54,0);    HashTableKInsert(&ht,108,0);    HashTableKPrint(&ht);    printf("/n");    printf("%d ",HashTableKFind(&ht,2)->_key);    printf("%d ",HashTableKFind(&ht,53)->_key);    printf("%d ",HashTableKFind(&ht,0)->_key);    printf("%d ",HashTableKFind(&ht,12)->_key);    printf("%p ",HashTableKFind(&ht,156));    printf("/n/n");    HashTableKRemove(&ht,2);    HashTableKRemove(&ht,53);    HashTableKRemove(&ht,1);    HashTableKRemove(&ht,54);    HashTableKRemove(&ht,89);    HashTableKPrint(&ht);    HashTableKDestory(&ht);    HashTableKPrint(&ht);}

测试结果:
法系拉链

相关哈希表概念请看哈希表详解:这里写链接内容

相关文章

    无相关信息

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台