The fifth chapter tellsHash table，It is implemented as a dictionary in Python and consists of hash functions and arrays. It has the advantages of both arrays and linked lists, avoiding duplication, and can simulate mapping relations.
hash table implementation
Hash function + array to achieve the hash table
conflict
Different inputs are mapped to the same output, which is conflict. How to handle conflicts? Create a linked list on the same output.
fill factor”
The hash table contains the number of elements / positions, and the fill factor measures how many positions in the hash table are empty. Once the fill factor is greater than 0.7, the length of the hash table is adjusted.
find
Create a telephone directory
phone_book = dict()
phone_book = {}
phone_book['jenny'] = 8675309
phone_book['emergency'] = 911
print(phone_book['jenny'])
voted = {}
def check_voter(name):
if voted.get(name):
print('kick them out!')
else:
voted[name] = True
print('let them vote!')
check_voter('tom')
check_voter('mike')
check_voter('mike')
cache = {}
def get_page(url):
if cache.get(url):
return cache[url]
else:
data = get_data_from_server(url)
cache[url] = data
return data
Create a telephone directory
phone_book = dict()
phone_book = {}
phone_book['jenny'] = 8675309
phone_book['emergency'] = 911
print(phone_book['jenny'])voted = {}
def check_voter(name):
if voted.get(name):
print('kick them out!')
else:
voted[name] = True
print('let them vote!')
check_voter('tom')
check_voter('mike')
check_voter('mike')