Quick Index
Basic Usage of Hash Function


A hash function converts a non-integer key (e.g., a string key) to a "hash code" (an integer).

Having an integer representation is useful for some algorithms (e.g., when it is desired to convert a non-integer key to an index).

Using a Hash Code Function
In this example we assume string objects understand the method "hashCode()".

The string key "asha@here.com" returns a hash code of -859259272 for the method "hashCode()".
let key = "asha@here.com";
let hc = key.hashCode();
//-859259272


String Hash Code Function Algorithm


Overview


Some languages will have a hash function built into some object types (e.g., Java has "hashCode()" on type "String").

In other cases, a hash function will need to be coded.

We next present a common hash function formula used for strings.

String Hash Function Formula


Formula
Here is a common hash function formula to compute the hash code of a string.

This can be implemented in any language.
s[0]*31^(n - 1) + s[1]*31^(n - 2) + ... + s[n - 1]

Where:
	"s[i]" is integer code of the ith character in string
	"n" is the length of the string
	"^" indicates exponentiation
	This calculation should use 32-bit signed integers (overflow is okay)
String Hash Function Samples
Here is a list of strings along with the computed hash code (using the formula from the previous step).
StringHash Code (Java)
EMPTY STRING0
foo101574
foofoo-1268874688
asofiaso-487121283
8967867-155975625
8708707078789781980649663
12348690
asha@here.com-859259272

Notes:
  • The Java hashCode function returns an "int" data type (four bytes). That is the reason for the negative hash codes, which are perfectly acceptable.
  • A JavaScript implmentation of the hashCode formula above will result in different hash codes because it uses a different number data type than Java. This difference is perfectly acceptable.


Java


Java's Built-In Hash Code Function
Java's String object provides a hashCode() method.
String string = "asha@hello.com";
int hashCode = string.hashCode();
System.out.printf("Hash code for \"%s\": %d%n",
			string, hashCode);
//Hash code for "asha@hello.com": -1638445808


JavaScript


Hash Function

In JavaScript, we need to code a hash function for the String object type as follows.

String.prototype.hashCode = function() {
	//TODO -- will not ruin your fun
	//implement algorithm from this page here
	//A number can be converted to a 32 bit signed integer via "int32 = num & num;"
}


Testing Hash Function

let log = console.log;
let s = 'foo';
log(`s: ${s} -- hashCode: ${s.hashCode()}`);


Integer Hash Code Function Algorithm


Function


The conversion from an integer key to a hash code is trivial.

The hashCode is simply the key.

hashCode = key

KeyHash Code
00
33
-8-8
1892341818923418
-91235198-91235198


Java


Java's Built-In Hash Code Function
Java's Integer object provides hashCode as shown here.

Note we must use an "Integer" (object), not a prim "int".
int hashCode;
Integer integer1 = Integer.valueOf(1003);
hashCode = integer1.hashCode();
System.out.printf("Hash code for %d: %d%n",
					integer1, hashCode);
//Hash code for 1003: 1003


JavaScript


Hash Function

In JavaScript, we need to code a hash function for the Number object type as follows.

Number.prototype.hashCode = function() {
	//This method assumes that String understands "hashCode"
	let n = this.valueOf();	//unwrap to prim
	if (Number.isInteger(n))
		return n
	else
		return ('' + n).hashCode();
}


Testing Hash Function

let log = console.log;
let n = 25;
log(`n: ${n} -- hashCode: ${n.hashCode()}`);

n = 25.82;
log(`n: ${n} -- hashCode: ${n.hashCode()}`);


Converting Hash Code To Index


Overview


We will now look at how to convert a hash code to an index for a given array.

Converting Hash Code to Array Index


Given Hash Code and Array Size
We are given:

	key = 'asha@here.com'
	hashCode = -859259272
	arraySize = 1000
Hash Code to Array Index
//Step 1 -- get hash code from key
let hashCode = key.hashCode();
//-859259272

//Step 2 -- convert hash code to absolute value to assure non-negative index
let index = convert hashCode to absolute value
//859259272

//Step 3 -- finally use the modulus (remainder) operator is valid index for given array size
index = index % arraySize
//272

//for our sample, the result is 272 (which is a valid index for an array of size 1000)

References














Navigation













Coding Fundamentals (Chapter 308 - 308 - Hashing)










Chapter 308 - 308 - Hashing Hash Code and Hash Function

Chapter Top Search Site TOC