5. Algorithm, Question, Explanation, Solution, at toptal.com : What is a Hash Table, and what is the average case and worst case time for each of its operations? How can we use this structure to find all anagrams in a dictionary? Use Python .
By: Chrysanthus Date Published: 30 Oct 2025
Meaning of Hash Table
A hash table is an array whose indexes are mapped from different sequences of text. The effective contents of the different array cells can be different (use of pointers in C). The different sequences of text are arbitrary; they are not from any list. The mapping of a sequence of text to an array index, is done by a hash function. This same hash function does the mapping for all the corresponding text sequences and array indexes.A hash table consists of key/value pairs. A key is the sequence of text. For the illustration in this article, the key is one string of letters, sorted in ascending order, and the value is a list of related words.
Accessing, inserting and deleting, each has an average time complexity of O(1). The worse case time complexity for each of these operations is O(N), where N is the number of elements in the Hash Table (array).
What is Anagram?
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. The original word or phrase is known as the subject of the anagram. Any word or phrase that exactly reproduces the letters in another order is an anagram.acer: acer acre care race
abekr: baker brake break kebar
aceehrst: cheaters hectares rechates recheats teachers
aabcdkrw: backward drawback
deeilnst: enlisted lintseed listened tinseled
adehrst: hardset dearths hardest hatreds threads trashed
aelmny: laymen meanly namely
amnopst: postman tampons topsman
einoprst: proteins pointers porniest repoints tropines
aeehrstw: wreathes weathers
Strategy
A function has to be written that returns a structure consisting of rows. The first element in the row is the subject or key for the rest of the row. All the elements in each row of the structure returned, are anagrams of one another. The first element in each row is detached from the rest of the elements in the row. In fact, the structure returned, is a hash table.For the program below, all the above words, except those in the first column, are considered as the dictionary. They are sent into the program in reverse order, beginning from weathers, then wreathes and then ending with acre and acre, in that order. They are sent as one array (one list). The output has to be the above table, with the first word in each row being the key of the returned hash table. The rest of the row is the corresponding list of anagrams. The key is the group of letters arranged alphabetically.
In PY the hash table to use is the ordered map data structure. This will order the keys in ascending order. The hash table is returned with the keys as shown in the table above. Each list will not necessarily be arranged in ascending order, in order to reduce the total running time of the whole function.
The algorithm function will operate as follows:
- Get the first word from the input array. Sort it by letters and use the sorted copy as a key in the hash table.
- Every word obtained from the input array (input list) is sorted first.
- It is then verified if the sorted group of letters (word) is already one of the keys in the hash table. If yes, the unsorted word is added to the list for its key. If no, the sorted word becomes a new key. In the algorithm function below, no time is used for this step (to search for a key).
The above algorithm continues until the end of the dictionary (end of input list).
The Program
The program is (read any comment as well):
from collections import defaultdict
def find_anagrams(words):
ordered_mp = defaultdict(list)
for word in words:
sorted_string_key = "".join(sorted(word))
# without searching for key,
ordered_mp[sorted_string_key].append(word)
return ordered_mp
#To call the function
words = [
'weathers', 'wreathes', 'tropines', 'repoints', 'porniest', 'pointers',
'proteins', 'topsman', 'tampons', 'postman', 'namely', 'meanly',
'laymen', 'trashed', 'threads', 'hatreds', 'hardest', 'dearths',
'hardset', 'tinseled', 'listened', 'lintseed', 'enlisted', 'backward',
'drawback', 'teachers', 'recheats', 'rechates', 'hectares', 'cheaters',
'kebar', 'break', 'brake', 'baker', 'race', 'care', 'acre', 'acer'
]
ht = find_anagrams(words)
for key, value_list in ht.items():
print(f"{key}: ", end="")
for word in value_list:
print(f"{word} ", end="")
print()
The output is:aabcdkrw: backward drawback
abekr: kebar break brake baker
aceehrst: teachers recheats rechates hectares cheaters
acer: race care acre acer
adehrst: trashed threads hatreds hardest dearths hardset
aeehrstw: weathers wreathes
aelmny: namely meanly laymen
amnopst: topsman tampons postman
deeilnst: tinseled listened lintseed enlisted
einoprst: tropines repoints porniest pointers proteins
Remarks
Only single words have been used in the above example. However, phrases can also be used in the place of words. Note that the space character is below 'a', 'A', and '0' in both ASCII and UTF-8 character code.The time complexity is obtained by multiplying the length of the given list, by the number of operations to sort the letters within a string (word). Let the length of the given list be N. Let the longest string length be L . Expect the time to sort a string to be L.log2L . So the time complexity for the find_anagrams() function is:
O(N.L.log2L)
No time is used to determine whether or not, a key is present in the hash table. The statement:
ordered_mp[sorted_string_key].append(word)
adds a key and its first string (with its arrayList), if the key is not present in the hash table. If the key is present, this same construct just adds the next string (word) to the end of the corresponding arrayList.The output may not be arranged vertically, as shown above.
Thanks for reading.