Probability

🎲揉5次，不出现一个1的可能性是：(5/6)⁵

至少出现一次1的可能性就是：1 - (5/6)⁵

100个学生在一个教室，多大可能性这100个人中今天有人过生日?

答：1 - (364/365)¹⁰⁰

Hashing

chr()根据整数返回对应的字符，也就是讲ascii转换为字符

unichr()将整数返回成unicode字符

ord()将字符转换成ascii码

从为什么会出现hash讲起。

convert the key to an integer and then use that integer to index into a list, which can be done in constant time because values of any object can be easily converted to an integer.

因为如果把所有的string都转换成integer会很大，所以采取取余数的办法。但是这样会产生collison，这个collison是可以接受的。

We have collisions because a hash function is a many-to-one mapping. The whole point was to take a very large space and map each element in that space into a much smaller space.

把table变大，collison就会少，以空间换时间。

接下来看一下有多大的机率会产生collison。

import random


class intDict(object):
    """A dictionary with integer keys"""
    
    def __init__(self, numBuckets):
        """Create an empty dictionary"""
        self.buckets = []
        self.numBuckets = numBuckets
        for i in range(numBuckets):
            self.buckets.append([])
            
    def addEntry(self, dictKey, dictVal):
        """Assumes dictKey an int.  Adds an entry."""
        hashBucket = self.buckets[dictKey%self.numBuckets] #确定第几个bucket
        for i in range(len(hashBucket)): #遍历这个bucket中的元素
            if hashBucket[i][0] == dictKey: #如果有相同的key
                hashBucket[i] = (dictKey, dictVal) #就更新
                return #返回为空表示结束这个method并且不执行下面的命令
        hashBucket.append((dictKey, dictVal)) #如果检查过后该bucket没有collison，则把这个tuple添加到该bucket。
        
    def getValue(self, dictKey):
        """Assumes dictKey an int.  Returns entry associated
           with the key dictKey"""
        hashBucket = self.buckets[dictKey%self.numBuckets]
        for e in hashBucket:
            if e[0] == dictKey:
                return e[1]
        return None
    
    def __str__(self):
        res = ''
        for b in self.buckets:
            for t in b:
                res = res + str(t[0]) + ':' + str(t[1]) + ','
        return '{' + res[:-1] + '}' #res[:-1] removes the last comma

#有29个buckets，要塞20个东西进去，key是随机生成的。通过除以29得余数来确定index，也就是存入这29个当中的第几个bucket。

D = intDict(29) 
for i in range(20):
    #choose a random int in range(10**5)
    key = random.choice(range(10**5))
    D.addEntry(key, i)

print '\n', 'The buckets are:'
for hashBucket in D.buckets: #violates abstraction barrier
    print '  ', hashBucket

这时再print D，就会看到生成的结果。

>>> {59340:1,53628:10,94664:17,1981:19,85967:14,86490:8,52270:9,23272:13,6918:5,13704:6,85104:3,3266:11,64630:15,55438:18,61589:0,28358:2,72409:4,9567:7,76674:12,5653:16}

当我们说有n个buckets。要放K个东西进去。

放入第一个不可能有collison，因为所有的buckets都是空的。也就是说冲突的可能性是0。

当放第一个的时候，不冲突的可能性是1

当放第二个的时候，不冲突的可能性是(n-1)/n

当放第三个的时候，不冲突的可能性是(n-2)/n

当放第K个的时候，不冲突的可能性是(n-(K-1))/n

这时候，如果我们要问，如果把K个东西都放进去，出现冲突的可能性是多少。思考方法与先前说的生日问题一样。也就是说，只有两种可能，一种是冲突了，一种是没冲突，两者之和代表所有可能性，所以是1。

也就是说出现冲突的可能性＝ 1 －上述不肯能的乘积。

用代码表示：

def collision_prob(numBuckets, numInsertions):
    '''
    Given the number of buckets and the number of items to insert, 
    calculates the probability of a collision.
    '''
    prob = 1.0
    for i in range(1, numInsertions):
        prob = prob * ((numBuckets - i) / float(numBuckets))
    return 1 - prob

Source Code