C++ 简单 Hash容器的实现

主要实现了以整数为关键字的hash，以key%m_nSize为哈希函数，以(hash(key)+i)%m_nSize重新寻址，并附带了elf_hash的实现，使用过程中可灵活修改。

1 #ifndef _MY_HASH_INT_H_
  2 #define _MY_HASH_INT_H_
  3 
  4 template<class T,class K>
  5 class HashInt{
  6 public:
  7     HashInt();
  8     virtual ~HashInt();
  9 private:
 10     typedef struct tagElement 
 11     {
 12         T data;
 13         K key;
 14         bool use;
 15         tagElement(){use = false;}
 16         ~tagElement(){}
 17     }Element;
 18     unsigned int m_nSize;
 19     Element *m_arrT;
 20     unsigned int m_nElementCnt;
 21     // 查找
 22     bool find(K key,unsigned int &index);
 23 public:
 24     // 初始化，分配内存
 25     bool init(const unsigned int size);
 26     // 哈希函数
 27     unsigned int hash(K key);
 28     // ELF哈希函数
 29     unsigned int hash_elf(char *str);
 30     // 插入
 31     bool insert(T data,K key);
 32     // 删除
 33     bool remove(K key);
 34     // 查找
 35     bool find(K key,T &data);
 36     // 修改
 37     bool modify(T data,K key);
 38     void dump();
 39 };
 40 
 41 template<class T,class K>
 42 unsigned int HashInt<T, K>::hash_elf( char *str)
 43 {
 44     unsigned int locate = 0;
 45     unsigned int x = 0;
 46     while (*str)
 47     {
 48         locate = (locate << 4) + (*str++);//hash左移4位，当前字符ASCII存入hash低四位。 
 49         if ((x = locate & 0xF0000000L) != 0)
 50         {//如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。
 51             locate ^= (x >> 24);
 52             //清空28-31位。
 53             locate &= ~x;
 54         }
 55     }
 56     return locate%m_nSize;
 57 }
 58 
 59 template<class T,class K>
 60 HashInt<T, K>::~HashInt()
 61 {
 62     if(m_arrT != NULL)
 63     {
 64         delete[] m_arrT;
 65     }
 66 }
 67 
 68 template<class T,class K>
 69 HashInt<T, K>::HashInt()
 70 {
 71     m_arrT = NULL;
 72     m_nSize = 0;
 73     m_nElementCnt = 0;
 74 }
 75 
 76 template<class T,class K>
 77 void HashInt<T, K>::dump()
 78 {
 79     cout<<"m_nElementCnt="<<m_nElementCnt<<",m_nSize="<<m_nSize<<endl;
 80     for(unsigned int i = 0;i < m_nSize;i++)
 81     {
 82         if(m_arrT[i].use == true)
 83         {
 84             cout<<i<<"-";
 85             m_arrT[i].data->display();
 86         }
 87     }
 88     cout<<endl;
 89 }
 90 
 91 template<class T,class K>
 92 bool HashInt<T, K>::modify( T data,K key )
 93 {
 94     if( m_nElementCnt == 0)
 95     {
 96         return false;
 97     }
 98     bool exist = false;
 99     unsigned int index;
100     exist = find(key,index);
101     if( exist == true )
102     {
103         m_arrT[index].data = data;
104     }
105     return false;
106 }
107 
108 template<class T,class K>
109 bool HashInt<T, K>::find( K key,T &data )
110 {
111     if( m_nElementCnt == 0)
112     {
113         return false;
114     }
115     bool exist = false;
116     unsigned int index;
117     exist = find(key,index);
118     if( exist == true )
119     {
120         data = m_arrT[index].data;
121     }
122     return false;
123 }
124 
125 
126 template<class T,class K>
127 bool HashInt<T, K>::find( K key,unsigned int &index )
128 {
129     if( m_nElementCnt == 0)
130     {
131         return false;
132     }
133     unsigned int locate = hash(key),i = 1;
134     while(i < m_nSize)
135     {
136         if( m_arrT[locate].use == true &&  m_arrT[locate].key == key)
137         {
138             index = locate;
139             return true;
140         }
141         locate = (locate + i)%m_nSize;
142         i++;
143     }
144     return false;
145 }
146 
147 
148 template<class T,class K>
149 bool HashInt<T, K>::remove( K key )
150 {
151     // 表为空
152     if( m_nElementCnt == 0 )
153     {
154         return false;
155     }
156     bool exist = false;
157     unsigned int index;
158     exist = find(key,index);
159     if( exist == true )
160     {
161         m_arrT[index].use = false;
162         m_nElementCnt--;
163         return true;
164     }
165     return false;
166 }
167 
168 template<class T,class K>
169 bool HashInt<T, K>::insert( T data,K key)
170 {
171     // 表已满
172     if( m_nElementCnt == m_nSize )
173     {
174         return false;
175     }
176     unsigned int locate = hash(key),i = 1;
177     while(i < m_nSize)
178     {
179         if( m_arrT[locate].use == false)
180         {
181             m_arrT[locate].data = data;
182             m_arrT[locate].key = key;
183             m_arrT[locate].use = true;
184             m_nElementCnt++;
185             return true;
186         }
187         locate = (locate + i)%m_nSize;
188         i++;
189     }
190     return false;
191 }
192 
193 template<class T,class K>
194 unsigned int HashInt<T, K>::hash( K key )
195 {
196     return key%m_nSize;
197 }
198 
199 template<class T,class K>
200 bool HashInt<T, K>::init( const unsigned int size )
201 {
202     m_nSize = size;
203     m_arrT = new Element[m_nSize];
204     m_nElementCnt = 0;
205     cout<<"size = "<<sizeof(Element)*m_nSize<<endl;
206     return true;
207 }
208 
209 #endif

原文链接: https://www.cnblogs.com/tangxin-blog/p/4869963.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