Hashtables

A hashtable is a special data structure that maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored. Hashtables are especially useful in programming because it is much faster to look up values in them as compared to other structures like lists or tuples. In this course we'll be exploring two types of hashtables: sets and dictionaries.

Sets

Sets can store many datapoints, just like lists and tuples, but cannot be indexed into because they have no particular order. Sets can be iterated over, however. 




Note that elements of sets are unique--even though we had three 1's in the original list 
	in the example above, the set only contains one.



Elements must also be immutable--they can't be changed after being created. 
	For instance, numbers, booleans, strings, and tuples are all immutable. 
	Lists are mutable--remember that we can add, remove, or change elements in it.





		







Again, sets are very useful because they run fast. 
	It takes much less time to determine if an element is in a set as compared to a list. 



Say we want to find the repeat elements of a list. 
	We could loop through and record all elements that have already occurred, 
	and if an element has occurred, we can add it to a new set.




















Dictionaries


Python dictionaries are very similar to actual dictionaries. 
	Each entry, known as a key, maps to a specific value. 
	Keys are stored like in a set--they must be immutable, and 
	end up being unique and unordered--but values can be anything.



For instance, we can create a dictionary of political connections. 











		

Suppose now we want to create a dictionary of connections of connections. 
	For example, Trump is connected with Trudeau and Putin, who are connected 
	with Merkel, Xi, and Trump. We want a new dictionary where the key of Trump 
	maps to a set containing Merkel and Xi.














Since the values in dictionaries are mutable, we can also directly modify them. 
	Let's say we have a list of people and want to make a dictionary mapping their names 
	to the number of times they show up in the list: