Hash Table
Hash table is a common-used data structure in algorithms. It provides a best O(1) operation to search any element in the table. Here I mainly summarize the implementation and classical application of this data structure.
Implementation
The implementation of hash table mainly lies on two aspects: Hash Function and Collision Handling.
Hash Function
In simple terms, a Hash Function maps a big number or string to a small integer that can be used as index in hash table.
A good hash function should have such two properties:
- Efficiently Computable.
- Should uniformly distribute the keys.
Collision Handling
Sometimes two different keys may be mapped to the same index via hash function. Here is where we need to apply collision handling to. There are two ways to deal with it:
- Chaining: The idea is to make each cell of hash table point to a linked list of records that have same hash function value. Requires additional memory.
- Open Addressing: Each key is stored in the hash table itself and each table entry contains a record or NIL. We examine the table slots one by one until it is found or not existed at all.
Application
Get a appropriate hash function for hashing
1. Group Anagram
Question: Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note: For the return value, each inner list's elements must follow the lexicographic order. All inputs will be in lower-case.
Analysis&Solution: this question mainly concerns how to divide the given words in groups according to their constructing letters. At first I was thinking about constructing lists based on the hash table of their member letters. But that is too time consuming and the complexity will be O(n*n).
Then I got this solution from Google that we could get a key after sorting this word and construct the lists based on the key. Then the hash table will be efficiently utilized in this question. The easy code is stated below:
def groupAnagrams(strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
strdic = {}
for astr in strs:
sortstr = ''.join(sorted(astr))
if sortstr in strdic:
strdic[sortstr].append(astr)
else:
strdic[sortstr] = [astr]
result = []
for key in strdic:
result.append(sorted(strdic[key]))
return result
2. Group Shifted Strings
Question: Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
"abc" -> "bcd" -> ... -> "xyz"
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"], Return:
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]
Note: For the return value, each inner list's elements must follow the lexicographic order.
Analysis&Solution: Based on the thinking of last question, I thought of transforming every word into one word to a word key that sets 'a' as the start of the word, then construct the other letters according to the difference in the original word. Then we can easily got this solution:
def groupStrings(strings):
"""
:type strings: List[str]
:rtype: List[List[str]]
"""
hdic = {}
for string in strings:
trastr = transform(string)
if trastr in hdic:
hdic[trastr].append(string)
else:
hdic[trastr] = [string]
result = []
for string in hdic:
result.append(sorted(hdic[string]))
return result
def transform(string):
result = ""
for i in range(len(string)):
diff = ord(string[i]) - ord(string[0])
if diff < 0:
diff += 26
result += str(97 + diff)
return result
Use hash table to judge circle
1. Fraction to Recurring Decimal
Question: Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".
Analysis&Solution: At first I did not figure out a suitable solution to judge the recurring decimals in the result. Then I found that hash table could do this function for me. Because if any previous remain of division occurs again, it implies that the sequence will repeat. Then we could get this code below:
class Solution(object):
def fractionToDecimal(self, numerator, denominator):
"""
:type numerator: int
:type denominator: int
:rtype: str
"""
hdic, result = {}, ""
if numerator * denominator < 0:
result += "-"
numerator = abs(numerator)
denominator = abs(denominator)
result += str(numerator // denominator)
numerator %= denominator
if numerator == 0:
return result
else:
result += "."
ind = len(result)
while numerator != 0:
if not numerator in hdic:
hdic[numerator] = ind
division = (numerator * 10) // denominator
numerator = (numerator * 10) % denominator
result += str(division)
ind += 1
else:
circbgn = hdic[numerator]
result = result[:circbgn] + "(" + result[circbgn:] + ")"
break
return result
2. Happy Number
Question:Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
$$1^2 + 9^2 = 82$$
$$8^2 + 2^2=68 $$
$$6^2 + 8^2=100$$
$$1^2 + 0^2 + 0^2 = 1$$
Analysis&Solution: The thinking of this question is the same with last one. But I just thought about count the occurring times of any number to judge whether it is repeating or not. This complicated the solution and wasted more time. We could also use hash table to do this here.
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
hdic = {}
while not n in hdic:
hdic[n], temp = 1, 0
while n != 0:
temp += (n % 10) ** 2
n = n // 10
n = temp
if n == 1:
return True
else:
return False