Hash, hash table

[Sidro]

HI,
CAn anyone explain and maybe give a small example of a hashing and a hash function? Lets say I have a string called "harry Potter", how would I use that as a key?Also whats Mapping.What is Collision and how would I deal with it? Big Thankx in advance!

 

[palbano]

>> Lets say I have a string called "harry Potter", how
>> would I use that as a key?

It's all built into the STL.


class foo{
public:
foo( const char* who, int whoid)
: name(who), id(whoid){}

std::string name;
int id;
};

std::map< string, foo> myfoohash; // hash map instance
foo harryp(&quot;harry Potter&quot;, 201); // foo instance
myfoohash[ harryp.name] = foo; // map foo using the hash of name

 

[chipperMDW]

The STL map is NOT a hash map; it's a binary tree. There's no hash table/map currently in the STL, although SGI has nonstandard extensions, and there almost certainly will be a hashing data structure in the next Standard.


Read this thread for info on how hash tables/maps work.

thread205-400144

 

[suicidal]

Indeed, <map> is not a hash table.

<<What's mapping
It is designed for storing and retrieving (key,value) pairs quickly. It uses a hash function on the key. Bassicly, the value is stored in an array at the result of the hash function. But that result is not unique. So each entry in that array is actually a list of items for which the result of the has function produces the same value. That's where collision kicks in: same hash result. This can get very nasty. Suppose you want to store a phone book in a hash table of 100 entries (so, the hash function returns results between 0 and 99). This table is too small and you will get collisions all the time.
Retrieving becomes very slow: you have to cylce through a list of similar hash results to find the result you want.

A bad hash function (i.e. one that returns 1 all the time) has the similar result.

In 'C++, the programming language' there is a paragraph on building a hash map.

P.S. Now I see there is a link on hashing in the previous post. I'll post this anyway.

 

[Zyrenthian]

YOu can use CMap<CString,CString,int,int> if you add the following code (end of post) to your project. Please keep all the author information in tact. I needed to do just what you were doing but the MFC CMap does not support mapping. I found this on the internet and removed some of the stuff I did not need (i.e. CMapEx). Searching on codeguru for CMapEx will result in the below as well.

Matt


CODE
=======================================================================================

//=========================================================
//	TITLE:	Missing API
//				for WinNT, MSVC 6.0, MFC 6.00
//				Copyright (C) Matrix Baltic Software
//				Vilnius, Lithuania
//
//	AUTHOR:		Audrius Vasiliauskas
// 
//	NOTES:		Added special hashkey for string maps
//
// I needed CMap to support the mapping of CString to int and I found this
// on [URL unfurl="true"]www.codeguru.com[/URL]  Seems to work :-)
// MGS
//
//=========================================================

#ifndef __MISSING_API_H__
#define __MISSING_API_H__

#if _MSC_VER < 0x0600
	#pragma warning(disable : 4786) //identifier was truncated to '255' characters in the debug information
#endif

#ifndef __AFXTEMPL_H__
	#include <afxtempl.h>
#endif


////////////////////////////////////////////////////////////////////////////
//
// Special Hashkey for String Maps
//

template<> 
inline UINT AFXAPI HashKey<CString> (CString strKey)
{
	LPCTSTR key = strKey;
	UINT nHash = 0;
	while (*key)
	{
		nHash = (nHash<<5) + nHash + *key++;
	}
	return nHash;
}

template<> 
inline UINT AFXAPI HashKey<CString&> (CString& strKey)
{
	LPCTSTR key = strKey;
	UINT nHash = 0;
	while (*key)
	{
		nHash = (nHash<<5) + nHash + *key++;
	}
	return nHash;
}

#endif

 

[suicidal]

This is NOT a hash table, just a (CString,int) map. The STL map does support a <string,int> map without the need for writing functions yourself.

 

[palbano]

suicidal,chipperMDW,

Yup! My bad. That was my brain on Java LOL

Thanks for having my back.

-pete