Data types, hashing | Rustam Zokirov

Data types in Python
Sorting list/tuple/dictionaries
Dictionary in Python
What can we use as a key in dict?
Hashing and hash functions
Collections
String formatting
Resources

Data types in Python

Mutable and immutable types?

Mutable — points to the same object `id()`	Immutable — creates new object when we modify
list	None
set	bool: True, False
dict	int, float
bytearray	str
	tuple
	frozenset
	bytes (integer in range 0 ≤ x ≤ 255)

Mutable and immutable types as function argument?

When mutable is argument to function → python does call by object reference.
Immutable object → python “switches” to call by value (creates a new string object to hold the newly created object).

Coding exercises

‣

Tricky questions

# QUESTION 1: default argument value is mutable. 

dеf append(list=[], value=0):
    list.append(value)
    print(list)
    return list

appеnd(['a','b'], 2) # # ['a', 'b', 2]

# calling with no arg uses default list value which is empty list

append() # [0], default argument is evaluated only once when function is defined

"""
what happens when we AGAIN call append with no arg? 
When the default value for a function argument is an expression, the expression is evaluated only once, not every time the function is called.
"""
append() # [0, 1]


# QUESTION 1a: How we may modify the implementation of the ‘append’ method in the previous question to avoid the undesirable behavior described there?
def append(list=None):
     if list is None:
         list = []
     list.append(len(list))
     return list

append() # [0]
append() # [0]

# QUESTION: What will be result?

>>> # INITIALIZING AN ARRAY -- METHOD 1
>>> x = [[1,2,3,4]] * 3
>>> x
[[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]
>>>
>>> # INITIALIZING AN ARRAY -- METHOD 2
>>> y = [[1,2,3,4] for _ in range(3)]
>>> y
[[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]
>>>
>>> # WHICH METHOD SHOULD YOU USE AND WHY?

Answer:
Method 2 produces, as you would expect, an array of 3 elements,
each of which is itself an independent 4-element array.

In method 1, however, the members of the array all point to the same object. 
This can lead to what is most likely unanticipated and undesired behavior.

>>> # MODIFYING THE x ARRAY FROM THE PRIOR CODE SNIPPET:
>>> x[0][3] = 99
>>> x
[[1, 2, 3, 99], [1, 2, 3, 99], [1, 2, 3, 99]]
>>> # UH-OH, DON’T THINK YOU WANTED THAT TO HAPPEN!
...
>>>
>>> # MODIFYING THE y ARRAY FROM THE PRIOR CODE SNIPPET:
>>> y[0][3] = 99
>>> y
[[1, 2, 3, 99], [1, 2, 3, 4], [1, 2, 3, 4]]
>>> # THAT’S MORE LIKE WHAT YOU EXPECTED!

# Problem: assigning mutable object as a value in dict

dict_ = {}
list_ = [1,2,3,4,5]
dict_[lеn(list_)] = list_
list_.clear() 
# dict_ with key 5 will be empty. Need to change 3rd line to list_.copy()

# Problem: appending to list which is inside the immutable tuple

a = (1, 2, [3, 4, 5])
a[2].append(6) # (1, 2, [3, 4, 5, 6])
a[2] += [7] # (1, 2, [3, 4, 5, 6, 7]) and exception will be thrown (TypeError: 'tuple' object does not support item assignment)

"""
a[2] += [7]: Evaluates under the hood as:

# Step 1: Modifies the list object in place
temp = a[2].__iadd__([7])

# Step 2: Attempts to assign the result back to the tuple index
a[2] = temp  # Throws TypeError: 'tuple' object does not support item assignment
"""

# QUESTION

def func(l=[]):
	l = l + [123]
	print(l)
	return l
	 
func() # [123]
func() # [123]



def func(l=[]):
	l += [123]
	print(l)
	return l
	 
func() # [123]
func() # [123, 123]

# .append() is similar to second version, in the first version we are creating the new object with assigning

Sorting list/tuple/dictionaries

dict(sorted(count_dict.items(), key=lambda x:x[1]))

Dictionary in Python

Python dicts are hash tables. Keys can be None, and keys should consist of immutable objects. Each row takes up 24 bytes.

If there is a collision, Python uses open addressing.

After 5 key-values are stored, when adding another key-value pair, the probability of hash collisions is too large, so the dictionary is doubled in size. It now takes 240 bytes of memory.

The common strategies to resolve collisions in a hash table are:

Open addressing - if the bucket you should use is busy, you just keep searching for a new bucket to be used, when deleting collided element will be also deleted.
Separate chaining - diving into buckets.

‣

Coding exercises

What can we use as a key in dict?

‣

Answer

A dictionary’s keys are almost arbitrary values. Values that are not hashable, that is, values containing lists, dictionaries or other mutable types (that are compared by value rather than by object identity) may NOT be used as keys.

An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() or __cmp__() method). Hashable objects which compare equal must have the same hash value.

By default, the __hash__ uses the object’s identity and the __eq__ returns True if two objects are the same.

Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally.

Just immutable types are hashable in Python. In case you are using an immutable container (like a tuple) also the content should be immutable to be hashable. Tuple containing the list inside it, is not allowed.
However, every custom defined object is hashable in Python and by default its hash is derived from it’s id. That means that two different instance of a same class, by default have different hashes, as shown in the following example

Why only for immutable objects we can apply hashing? The short answer is that if the object's value changes, then the hash must also change since hashes are based on values. However, if the object's value changes after it's used as a key in a dictionary, the hash will no longer refer to the correct bucket in the dictionary for that key

class without the hash and eq dunders, Class objects are mutable in Python, but we can use them as dict keys cuz "object" class has _hash and _eq. It's like when you pass by value

class MyClass:
    def __init__(self, foo, bar):
        self.foo = foo
        self.bar = bar
        
    def __eq__(self, other): 
        if not isinstance(other, MyClass):
            # don't attempt to compare against unrelated types
            return NotImplemented
        return self.foo == other.foo and self.bar == other.bar

Hashing and hash functions

‣

Hash function

‣

hashable()

Collections

namedtupes, defaultdicts, Counter

String formatting

>>> name = 'IBM'
>>> shares = 100
>>> price = 91.1
>>> f'{name:>10s} {shares:>10d} {price:>10.2f}'
'       IBM        100      91.10'

>>> for name, shares, price, change in report:
        print(f'{name:>10s} {shares:>10d} {price:>10.2f} {change:>10.2f}')

          AA        100       9.22     -22.98
         IBM         50     106.28      15.18
         CAT        150      35.46     -47.98
        MSFT        200      20.89     -30.34
...
>>>

d       Decimal integer
b       Binary integer
x       Hexadecimal integer
f       Float as [-]m.dddddd
e       Float as [-]m.dddddde+-xx
g       Float, but selective use of E notation
s       String
c       Character (from integer)

:>10d   Integer right aligned in 10-character field
:<10d   Integer left aligned in 10-character field
:^10d   Integer centered in 10-character field
:0.2f   Float with 2 digit precision

Resources

Mutable and immutable, call by reference and call by value

Dictionary