Exploring Hashing Algorithms and Hashtables in JavaScript

The code below, when executed, implements a hashtable in JavaScript, inserts several values into it, and then reads them back out. To see it in action, copy the code into an .html file and open that file in a web browser that runs JavaScript.

JavaScript obviously already has hashtables, and they work far more effectively and efficiently than this implementation.  The purpose of this code, therefore, is simply to illustrate in very general and simplified terms how hashtables and hashing functions actually work.

<html>
<body>
<script type='text/javascript'>

// main

function main()
{
	var keyValuePairsToAdd = 
	[
		[ "Name", 	"Peter Pearson" ],
		[ "Address", 	"123 Hash Street" ],
		[ "City", 	"Hashville" ],
		[ "State",	"NV" ],
		[ "ZIP",	"12345" ],		
	];

	var hashtable = new Hashtable();

	for (var i = 0; i < keyValuePairsToAdd.length; i++)
	{
		var keyValuePair = keyValuePairsToAdd[i];
		hashtable.addKeyAndValue(keyValuePair[0], keyValuePair[1]);
	}

	var outputText = "";

	for (var i = 0; i < keyValuePairsToAdd.length; i++)
	{
		var keyValuePair = keyValuePairsToAdd[i];
		var keyToGet = keyValuePair[0];
		var valueFromHashtableForKey = hashtable.getValueForKey(keyToGet);

		outputText += 
			"hashtable[" 
			+ keyToGet 
			+ "] is " 
			+ valueFromHashtableForKey 
			+ Constants.Newline; 
	}
	

	document.write(outputText);
}

// classes

function Constants()
{}
{
	Constants.BitsPerByte = 8;
	Constants.Newline = "<br />";
}

function Hasher()
{
	this.buildRandomPermutationTable();
}
{
	Hasher.prototype.buildRandomPermutationTable = function()
	{
		this.permutationTable = [];
		
		var uniqueValuesPerByte = Math.pow(2, Constants.BitsPerByte);

		for (var i = 0; i < uniqueValuesPerByte; i++)
		{
			var randomIndex = Math.floor
			(
				Math.random() 
				* this.permutationTable.length
			);

			this.permutationTable.splice(randomIndex, 0, i)
		}
	}

	Hasher.prototype.hashString = function(stringToHash)
	{
		// Using the Pearson hashing algorithm.
		// This code is adapted from pseudocode found at the URL
		// "https://en.wikipedia.org/wiki/Pearson_hashing".

		var returnValue = 0;
	
		for (var i = 0; i < stringToHash.length; i++)
		{
			// hack
			// This assumes the character code values are < 256,
			// which is not necessarily true for Unicode.

			var characterFromStringAsByte = stringToHash.charCodeAt(i);
	
			var index = (returnValue ^ characterFromStringAsByte);
			returnValue = this.permutationTable[index];
		}
	
		return returnValue;
	}
}

function Hashtable()
{
	this.hasher = new Hasher();
	this.buckets = [];
}
{
	Hashtable.prototype.addKeyAndValue = function(key, value)
	{
		var hashValueForKey = this.hasher.hashString(key);
		var bucket = this.buckets[hashValueForKey];
		if (bucket == null)
		{
			bucket = [];
			this.buckets[hashValueForKey] = bucket;
		}	

		var keyValuePair = [key, value];
	
		bucket.push(keyValuePair);	
	}

	Hashtable.prototype.getValueForKey = function(key)
	{
		var returnValue;

		var hashValueForKey = this.hasher.hashString(key);
		var bucket = this.buckets[hashValueForKey];

		if (bucket.length == 0)
		{
			returnValue = null;
		}
		else if (bucket.length == 1)
		{
			returnValue = bucket[0][1];
		}
		else
		{
			for (var i = 0; i < bucket.length; i++)
			{
				var keyValuePairFromBucket = bucket[i];
				if (keyValuePairFromBucket[0] == key)
				{
					returnValue = keyValuePairFromBucket[1];
					break;
				}
			}
		}

		return returnValue;
	}
}

// run

main();

</script>
</body>
</html>
This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s