Что происходит в следующем коде и чем отличаются его версии?
Версия 1:
"""
<h1><b>Задание 2.1</b><br>Постройте случайные хеш-функции F[2, 32] → F[2, n] для n ∈ {8, 16, 32} вида A[n×32] × x + b, где x – ключ из потока.</h1>
"""
import numpy as np

def generate_random_hash_function(n):
    # Генерируем случайную матрицу A[n×32] и вектор b размера n
    A = np.random.randint(0, 2, size=(n, 32))  # 0 или 1
    b = np.random.randint(0, 2, size=n)  # 0 или 1
    return A, b

def hash_function(A, b, x):
    # x должен быть 32-битным значением
    x_bits = np.array([(x >> i) & 1 for i in range(32)])  # Преобразуем x в массив битов

    r = np.zeros(A.shape[0], dtype=int)  # Результирующий массив битов
    for i in range(A.shape[0]):
        # Подсчитываем четность количества единичных бит в Ai & x
        parity = (A[i] & x_bits).sum() % 2  # вычисляем четность
        r[i] = parity  # Устанавливаем i-ый бит результата

    # Возвращаем r XOR b
    return r ^ b

# Генерируем данные
def generate_data_without_deletion(distribution, size):
    if distribution == 'uniform':
        return np.random.randint(0, 2**32, size=size)
    elif distribution == 'normal':
        return np.random.normal(loc=2**31, scale=2**10, size=size).astype(np.int32) % (2**32)

def linear_congruential_generator(a, c, m, seed, size, lower_bound, upper_bound):
    numbers = []
    current_seed = seed

    for _ in range(size):
        current_seed = (a * current_seed + c) % m # [0...m)
        random_number = current_seed / m # [0...1)
        # to range [lower_bound, upper_bound]
        scaled_number = lower_bound + random_number * (upper_bound - lower_bound)
        numbers.append((scaled_number))

    return numbers

def generate_uniform_random_numbers(size=100000, lower_bound=1, upper_bound=1000000):
    # linear congruential generator parameters
    a = 1664525    # 48271
    c = 1013904223 # 0
    m = 2**32

    seed = 12345

    return linear_congruential_generator(a, c, m, seed, size, lower_bound, upper_bound)

# Функция для генерации потока данных без удаления
def generate_data_without_deletion(distribution_type, size):
    if distribution_type == 'uniform':
        return generate_uniform_random_numbers(size)
    '''elif distribution_type == 'normal':
        return generate_normal_random_numbers(size, mean=500000, std_dev=100000)
    elif distribution_type == 'zipf':
        return generate_zipf_random_numbers(size, N=1000000, s=1.5)'''

# Пример использования
uniform_data_without_deletion = generate_data_without_deletion('uniform', size=1000)

# Создаем хеш-функцию для n = 8
A, b = generate_random_hash_function(8)

# Применяем хеш-функцию ко всем ключам
hashed_values = [hash_function(A, b, int(x)) for x in uniform_data_without_deletion]

# Выводим несколько результатов
for i in range(5):
    print(f"Key: {uniform_data_without_deletion[i]}, Hash: {hashed_values[i]}")

"""<h1><b>Задание 2.2</b><br>
Для тестовых потоков, посчитайте количество коллизий для полученных хеш-функций.</h1>
"""

from collections import Counter

def count_collisions(data, A, b):
    hashes = [tuple(hash_function(A, b, int(x))) for x in data]  # Вычисляем хеши для всех ключей
    hash_counts = Counter(hashes)  # Подсчитываем количество уникальных хешей
    collisions = 0

    # Считаем количество коллизий
    for count in hash_counts.values():
        if count > 1:
            collisions += count * (count - 1) // 2  # Количество пар (k * (k-1) / 2)

    return collisions

# Подсчитываем коллизии
num_collisions = count_collisions(uniform_data_without_deletion, A, b)

print(f"Number of collisions: {num_collisions}")

Версия 2:
"""
<h1><b>Задание 2.1</b><br>Постройте случайные хеш-функции F[2, 32] → F[2, n] для n ∈ {8, 16, 32} вида A[n×32] × x + b, где x – ключ из потока.</h1>
"""
import numpy as np

def generate_random_hash_function(n):
    #A = np.random.randint(0, 2, size=(n, 32))  # random binary matrix [n×32]

    A = [random.getrandbits(32) for i in range(n)]

    #b = np.random.randint(0, 2, size=n)  # random binary vector [n]
    b = random.getrandbits(n)
    return A, b

def hash_function(A, b, x):
    # x должен быть 32-битным значением
    #x_bits = np.array([(x >> i) & 1 for i in range(32)])  # bit extraction
    x_bits = [ (bool((x & i).bit_count()) % 2) for i in A]
    #print(x_bits)

    #r = np.zeros(A.shape[0], dtype=int)  # result bit array
    r0 = 0
    # fir each row of mtrx A
    '''for i in range(A.shape[0]):
        # Calculate the parity of the number of 1-bits in Ai & x
        parity = (A[i] & x_bits).sum() % 2
        r[i] = parity'''

    #print()
    for i in x_bits:
        r0 = (r0 << 1) | i

    #print("r0", r0)

    # r XOR b (if b is 1, then ~r)
    return r0 ^ b

import random
A, b = generate_random_hash_function(8)
hashes = hash_function(A, random.getrandbits(8), 24)
print(hashes)

