Source code online books for professionals by professionals

BLaCK BOX: DICt aND Set
One technique covered in detail in most algorithm books, and usually taken for granted by python programmers, 
is hashing. hashing involves computing some often seemingly random integer value from an arbitrary object. this 
value can then be used, for example, as an index into an array (subject to some adjustments to make it fit the 
index range).
the standard hashing mechanism in python is available through the 
hash
 function, which calls the 
__hash__
 
method of an object:
 
>>> hash(42)
42
>>> hash("Hello, world!")
-1886531940
 
this is the mechanism that is used in dictionaries, which are implemented using so-called hash tables. sets 
are implemented using the same mechanism. the important thing is that the hash value can be constructed in 
essentially constant time. it’s constant with respect to the hash table size but linear as a function of the size of the 

---

Chapter 2 
■
 the BasiCs
24
object being hashed. if the array that is used behind the scenes is large enough, accessing it using a hash value 
is also 
Q(1) in the average case. the worst-case behavior is Q(n), unless we know the values beforehand and can 
write a custom hash function. still, hashing is extremely efficient in practice.
What this means to us is that accessing elements of a 
dict
 or 
set
 can be assumed to take constant expected 
time, which makes them highly useful building blocks for more complex structures and algorithms.
Note that the 
hash
 function is specifically used for use in hash tables. For other uses of hashing, such as in 
cryptography, there is the standard library module 
hashlib
.
Adjacency Lists and the Like
One of the most intuitive ways of implementing graphs is using adjacency lists. Basically, for each node, we can access 
a list (or set or other container or iterable) of its neighbors. Let’s take the simplest way of implementing this, assuming 
we have n nodes, numbered 0 . . . n–1.
Note
 
■
  Nodes can be any objects, of course, or have arbitrary labels or names. Using integers in the range 0 . . . n–1 
can make many implementations easier, though, because the node numbers can easily be used as indices.
Each adjacency (or neighbor) list is then just a list of such numbers, and we can place the lists themselves into 
a main list of size n, indexable by the node numbers. Usually, the ordering of these lists is arbitrary, so we’re really 
talking about using lists to implement adjacency sets. The term list in this context is primarily historical. In Python 
we’re lucky enough to have a separate set type, which in many cases is a more natural choice.
For an example that will be used to illustrate the various graph representations, see Figure 
2-3
.
c
b
a
d
e
f
g
h