<jupyter_start><jupyter_text>Hash functions and multiplanesA key point for the lookup using hash functions is the calculation of the hash key or bucket id that we assign for a given entry. In this notebook, we will cover:- Basic hash tables- Multiplanes- Random planes  Basic Hash TablesHash tables are data structures that allo indexing data to make lookup tasks more efficient. In this part, you will see the implementation of the simplest hash function.<jupyter_code>import numpy as np
import pprint
import matplotlib.pyplot as plt

pp = pprint.PrettyPrinter(indent=4)
# Procedure to plot and arrows that represents vectors with pyplot
def plot_vectors(vectors, colors=['k', 'b', 'r', 'm', 'c'], axes=None, fname='image.svg', ax=None):
    scale = 1
    scale_units = 'x'
    x_dir = []
    y_dir = []
    
    for i, vec in enumerate(vectors):
        x_dir.append(vec[0][0])
        y_dir.append(vec[0][1])
    
    if ax == None:
        fig, ax2 = plt.subplots()
    else:
        ax2 = ax
      
    if axes == None:
        x_axis = 2 + np.max(np.abs(x_dir))
        y_axis = 2 + np.max(np.abs(y_dir))
    else:
        x_axis = axes[0]
        y_axis = axes[1]
        
    ax2.axis([-x_axis, x_axis, -y_axis, y_axis])
        
    for i, vec in enumerate(vectors):
        ax2.arrow(0, 0, vec[0][0], vec[0][1], head_width=0.05 * x_axis, head_length=0.05 * y_axis, fc=colors[i], ec=colors[i])
    
    if ax == None:
        plt.show()
        fig.savefig(fname)<jupyter_output><empty_output><jupyter_text>In the next cell, we will define a straightforward hash function for integer numbers. The function will receive a list of integer numbers and the desired amount of buckets. The function will produce a hash table stored as a dictionary, where keys contain the hash keys, and the values will provicde the hashed elements of the input list.<jupyter_code>def basic_hash_table(value_l, n_buckets):
  def hash_function(value, n_buckets):
    return int(value) % n_buckets

  hash_table = {i:[] for i in range(n_buckets)}
  for value in value_l:
    hash_value = hash_function(value, n_buckets)
    hash_table[hash_value].append(value)
  return hash_table
value_l = [100, 10, 14, 17, 97]
hash_table_example = basic_hash_table(value_l, n_buckets=10)
pp.pprint(hash_table_example)<jupyter_output>{   0: [100, 10],
    1: [],
    2: [],
    3: [],
    4: [14],
    5: [],
    6: [],
    7: [17, 97],
    8: [],
    9: []}<jupyter_text>In this case, the bucket key must be the rightmost digit of each number.  PlanesMultiplanes hash functions are other type of hash functions. Multiplanes hash functions are based on the idea of numbering every single region that is formed by the intersection of n planes. In the following code, we shoe the most basic forms of the multiplanes principle. First, with a single plane:<jupyter_code>np.random.uniform(-2, 2, 2)
P = np.array([[1, 1]])
fig, ax1 = plt.subplots(figsize=(8, 8))
plot_vectors([P], axes=[2,2], ax=ax1)
for i in range(0, 10):
  v1 = np.array(np.random.uniform(-2, 2, 2))
  side_of_plane = np.sign(np.dot(P, v1.T))

  # color the points depending on the sign of the result of np.dot
  if side_of_plane == 1:
    ax1.plot([v1[0]], [v1[1]], 'bo')
  else:
    ax1.plot([v1[0]], [v1[1]], 'ro')<jupyter_output><empty_output><jupyter_text>The first thing to note is that the vector that defined the plane does not mark the boundary between the two sides of the plane. It marks the direction in which you will find the 'positive' side of the plane. Not intuitive at all!If we want to plot the separation plane, we need to plot a line that is perpendiculer to our vector P. We can get such a line using a $90^o$ rotation matrix.<jupyter_code>P = np.array([[1, 2]]) # Define a single plane. 
