Hashing is the process of taking characters and converting them to number. Hashing the integer value (usually integer) created from hashing. Used as the index for the hash table Hash function is the code used to conduct hashing.
* Valid means the function converts the same string to the same number every single time.
3.1 HF: Addition Example 1
Assume A=1, B=2, C=3, D=4, etc…
Input is BAD
HF(BAD) will return: 1 + 2 + 4 = 7
3.2 HF: Multiplication Example 1
Assume A=1, B=2, C=3, D=4, etc…
Input is BAD
HF(BAD) will return: 1 * 2 * 4 = 8
3.3 HF: Multiplication Example 2
Assume A=1, B=2, C=3, D=4, etc…
Input is DAB
HF(DAB) will return: 4 * 1 * 2 = 8
Note: BAD and DAB returned the same index value of 8. This issue needs and will be address later.
4. Thesaurus App - Part 1
Imagine creating a thesaurus_app when given a input_word (or key) it return a single synonym (or value)
Create hash_values (or indices to our array):
by hashing our input_word via
our hash_function
Create a letter_dict dictionary from some input (representing real world data):
key (at index): hash_value
value: synonym
Retrieve synonym by:
by hashing our input_word via our hash_function
using dict[hash_value]
4.1 Create letters_dict
Each dict key is the letter and each dict value is the letter’s place in the alphabet
thesaurus_arr = [None]*16# create empty thesaurusletters_dict = {chr(i): i -96for i inrange(97, 97+26)}print(letters_dict)
This hash_value will be the index in our thesaurus_dict.
def alphabet_multiplicative_hash_fn(input_word: str):# convert some string into hash_value by multiplying all letters value hash_value =1for character in input_word:# dict_val = dict[char] letter_val = letters_dict[character] hash_value *= letter_val # cumulative product: char1 * char2 ...return hash_value
I’ll add the feature to get our a synonym given a input_word and explore it’s time-complexity.
Also, how to deal with collisions. This is when are multiple entries at the same index of our dictionary. That is, the same hash value calculated for different words.