%%bigquery df
CREATE TEMPORARY FUNCTION hashed(airport STRING, numbuckets INT64) AS (
   ABS(MOD(FARM_FINGERPRINT(airport), numbuckets))
);

WITH airports AS (
SELECT 
   DISTINCT(departure_airport)
FROM `bigquery-samples.airline_ontime_data.flights`
)

SELECT 
   departure_airport,
   hashed(departure_airport, 3) AS hash3,
   hashed(departure_airport, 10) AS hash10,
   hashed(departure_airport, 1000) AS hash1000,
FROM airports

df.head(n=10)

len(df)

"""
Explanation: Hashed Features Design Pattern
Solves problems related to not knowing the vocabulary of a categorical variable beforehand.
End of explanation
"""


%%bigquery
SELECT 
   departure_airport, COUNT(1) AS num_flights
FROM `bigquery-samples.airline_ontime_data.flights`
GROUP BY departure_airport
ORDER BY num_flights ASC
LIMIT 10

"""
Explanation: Some airports had very few flights
End of explanation
"""


import pandas as pd

def calc_collision_prob(num_total, num_hash):
    no_collision_prob = 1.0
    for i in range(num_total):
        # i of the previous buckets is occupied now
        collision_likelihood = float(i) / num_hash
        no_collision_prob *= (1 - collision_likelihood)
    return 1 - no_collision_prob


data = []
for num_hash in [3, 10, 100, 1000, 10000, 100000]:
    data.append([num_hash, 
                 len(df)/num_hash, 
                 calc_collision_prob(len(df), num_hash)
                ])
prob = pd.DataFrame(data, columns=['num_hash_buckets', 'entries_per_bucket', 'collision_prob'])
prob

calc_collision_prob(5, 1000) # num_hash >> num_total

"""
Explanation: Likelihood of collision
To calculate the likelihood of collision, consider that previous N entries don't collide.
Even with 100,000 hash-length, the chance of a collision is 45%. So, hashed columns should never be used if collisions will cause problems.
End of explanation
"""


%%bigquery
CREATE TEMPORARY FUNCTION hashed(airport STRING, numbuckets INT64) AS (
   ABS(MOD(FARM_FINGERPRINT(airport), numbuckets))
);

WITH airports AS (
SELECT 
   departure_airport, COUNT(1) AS num_flights
FROM `bigquery-samples.airline_ontime_data.flights`
GROUP BY departure_airport 
)

SELECT 
   departure_airport, num_flights
FROM airports
WHERE hashed(departure_airport, 100) = hashed('ORD', 100)

"""
Explanation: Airports that share hash buckets
Which airports have the same hashbucket as Chicago, assuming 100 hash buckets?
End of explanation
"""


