hash.cpp

Matrix code

typedef int ValueType;

class Entry {
public:
	int hash;
	string key;
	int value;
	Entry* next;

	Entry()
	{
		this->hash=0;
		this->value=0;
		this->next=0;
	}

	Entry(int hash, string key, ValueType value, Entry* next)
	{
		this->hash=hash;
		this->key=key;
		this->value=value;
		this->next=next;
	}
};

class HashTable{
	public:
		HashTable(int initialCapacity=11, float loadFactor=0.75);
		~HashTable() { delete[] table; }
		class Bad_HashTable{};

		bool IsEmpty(); 		
		int getCount() const { return count; }
		void Put(string key, ValueType value, ValueType& oldValue);
		void Remove(string key, ValueType& value);
		ValueType* Get(string key);
		void ReHash();

	private:
		int HashCode(string key);
		
		// The hash table data
		Entry** table;

		//  The length of Table;
		int length;
    
        // The total number of entries in the hash table.
        int count;

        /**
        * The table is rehashed when its size exceeds this threshold.  (The
        * value of this field is (int)(capacity * loadFactor).)       
        */
        int threshold;
							 
        // The load factor for the hashtable.
        float loadFactor;    
};


HashTable::HashTable(int initialCapacity, float loadFactor) 
{
	if (initialCapacity < 0)
	    throw Bad_HashTable();

	if (loadFactor <= 0 )
        throw Bad_HashTable();

    if (initialCapacity==0)
            initialCapacity = 1;

	this->loadFactor = loadFactor;
	table = new Entry*[initialCapacity];
	for( int i=0; i<initialCapacity; i++)
	{
		table[i]=0;
	}
	count=0;
	length=initialCapacity;
	threshold = (int)(initialCapacity * loadFactor);
}

bool HashTable::IsEmpty() 
{
	return count==0;
}

    
void HashTable::Put(string key, ValueType value,ValueType& oldValue )
{
	// Make sure the value is not null
	if ( key.empty() ){ 
	    throw Bad_HashTable();
	}

	// Makes sure the key is not already in the hashtable.
	Entry** tab = table;
	int hash = HashCode(key);
	int index = hash % length;
	for(Entry* p=tab[index]; p!=0; p=p->next) 
	{
		if ( p->hash == hash && p->key==key ) {
			oldValue = p->value;
			p->value = value;
		}
	}

	if (count >= threshold) {
	    // Rehash the table if the threshold is exceeded
	    ReHash();		
		tab = table;
        index = hash % length;
	} 

	// Creates the new entry.
	Entry* q = new Entry(hash, key, value, tab[index]);
	tab[index] = q;
	count++;
}

void HashTable::Remove(string key, ValueType& value) 
{
	Entry** tab = table;
	int hash = HashCode(key);
	int index = hash % length;
	for (Entry* p=tab[index], *prev=0; p!=0; prev=p, p=p->next) {
		if ( p->hash == hash && p->key==key) {
			if (prev != 0)
			    prev->next = p->next;
			else
				tab[index] = p->next;
		}
		count--;
		value = p->value;
		delete p;
	}
}

ValueType* HashTable::Get(string key) 
{
	Entry** tab= table;
	int hash = HashCode(key);
	int index = hash % length;
	for (Entry* p=tab[index]; p!=0 ; p=p->next) {
		if (p->hash == hash && p->key==key) {
			return &(p->value);
		}
	}
	return 0;
}

void HashTable::ReHash() 
{
	int oldCapacity = length;
	Entry** oldTab = table;

	int newCapacity = oldCapacity * 2 + 1;
	Entry** newTab = new Entry*[newCapacity];
	for( int j=0; j<newCapacity; j++)
	{
		newTab[j]=0;
	}

	threshold = (int)(newCapacity * loadFactor);
	table = newTab;

	for (int i=oldCapacity; i-->0;) 
	{
		for (Entry* old=oldTab[i]; old!=0; )
		{
			Entry* e = old;
			old = old->next;
			int index = e->hash % newCapacity;
			e->next = newTab[index];
			newTab[index] = e;
		}
	}	
}

int HashTable::HashCode(string key) 
{
	int hash=0;
	int len = key.size();
	
	for(int i = 0; i < len; i++) {
		hash = 31*hash + key.at(i);
	}	
	return hash;
}

void main(){
	
	HashTable hash;
	string key;
	ValueType value,oldValue;

	while( cin>>key>>value )
	{
		hash.Put(key,value,oldValue);
		cout<<*(hash.Get(key));
	}	

}