Scribd
Upload
25 views2 pages

Interview Camp: Level: Hard Generate A Good Hash Function For A String

This document describes using a polynomial hash function to generate a hash code for strings. It explains that each character's integer value is multiplied by increasing powers of a prime number, like 53, and summed. Pseudocode provides a hash(string) method that loops through each character, multiplying the running hash by x and adding the character value. The method returns the final hash and runs in O(n) time with O(1) space.

Uploaded by

abhi74
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
25 views2 pages

Interview Camp: Level: Hard Generate A Good Hash Function For A String

This document describes using a polynomial hash function to generate a hash code for strings. It explains that each character's integer value is multiplied by increasing powers of a prime number, like 53, and summed. Pseudocode provides a hash(string) method that loops through each character, multiplying the running hash by x and adding the character value. The method returns the final hash and runs in O(n) time with O(1) space.

Uploaded by

abhi74
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

 

Interview Camp 

 
Technique: Polynomial Hash Function 

Level: Hard 

Generate a good hash function for a String. 


 
Questions to Clarify: 

Solution: 
Hash functions are basic building blocks of hash based data structures. Interviewers are generally 
impressed if you have knowledge of good hash functions. 
 
For strings, we generate hash functions as a polynomial: 
 
hash("goat") => 'g'.x​3​ + 'o'.x​2​ + 'a'.x + 't' 
 
Note that these are the integer values of the characters. 
We need to assign an integer value to ​x​. Prime numbers are known to make good values for ​x​.  
The mathematical proof of this is beyond the scope of an interview. We use 53 in the code below. 
 
We run a simple for loop to calculate the hash: 
 
for i -> 0 to s.length - 1
hash = hash * x + s[i];

Pseudocode: 
(Note: Never write pseudocode in an actual interview. Unless you're writing a few
lines quickly to plan out your solution. Your actual solution should be in a real
language and use good syntax.)
 
find hash(string s)
int hash = 0, x = 53;
for i -> 0 to s.length - 1
hash = hash * x + s[i];
return hash;

Test Cases: 
Edge Cases: empty string, null string 
Base Cases: string with 1 character 
Regular Cases: try same string twice, should return the same hash code 

Time Complexity: O(n) 

Space Complexity: O(1) 

 
 
© ​2017 Interview Camp (interviewcamp.io) 
 
Interview Camp 

 
public static int hash(String str) {
char[] ch = str.toCharArray();
int hash = 0, x = 53;
for (int i = 0; i < ch.length; i++) {
hash = hash * x + ch[i];
}
return hash;
}
 

 
 
© ​2017 Interview Camp (interviewcamp.io) 

You might also like