Chinaunix首页 | 论坛 | 博客

韩轶明

首页　| 　博文目录　| 　关于我

enenshiwo

  • 博客访问： 265270
  • 博文数量： 84
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 927
  • 用 户 组： 普通用户
  • 注册时间： 2015-03-06 23:00
个人简介

growing

文章分类

全部博文（84）

文章存档

2017年（6）

2016年（61）

2015年（17）

我的朋友
最近访客
推荐博文
相关博文
HashTable:线性探测，二次探测。

分类： C/C++

2016-03-29 17:25:07

1.线性探测

  1. #pragma once
  2. #include<string>
  3.  
  4. enum Status
  5. {
  6.     EMPTY,
  7.     EXISTS,
  8.     DELETE,
  9. };

  11. template<class K>
  12. struct HashFuner
  13. {
  14.     size_t operator()(const K &key,int capacity)
  15.     {
  16.         return key%capacity;
  17.     }
  18. };

  20. template <>
  21. struct HashFuner<string>
  22. {

  24.     static size_t BKDRHash(const char *s)
  25.     {
  26.         unsigned int seed = 131;
  27.         unsigned hash = 0;
  28.         while (*s)
  29.         {
  30.             hash = hash*seed + (*s++);

  32.         }
  33.         return (hash & 0x7FFFFFFF);
  34.     }
  35.     size_t operator()(const string &key,int capacity)
  36.     {
  37.         return BKDRHash(key.c_str())%capacity;
  38.     }
  39. };



  43. template<class K ,class Hashfuncer=HashFuner<K>>
  44. class HashTable
  45. {
  46. public:
  47.     HashTable()
  48.         :_array(NULL)
  49.         ,_size(0)
  50.         ,_capacity(0)
  51.         ,_status(NULL)
  52.     {

  54.     }
  55.     HashTable(size_t capacity)
  56.         :_array(new K[capacity])
  57.         , _size(0)
  58.         , _capacity(capacity)
  59.         , _status(new Status[capacity])
  60.     {
  61.         for (int i = 0; i < capacity; ++i)
  62.         {
  63.             _status[i] = EMPTY;
  64.         }
  65.     }
  66.     ~HashTable()
  67.     {
  68.         delete[] _array;
  69.         delete[] _status;
  70.     }


  73.     bool Insert(const K& key)
  74.     {
  75.         if (_size * 10 / _capacity > 8)//载荷因子大于0.8时要扩容
  76.         {
  77.             HashTable<K,Hashfuncer> *newHash = new HashTable<K, Hashfuncer>(_capacity * 3);

  79.             for (int i = 0; i < _capacity; ++i)
  80.             {
  81.                 if (_status[i] == EXISTS)
  82.                 {
  83.                     newHash->Insert(_array[i]);
  84.                 }
  85.             }
  86.             Swap(*newHash);
  87.         }
  88.         int index = Hashfuncer()(key,_capacity);
  89.         while (_status[index]==EXISTS)
  90.         {
  91.             index++;
  92.             if (index == _capacity)
  93.             {
  94.                 index = 0;
  95.             }
  96.         }
  97.         _array[index] = key;
  98.         _status[index] = EXISTS;
  99.         _size++;
  100.         return true;
  101.     }
  102.     bool Remove(K key)
  103.     {
  104.         int index = Hashfuncer()(key,_capacity);
  105.         while (_status[index] != EMPTY)
  106.         {
  107.             if (_array[index] == key)
  108.             {
  109.                 if (_status[index] == DELETE)
  110.                 {
  111.                     return false;
  112.                 }
  113.                 _status[index] = DELETE;
  114.                 return true;
  115.             }
  116.             index++;
  117.             if (index == _capacity)
  118.             {
  119.                 index = 0;
  120.             }
  121.         }
  122.         return false;
  123.     }
  124.     bool Find(K key)
  125.     {
  126.         int index = Hashfuncer()(key,_capacity);
  127.         while (_status[index] != EMPTY)
  128.         {
  129.             if (_array[index] == key)
  130.             {
  131.                 if (_status[index] == DELETE)
  132.                 {
  133.                     return false;
  134.                 }
  135.                 return true;
  136.             }
  137.             index++;
  138.             if (index == _capacity)
  139.             {
  140.                 index = 0;
  141.             }
  142.         }
  143.         return false;
  144.     }
  145.     void Print()
  146.     {
  147.         for (int i = 0; i < _capacity; ++i)
  148.         {
  149.             if (_status[i] == EXISTS)
  150.             {
  151.                 cout << '[' << _array[i]<< ']' << " ";
  152.             }
  153.             else
  154.                 cout << "[]" << " ";
  155.         }
  156.         cout << endl;
  157.     }

  159.     void Swap(HashTable<K, Hashfuncer> h)
  160.     {
  161.         swap(_array, h._array);
  162.         swap(_size, h._size);
  163.         swap(_capacity, h._capacity);
  164.         swap(_status, h._status);
  165.     }


  168. protected:
  169.     K* _array;
  170.     size_t _size;
  171.     size_t _capacity;
  172.     Status *_status;
  173. };

