参照jdk自带HashMap，用c++实现了一个类似功能的东东，希望各位大虾指出不足。
#include "stdafx.h "
#include <stdio.h>
#include <memory.h>
class HashMap;
class Entry
{
friend class HashMap;
private:
void *key;
int keySize;
void *value;
Entry *next;
public:
Entry(int keySize=0)
{
key = NULL;
if(keySize > 0)
{
key = new char[keySize];
}
value = NULL;
next =NULL;
}
~Entry()
{
if(key != NULL)
delete [] key;
key = NULL;
}
const void *getKey(){return key;}
const int getKeySize(){return keySize;}
const void *getValue(){return value;}
};
class HashMap
{
private:
unsigned int max_capacity;
unsigned int capacity;
unsigned int cursize;
double load_factor;
Entry *entry;
Entry *entrySet;
private:
int HashCode(void *p,int length)
{
if(p == NULL) return 0;
int h = 0;
unsigned char *s = (unsigned char*)p;
for(int i=0;i <length;i++)
h += s[i];
h += ~(h < < 9);
h ^= (h > > 14);
h += (h < < 4);
h ^= (h > > 10);
return h;
}
unsigned int makeIndex(int hash)
{
return hash & (capacity - 1);
}
int expand()
{
Entry *entryNew = new Entry[2*capacity]();
if(entryNew == NULL)
return 1;
Entry *entryOld = entry;
entry = entryNew;
cursize = 0;
unsigned int capacityOld = capacity;
capacity = 2*capacity;
for(unsigned int i=0;i <capacityOld;i++)
{
Entry *pOld = &entryOld[i];
Entry *temp = NULL;
while(pOld != NULL)
{
if(pOld-> key != NULL && pOld-> value != NULL)
{
putValue(pOld-> key,pOld-> keySize,pOld-> value);
}
pOld = pOld-> next;
if(temp != NULL)
delete temp;
temp = pOld;
}
temp = NULL;
}
delete [] entryOld;
return 0;
}
void *putValue(void *key,int keySize,void *value)
{
#ifdef _DEBUG
int deep = 0;
#endif
if(key == NULL || value == NULL || keySize < 1) return NULL;
int hash = HashCode(key,keySize);
int index = makeIndex(hash);
Entry *pre = NULL,*e=NULL;
if(entry[index].key == NULL && entry[index].value == NULL)
{
void *p = new char[keySize];
if(p == NULL) return NULL;
entry[index].key = p;
memcpy(entry[index].key,key,keySize);
entry[index].keySize = keySize;
entry[index].value = value;
entry[index].next = NULL;
cursize++;
}
else
{
for(e = &entry[index];e != NULL;e=e-> next)
{
pre = e;
if( keySize == e-> keySize &&
memcmp(key,e-> key,keySize) == 0 )
{
void *temp = e-> value;
e-> value = value;
return temp;
}
#ifdef _DEBUG
deep++;
#endif
}
}
if(e == NULL && pre != NULL)
{
pre-> next = new Entry(keySize);
e = pre-> next;
if(e == NULL || e-> key == NULL) return NULL;
memcpy(e-> key,key,keySize);
e-> keySize = keySize;
e-> value = value;
e-> next = NULL;
cursize++;
}
#ifdef _DEBUG
printf( "\tdeep:%d ",deep);
#endif
return value;
}
Entry *getEntrySet()
{
if(cursize == 0) return NULL;
Entry *p = new Entry[cursize]();
if(p == NULL) return NULL;
int cur = 0;
for(unsigned int i=0;i <capacity;i++)
{
Entry *temp = &entry[i];
while(temp != NULL)
{
if(temp-> key != NULL && temp-> value != NULL)
{
p[cur].key = new char[temp-> keySize];
if(p[cur].key == NULL) return NULL;
memcpy(p[cur].key,temp-> key,temp-> keySize);
p[cur].keySize = temp-> keySize;
p[cur].value = temp-> value;
p[cur].next = NULL;
cur++;
}
temp = temp-> next;
}
}
return p;
}
public:
HashMap(unsigned int capacity = 16)
{
if(capacity < 1) capacity = 16;
max_capacity = 0xffffffff;
this-> capacity = capacity;
cursize = 0;
load_factor = 0.75;
entry = new Entry[capacity];
entrySet = NULL;
}
~HashMap()
{
Entry *p = NULL,*temp = NULL;
for(unsigned int i=0;i <capacity;i++)
{
p = &entry[i];
temp = NULL;
while(p != 0)
{
p = p-> next;
if(temp != 0)
delete temp;
temp = p;
}
}
if(entry != NULL)
delete [] entry;
entry = NULL;
if(entrySet != NULL)
delete [] entrySet;
entrySet = NULL;
this-> capacity = 16;
}
void *put(void *key,int keySize,void *value)
{
putValue(key,keySize,value);
if( (float)cursize/(float)capacity > = load_factor)
{
if(expand()) return NULL;
}
return value;
}
void* get(void *key,int keySize)
{
#ifdef _DEBUG
int deep = 0;
#endif
if(key == NULL || keySize < 1)
return NULL;
int hash = HashCode(key,keySize);
int index = makeIndex(hash);
if(entry[index].next == NULL)
return entry[index].value;
for(Entry *e = &entry[index];e != NULL;e = e-> next)
{
#ifdef _DEBUG
deep++;
#endif
if(e-> keySize == keySize &&
memcmp(key,e-> key,keySize) == 0 )
{
#ifdef _DEBUG
printf( "deep:%d\t ",deep);
#endif
return e-> value;
}
}
return NULL;
}
void * del(void *key,int keySize)
{
if(key == NULL || keySize < 1)
return NULL;
int hash = HashCode(key,keySize);
int index = makeIndex(hash);
if(entry[index].value == NULL && entry[index].key == NULL)
return NULL;
Entry *pre = NULL;
for(Entry *e = &entry[index];e != NULL;e = e-> next)
{
if(e-> keySize == keySize &&
memcmp(key,e-> key,keySize) == 0 )
{
void * value = NULL;
if(pre != NULL)
{
pre-> next = e-> next;
value = e-> value;
delete e;
}
else
{
delete [] e-> key;
e-> key = NULL;
if(e-> next != NULL)
{
value = e-> value;
e-> key = e-> next-> key;
e-> next-> key = NULL;
e-> keySize = e-> next-> keySize;
e-> value = e-> next-> value;
Entry *pn = e-> next;
e-> next = pn-> next;
delete pn;
}
else
{
memset(e,0x0,sizeof(Entry));
}
}
cursize--;
return value;
}
pre = e;
}
return NULL;
}
Entry * const getEntry()
{
if(entrySet != NULL)
{
delete [] entrySet;
}
entrySet = getEntrySet();
return entrySet;
}
const unsigned int getSize()
{
return cursize;
}
const unsigned int getCapacity()
{
return capacity;
}
};
int main(int argc, char* argv[])
{
HashMap map;
Entry *pe = new Entry[1]();
delete [] pe;
char temp[200][56];
for(int i=0;i <150;i++)
{
sprintf(temp[i], "string%d ",i);
map.put(&i,4,temp[i]);
}
printf( "size:%d,capacity:%d\n ",map.getSize(),map.getCapacity());
for(i=0;i <150;i++)
{
char *p = (char*)map.get(&i,4);
if(p != NULL)
#ifdef _DEBUG
printf( "%s\n ",p);
#else
printf( "%s\t ",p);
#endif
}
for(i = 3;i <50;i++)
map.del(&i,4);
i = 10;
printf( "size:%d,capacity:%d\t\t ",map.getSize(),map.getCapacity());
puts((char*)map.get(&i,4) == NULL? "NULL ":(char*)map.get(&i,4));
Entry *ee = map.getEntry();
for(i = 0;i < (int)map.getSize();i++)
{
printf( "key:%d\tvalue:%s\n ",*(int*)(ee[i].getKey()),(char*)(ee[i].getValue()));
}
return 0;
}
[解决办法]
去看《STL源码剖析》你就知道自己哪写得不好了。
有现成的就用现成的，绝对不要自己搞一套。
