Skip to main content

String Hashing

Learn String Hashing (Strings, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What is String Hashing? String hashing converts a string into a single number (a "hash") so two strings can be compared in O(1) instead of O(length) - useful for detecting duplicates, comparing substrings quickly, or as the key in a HashMap. A simple polynomial hash treats the string as a number in some base p : hash(s) = s[0]·p⁰ + s[1]·p¹ + ... + s[n-1]·pⁿ⁻&sup9; (mod M)

More lessons in Strings