测试：

  1. #include <iostream>
  2. using namespace std;
  3. #include "HashTable.h"

  5. void Test()
  6. {
  7.     HashTable<string>ht1(3);
  8.     ht1.Insert("a");
  9.     ht1.Insert("b");
  10.     ht1.Insert("c");
  11.     ht1.Insert("d");
  12.     ht1.Insert("d");
  13.     ht1.Print();
  14.     ht1.Remove("c");
  15.     ht1.Print();
  16.     
  17.     if(ht1.Find("d"))
  18.     {
  19.         cout<<"find success!"<<endl;
  20.     }
  21.     if(ht1.Find("c"))
  22.     {
  23.         cout<<"aa"<<endl;
  24.     }

  26. }
  27. int main()
  28. {
  29.     Test();
  30.     return 0;
  31. }
2.二次探测

  1. #pragma once

  3. enum Status
  4. {
  5.     EXISTS,
  6.     DELETE,
  7.     EMPTY,
  8. };
  9. static size_t BKDRHash(const char *s)
  10. {
  11.     unsigned int seed = 131;
  12.     unsigned hash = 0;
  13.     while (*s)
  14.     {
  15.         hash = hash*seed + (*s++);

  17.     }
  18.     return (hash & 0x7FFFFFFF);
  19. }
  20. template<class K>
  21. size_t Hashfun0(const K &key, int _capacity)
  22. {

  24.     return BKDRHash(key.c_str()) % _capacity;
  25. }
  26. template<class K>
  27. size_t Hashfun2(const K & preHashNum, int i)
  28. {
  29.     return preHashNum + 2 * i - 1;
  30. }


  33. template<class K>
  34. struct HashFuner
  35. {
  36.     size_t operator()(const K &key)
  37.     {
  38.         return key;
  39.     }
  40. };
  41. template<>
  42. struct HashFuner<string>
  43. {
  44.     size_t operator()(const string &key, int _capacity)
  45.     {
  46.         return Hashfun0(key, _capacity);
  47.     }
  48. };

  50. template<class K,class V>
  51. class KeyValueNode
  52. {
  53. public:
  54.     KeyValueNode()
  55.     {}
  56.     KeyValueNode(const K& key,const V& value)
  57.         :_key(key)
  58.         ,_value(value)
  59.     {}
  60.     K _key;
  61.     V _value;
  62. };

  64. template<class K, class V, class HashFun = HashFuner<K>>
  65. class HashTable
  66. {
  67. public:
  68.     typedef KeyValueNode<K, V> KVNode;

  70.     HashTable()
  71.         :_tables(NULL)
  72.         , _size(0)
  73.         , _capacity(0)
  74.         , _status(NULL)
  75.     {}
  76.     HashTable(size_t capacity)
  77.         :_tables(new KVNode[capacity])
  78.         , _size(0)
  79.         , _capacity(capacity)
  80.         , _status(new Status[capacity])
  81.     {
  82.         for (int i = 0; i < _capacity; ++i)
  83.         {
  84.             _status[i] = EMPTY;
  85.         }
  86.     }
  87.     ~HashTable()
  88.     {
  89.         delete[] _tables;
  90.         delete[] _status;
  91.         _capacity = 0;
  92.         _size = 0;
  93.     }
  94.     bool Insert(const K& key,const V& value)
  95.     {
  96.         if (_size * 10 / _capacity > 8)
  97.         {
  98.             HashTable<K, V, HashFun> *newtables = new HashTable<K, V, HashFun>(3 * _capacity);
  99.             for (int i = 0; i < _capacity; ++i)
  100.             {
  101.                 newtables->Insert(_tables[i]._key, _tables[i]._value);
  102.             }
  103.             Swap(*newtables);
  104.         }
  105.         int i = 1;
  106.         int index = HashFun()(key, _capacity);
  107.         while (_status[index] == EXISTS)
  108.         {
  109.             index = Hashfun2(index, i++);
  110.             if (index >= _capacity)
  111.             {
  112.                 index = index%_capacity;
  113.             }
  114.         }
  115.         _tables[index] = KVNode(key, value);
  116.         _status[index] = EXISTS;
  117.         _size++;
  118.         return true;
  119.     }
  120.     bool Remove(const K& key)
  121.     {
  122.         int index = HashFun()(key, _capacity);
  123.         int i = 1;
  124.         while (_status[index] != EMPTY)
  125.         {
  126.             if (_array[index] == key)
  127.             {
  128.                 if (_status[index] == DELETE)
  129.                 {
  130.                     return false;
  131.                 }
  132.                 _status[index] = DELETE;
  133.                 return true;
  134.             }
  135.             index = Hashfun2(index, i++);
  136.             if (index >= _capacity)
  137.             {
  138.                 index = index%_capacity;
  139.             }
  140.         }
  141.         return false;
  142.     }
  143.     KVNode<K,V>* Find(const K& key)
  144.     {
  145.         int index = HashFun()(key, _capacity);
  146.         int i = 1;
  147.         while (_status[index] != EMPTY)
  148.         {
  149.             if (_tables[index] == key)
  150.             {
  151.                 if (_status[index] == DELETE)
  152.                 {
  153.                     return NULL;
  154.                 }
  155.                 return _tables[index];
  156.             }
  157.             index = Hashfun2(index, i++);
  158.             if (index >= _capacity)
  159.             {
  160.                 index = index%_capacity;
  161.             }
  162.         }
  163.         return NULL;
  164.     }
  165.     void Print()
  166.     {
  167.         for (int i = 0; i < _capacity; ++i)
  168.         {
  169.             if (_status[i] == EXISTS)
  170.             {
  171.                 cout << '[' << _tables[i]._key.c_str() << "：" << _tables[i]._value.c_str() << ']' << " ";
  172.             }
  173.             else
  174.                 cout << "[]" << " ";
  175.         }
  176.         cout << endl;
  177.     }
  178.     void Swap(HashTable<K, V, HashFun> h)
  179.     {
  180.         swap(_tables, h._tables);
  181.         swap(_size, h._size);
  182.         swap(_capacity, h._capacity);
  183.         swap(_status, h._status);
  184.     }
  185. protected:
  186.     KVNode *_tables;
  187.     size_t _size;
  188.     size_t _capacity;
  189.     Status *_status;
  190. };
测试:

  1. void Test2()//二次
  2. {
  3.     HashTable<string, string>ht1(3);
  4.     ht1.Insert("a", "a");
  5.     ht1.Insert("b", "a");
  6.     ht1.Insert("c", "a");
  7.     ht1.Insert("d", "a");
  8.     ht1.Insert("d", "a");
  9.     ht1.Print();

  11.     HashTableNode<string, string>* ret = ht1.Find("a");
  12. }
  13. int main()
  14. {
  15.     Test2();
  16.     return 0;
  17. }



阅读(1199) | 评论(0) | 转发(0) |
0

上一篇：堆Heap（最小堆）

下一篇：BitSet位图

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6