xbe.at

Machine learning / Feature engineering and preprocessing

Hash Tables in Machine Learning with Python

10 min read

Introduction to Hash Tables

Hash tables are data structures that store key-value pairs and provide efficient insertion, deletion, and lookup operations. They are widely used in various applications, including caching, databases, and machine learning. In this slideshow, we will explore hash tables, their implementation in Python, and how they handle collisions.

# This is a simple implementation of a hash table in Python
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash(key)
        for item in self.table[index]:
            if item[0] == key:
                item[1] = value
                return
        self.table[index].append([key, value])

    def get(self, key):
        index = self.hash(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        raise KeyError(key)

Hash Functions

A hash function is a crucial component of a hash table. It maps keys to indexes within the hash table's array. In Python, the built-in hash() function can be used for this purpose. However, it's essential to ensure that the hash function distributes keys evenly across the table to avoid clustering and collisions.

def hash_function(key, size):
    return hash(key) % size

# Example usage
key = "hello"
table_size = 10
index = hash_function(key, table_size)
print(f"Index for '{key}' in a table of size {table_size} is {index}")

Handling Collisions: Separate Chaining

Collisions occur when two or more keys are mapped to the same index in the hash table. Separate chaining is a technique to handle collisions by storing key-value pairs in a linked list or array at each index of the hash table. This allows multiple key-value pairs to be stored at the same index.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash(key)
        self.table[index].append((key, value))

    def get(self, key):
        index = self.hash(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        raise KeyError(key)

Handling Collisions: Linear Probing

Linear probing is another technique for handling collisions in hash tables. When a collision occurs, the algorithm searches for the next available empty slot in the array by linearly probing the subsequent indexes until an empty slot is found or the entire table has been traversed.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash(key)
        for i in range(self.size):
            probe = (index + i) % self.size
            if self.table[probe] is None or self.table[probe][0] == key:
                self.table[probe] = (key, value)
                return
        raise ValueError("Hash table is full")

    def get(self, key):
        index = self.hash(key)
        for i in range(self.size):
            probe = (index + i) % self.size
            if self.table[probe] is None:
                raise KeyError(key)
            elif self.table[probe][0] == key:
                return self.table[probe][1]
        raise KeyError(key)

Handling Collisions: Quadratic Probing

Quadratic probing is a variation of linear probing, where the probing sequence is based on a quadratic function. This technique can help reduce clustering and provide better distribution of key-value pairs in the hash table.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash(key)
        for i in range(self.size):
            probe = (index + i**2) % self.size
            if self.table[probe] is None or self.table[probe][0] == key:
                self.table[probe] = (key, value)
                return
        raise ValueError("Hash table is full")

    def get(self, key):
        index = self.hash(key)
        for i in range(self.size):
            probe = (index + i**2) % self.size
            if self.table[probe] is None:
                raise KeyError(key)
            elif self.table[probe][0] == key:
                return self.table[probe][1]
        raise KeyError(key)

Handling Collisions: Double Hashing

Double hashing is a technique that uses a second hash function to determine the probing sequence when collisions occur. This helps distribute key-value pairs more evenly across the hash table and can improve performance.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash1(self, key):
        return hash(key) % self.size

    def hash2(self, key):
        return 1 + (hash(key) % (self.size - 1))

    def insert(self, key, value):
        index = self.hash1(key)
        for i in range(self.size):
            probe = (index + i * self.hash2(key)) % self.size
            if self.table[probe] is None or self.table[probe][0] == key:
                self.table[probe] = (key, value)
                return
        raise ValueError("Hash table is full")

    def get(self, key):
        index = self.hash1(key)
        for i in range(self.size):
            probe = (index + i * self.hash2(key)) % self.size
            if self.table[probe] is None:
                raise KeyError(key)
            elif self.table[probe][0] == key:
                return self.table[probe][1]
        raise KeyError(key)

Load Factor and Resizing

The load factor of a hash table is the ratio of the number of elements in the table to the size of the table. As the load factor increases, the probability of collisions also increases, which can degrade the performance of the hash table. To maintain efficient operations, the hash table can be resized when the load factor exceeds a certain threshold.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        self.num_elements = 0
        self.load_factor_threshold = 0.7

    def hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        if self.num_elements / self.size >= self.load_factor_threshold:
            self.resize(2 * self.size)

        # Insert the key-value pair
        # ...

    def resize(self, new_size):
        old_table = self.table
        self.table = [None] * new_size
        self.size = new_size
        self.num_elements = 0

        for item in old_table:
            if item is not None:
                self.insert(item[0], item[1])

Hash Table Performance Analysis

The performance of a hash table depends on the quality of the hash function and the load factor. With a good hash function that distributes keys evenly across the table, and a low load factor, the average time complexity for insertion, deletion, and lookup operations is O(1) in the average case. However, in the worst case, when all keys hash to the same index (clustering), the time complexity degrades to O(n), where n is the number of elements in the table.

# Insertion
def insert(self, key, value):
    index = self.hash(key)
    # Handling collisions (e.g., separate chaining)
    # ...
    # Average case: O(1)
    # Worst case: O(n)

# Lookup
def get(self, key):
    index = self.hash(key)
    # Handling collisions (e.g., separate chaining)
    # ...
    # Average case: O(1)
    # Worst case: O(n)

# Deletion
def delete(self, key):
    index = self.hash(key)
    # Handling collisions (e.g., separate chaining)
    # ...
    # Average case: O(1)
    # Worst case: O(n)

Hash Tables in Machine Learning

Hash tables are widely used in machine learning for various purposes, such as caching, feature hashing, and building associative data structures. For example, in feature hashing, high-dimensional sparse data is mapped to a lower-dimensional space using hash functions, enabling efficient storage and computation.

from sklearn.feature_extraction import FeatureHasher

# Example: Feature Hashing
data = [
    {'word': 'machine', 'count': 1},
    {'word': 'learning', 'count': 3},
    {'word': 'hash', 'count': 2},
    {'word': 'table', 'count': 1}
]

hasher = FeatureHasher(n_features=10)
X = hasher.transform(data)
print(X.toarray())

Hash Tables and Caching

Caching is a technique used to store and retrieve frequently accessed data efficiently. Hash tables are commonly used for implementing caches due to their constant-time lookup and insertion operations. In machine learning, caching can be used to store intermediate results, model parameters, or preprocessed data, improving overall performance.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.lru = []

    def get(self, key):
        if key not in self.cache:
            return -1
        self.lru.remove(key)
        self.lru.append(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.lru.remove(key)
        self.cache[key] = value
        self.lru.append(key)
        if len(self.cache) > self.capacity:
            evicted_key = self.lru.pop(0)
            del self.cache[evicted_key]

Hash Tables and Associative Data Structures

Associative data structures, such as dictionaries and sets, are commonly implemented using hash tables in Python. These data structures are widely used in machine learning for various tasks, such as data preprocessing, feature engineering, and model evaluation.

# Dictionary (hash table)
word_counts = {}
for document in documents:
    words = document.split()
    for word in words:
        if word in word_counts:
            word_counts[word] += 1
        else:
            word_counts[word] = 1

# Set (hash table)
unique_words = set()
for document in documents:
    words = document.split()
    unique_words.update(words)

Handling Large Data with Hash Tables

When working with large datasets in machine learning, hash tables can be used to efficiently store and process data. However, it's important to consider the memory requirements and potential collisions when using hash tables with large datasets. Techniques like bucketing, sharding, or external storage can be employed to handle large datasets effectively.

import pickle

class DiskHashTable:
    def __init__(self, file_path, size):
        self.file_path = file_path
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash(key)
        self.table[index].append((key, value))
        self.save_to_disk()

    def get(self, key):
        index = self.hash(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        raise KeyError(key)

    def save_to_disk(self):
        with open(self.file_path, 'wb') as file:
            pickle.dump(self.table, file)

    def load_from_disk(self):
        try:
            with open(self.file_path, 'rb') as file:
                self.table = pickle.load(file)
        except FileNotFoundError:
            self.table = [[] for _ in range(self.size)]

Hash Tables in Popular Machine Learning Libraries

Many popular machine learning libraries, such as scikit-learn, TensorFlow, and PyTorch, utilize hash tables internally for various purposes, such as feature hashing, caching, and data preprocessing. Understanding the underlying data structures and algorithms can help in optimizing and improving the performance of machine learning models and pipelines.

# Example: Feature Hashing in scikit-learn
from sklearn.feature_extraction import FeatureHasher

data = [
    {'word': 'machine', 'count': 1},
    {'word': 'learning', 'count': 3},
    {'word': 'hash', 'count': 2},
    {'word': 'table', 'count': 1}
]

hasher = FeatureHasher(n_features=10)
X = hasher.transform(data)
print(X.toarray())

Additional Resources

For more information and advanced topics related to hash tables and their applications in machine learning, you can refer to the following resources:

  • "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (Chapter 11: Hash Tables)
  • "Mining of Massive Datasets" by Leskovec, Rajaraman, and Ullman (Chapter 3: Hash Tables)
  • "Hashing for Parallel and Distributed Computing" (arXiv:1804.06422)
  • "Hash Tables: Theory and Practice" (arXiv:2109.08012)

ArXiv links:

Additional Resources

For more information and advanced topics related to hash tables and their applications in machine learning, you can refer to the following resources from ArXiv:

  1. "Hashing for Parallel and Distributed Computing" (arXiv:1804.06422)
    • Reference: P. Li, C. Meng, A. Natsev, A. Natsev, and J. R. Smith, "Hashing for Parallel and Distributed Computing," arXiv:1804.06422 [cs.DS], Apr. 2018.
    • URL: https://arxiv.org/abs/1804.06422
  2. "Hash Tables: Theory and Practice" (arXiv:2109.08012)
  3. "Practical Hash Table Designs for Sorting and Searching" (arXiv:2201.05696)
  4. "Hash Tables for Beginners" (arXiv:1805.07825)

These resources cover various aspects of hash tables, including theoretical foundations, practical implementations, and applications in parallel and distributed computing, as well as introductory materials for beginners.

Conclusion

In this slideshow, we explored the fundamentals of hash tables, their implementation in Python, and techniques for handling collisions, such as separate chaining, linear probing, quadratic probing, and double hashing. We also discussed the importance of load factor and resizing, performance analysis, and the applications of hash tables in machine learning, including feature hashing, caching, and associative data structures. Finally, we provided additional resources from ArXiv for further exploration of advanced topics related to hash tables.

More in Feature engineering and preprocessing

  1. Identifying and Handling Outliers in Machine Learning13 min

    Outliers are data points that significantly deviate from the normal pattern in a dataset. These anomalous observations can have a substantial impact on...

  2. Handling Imbalanced Data with Reweighting7 min

    Data imbalance occurs when class distributions are significantly skewed, commonly seen in fraud detection, medical diagnosis, and recommendation systems....

  3. Imbalanced Stratification Techniques for Machine Learning using Python6 min

    Imbalanced classification is a common problem in machine learning where one class significantly outnumbers the other(s). This can lead to biased models that...

  4. Handling Imbalanced Data in Machine Learning with Python8 min

    Imbalanced data occurs when one class significantly outnumbers the other(s) in a dataset. This common problem can lead to biased models that perform poorly...

  5. Importance of Data Quality in Machine Learning22 min

    Data quality assessment is a crucial first step in machine learning projects. We'll create a comprehensive data quality analyzer that checks for missing...

  6. Generative Data Augmentation and Bayesian Techniques in Machine Learning15 min

    Generative Data Augmentation is a technique that leverages generative models to create synthetic data for training machine learning models. This approach...