def linear_congruential_generator(a, c, m, seed, size, lower_bound, upper_bound):
    numbers = []
    current_seed = seed

    for _ in range(size):
        current_seed = (a * current_seed + c) % m # [0...m)
        random_number = current_seed / m # [0...1)
        # to range [lower_bound, upper_bound]
        scaled_number = lower_bound + random_number * (upper_bound - lower_bound)
        numbers.append((scaled_number))

    return numbers

def generate_uniform_random_numbers(size=100000, lower_bound=1, upper_bound=1000000):
    # linear congruential generator parameters
    a = 1664525    # 48271
    c = 1013904223 # 0
    m = 2**32

    seed = 12345

    return linear_congruential_generator(a, c, m, seed, size, lower_bound, upper_bound)

def generate_normal_random_numbers(size, mean, std_dev):
    uniform_random_pairs = generate_uniform_random_numbers(size * 2, lower_bound=0, upper_bound=1)
    random_numbers = []

    for i in range(0, size * 2, 2):
        x = uniform_random_pairs[i]  # First uniform random number
        y = uniform_random_pairs[i + 1]  # Second uniform random number

        # Applying the Box-Muller transform
        z0 = np.cos(2 * np.pi * x) * np.sqrt(-2 * np.log(y))
        z1 = np.sin(2 * np.pi * x) * np.sqrt(-2 * np.log(y))

        # Transform z0 and z1 to match the normal distribution
        random_numbers.append(mean + std_dev * z0)
        random_numbers.append(mean + std_dev * z1)

    return random_numbers[:size]

def generate_zipf_random_numbers(size, N, s):
    # Calculate H(N, s)
    H_N_s = sum(1 / (n ** s) for n in range(1, N + 1))

    # Compute cumulative probabilities
    cumulative_probabilities = np.zeros(N)
    cumulative_probabilities[0] = 1 / (1 ** s) / H_N_s  # f(1)

    for k in range(2, N + 1):
        cumulative_probabilities[k - 1] = cumulative_probabilities[k - 2] + (1 / (k ** s)) / H_N_s

    # Generate uniform random numbers between 0 and 1
    uniform_randoms = generate_uniform_random_numbers(size=size, lower_bound=0, upper_bound=1)
    #uniform_randoms = np.random.uniform(0, 1, size)

    # convert uniformly distributed random numbers into samples that follow the Zipf distribution
    samples = np.searchsorted(cumulative_probabilities, uniform_randoms) + 1

    return samples

def generate_data_without_deletion(distribution_type, size):
    if distribution_type == 'uniform':
        return generate_uniform_random_numbers(size)
    elif distribution_type == 'normal':
        return generate_normal_random_numbers(size, mean=500000, std_dev=100000)
    elif distribution_type == 'zipf':
        return generate_zipf_random_numbers(size, N=1000000, s=1.5)

uniform_data_without_deletion = generate_data_without_deletion('uniform', size=10)

# hash for n = 8
A, b = generate_random_hash_function(8) # (8 rows and 32 columns)

# apply hash
hashed_values = [hash_function(A, b, int(x)) for x in uniform_data_without_deletion]

for i in range(5):
    print(f"Key: {uniform_data_without_deletion[i]}, Hash: {hashed_values[i]}")

normal_data_without_deletion = generate_data_without_deletion('normal', size=10)

# hash for n = 32
A, b = generate_random_hash_function(32) # (32 rows and 32 columns)

# apply hash
hashed_values = [hash_function(A, b, int(x)) for x in normal_data_without_deletion]

for i in range(5):
    print(f"Key: {normal_data_without_deletion[i]}, Hash: {hashed_values[i]}")

zipf_data_without_deletion = generate_data_without_deletion('zipf', size=1000)

# hash for n = 16
A, b = generate_random_hash_function(16) # (16 rows and 32 columns)

# apply hash
hashed_values = [hash_function(A, b, int(x)) for x in zipf_data_without_deletion]

for i in range(5):
    print(f"Key: {zipf_data_without_deletion[i]}, Hash: {hashed_values[i]}")

"""<h1><b>Задание 2.2</b><br>
Для тестовых потоков, посчитайте количество коллизий для полученных хеш-функций.</h1>
"""

from collections import Counter

def count_collisions(data, A, b):

    A, b = generate_random_hash_function(32)

    hashes = [(hash_function(A, b, int(x))) for x in [1,2,3,400,37,111, 910029.60, 940629.6037318874]]
    print(hashes)
    #hash_counts = Counter(hashes)  # dict of hashes
    #collisions = 0

    #print("Hashes: ", hashes)
    #print("hash_counts: ", hash_counts)
    #print("all unique hashes: ", hash_counts.keys())
    #print("hash_counts (nums): ", hash_counts.values())
    #print(f"Number of hashes: ", len(hash_counts.keys()))
    #print(f"Number of collisions: {num_collisions}")



    ''' for count in hash_counts.values():
        if count > 1: # if collision occures
            collisions += 1 #count * (count - 1) // 2  # (k * (k-1) / 2)
    '''
    return len(set(data)) - len(set(hashes))

A, b = generate_random_hash_function(8)

uniform_data_without_deletion = generate_data_without_deletion('uniform', size=100)
num_collisions = count_collisions(uniform_data_without_deletion, A, b)

print(uniform_data_without_deletion)

print(f"Number of collisions: {num_collisions}")

A, b = generate_random_hash_function(16)

num_collisions = count_collisions(uniform_data_without_deletion, A, b)

print(f"Number of collisions: {num_collisions}")

A, b = generate_random_hash_function(32)

num_collisions = count_collisions(uniform_data_without_deletion, A, b)

print(f"Number of collisions: {num_collisions}")