fig, ax1 = plt.subplots(figsize=(8, 8)) # Create a plot

PT = np.dot([[0, 1], [-1, 0]], P.T).T

plot_vectors([P], colors=['b'], axes=[2, 2], ax=ax1) # Plot the plane P as a vector

plot_vectors([PT * 4, PT * -4], colors=['k', 'K'], axes=[4, 4], ax=ax1)

# Plot  random points. 
for i in range(0, 10):
        v1 = np.array(np.random.uniform(-4, 4, 2)) # Get a pair of random numbers between -4 and 4 
        side_of_plane = np.sign(np.dot(P, v1.T)) 
        
        # Color the points depending on the sign of the result of np.dot(P, point.T)
        if side_of_plane == 1:
            ax1.plot([v1[0]], [v1[1]], 'bo') # Plot blue points
        else:
            ax1.plot([v1[0]], [v1[1]], 'ro') # Plot red points
P = np.array([[1, 1]])
v1 = np.array([[1, 2]])
v2 = np.array([[-1, 1]])
v3 = np.array([[-2, -1]])
np.dot(P, v1.T)
np.dot(P, v2.T)
np.dot(P, v3.T)
def side_of_plane(P, v):
  dotproduct = np.dot(P, v.T)
  sign_of_dot_product = np.sign(dotproduct)
  sign_of_dot_product_scalar = sign_of_dot_product.item()
  return sign_of_dot_product_scalar
side_of_plane(P, v1)
side_of_plane(P, v2) 
side_of_plane(P, v3)<jupyter_output><empty_output><jupyter_text>Hash function with multiples planesIn the following section, we are going to define a hash function with a list of three custom planes in 2D.<jupyter_code>P1 = np.array([[1, 1]])
P2 = np.array([[-1, 1]])
P3 = np.array([[-1, -1]])

P_l = [P1, P2, P3]

v = np.array([[2, 2]])<jupyter_output><empty_output><jupyter_text>The next function creates a hash value based on a set of planes. The output is a combination of the side of the plane where vector is located with respect to the collection of planes.We can think of this list of planes as a set of basic hash functions, each of which can produce only 1 or 0 as output.<jupyter_code>def hash_multi_plane(P_l, v):
  hash_value = 0
  for i, P in enumerate(P_l):
    sign = side_of_plane(P, v)
    if sign >=0:
      hash_value += 2 ** i
  return hash_value 
hash_multi_plane(P_l, v)<jupyter_output><empty_output><jupyter_text>Random Planes<jupyter_code>np.random.seed(0)
num_dimensions = 2
num_planes = 3
random_planes_matrix = np.random.normal(
    size=(num_planes, num_dimensions)
)
print(random_planes_matrix)
v = np.array([[2, 2]])
def side_of_plane_matrix(P, v):
  dotprod = np.dot(P, v.T)
  sign_dotprod = np.sign(dotprod)
  return sign_dotprod
sides_l = side_of_plane_matrix(random_planes_matrix, v)
sides_l
def hash_multi_plane_matrix(P, v, num_planes):
  sides_matrix = side_of_plane_matrix(P, v)
  hash_value = 0
  for i in range(num_planes):
    sign = sides_matrix[i].item()
    if sign >=0:
      hash_value += 2**i
  return hash_value 
hash_multi_plane_matrix(random_planes_matrix, v, num_planes)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1239605789959963, 'fraction_numerical': 0.026947951955651372, 'mean_word_length': 3.811111111111111, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '367638', 'license': 'Apache-2.0', 'n_tokens_mistral': 2427, 'n_tokens_neox': 2322, 'n_words': 754, 'path': 'deeplearning.ai/nlp/c1_w4_hashfunctions_multiplanes.ipynb', 'repo_name': 'martin-fabbri/colab-notebooks', 'size': '6494'}