Arrays and Hashing in Python

Mastering fundamental data structures is crucial to excelling in Programming.

Arrays & hashing are foundational concepts -> every developer should understand deeply.

As an expert in Python, I've worked extensively with these structures, solving real-world problems and optimising code performance.

This article dives into the nuances of arrays and hashing in Python, providing clear examples and practical applications.

Arrays in Python

Arrays store elements in contiguous memory locations.

In Python, while we commonly use lists as dynamic arrays, other specialised array types serve specific purposes.

Lists (Dynamic Arrays)

Python lists are flexible and can store elements of different types. Their dynamic nature allows for resizing, which is highly beneficial for many applications.
 

Creating a list

arr_vals = [8, 3, 1, 6, 4]

Access arr_vals elements
 

print(arr_vals[0])  # Output: 8

Modify arr_vals elements

arr_vals[1] = 33
print(arr_vals)  # Output: [8, 33, 1, 6, 4]

Add element to arr_vals

arr_vals.append(22)
print(arr_vals)  # Output: [8, 33, 1, 6, 4, 22]

Remove arr_vals elements

arr_vals.pop()   # Removes the last element
print(arr_vals)  # Output: [8, 33, 1, 6, 4]

Slicing

print(arr[1:4])  # Output: [20, 3, 4]

Array Module

For type-constrained arrays, Python offers the array module, which is useful for numerical data.

import array

# Create an array of integers
arr = array.array('i', [1, 2, 3, 4, 5])

# Adding elements
arr.append(6)

# Removing elements
arr.remove(4)

print(arr)  # Output: array('i', [1, 2, 3, 5, 6])

Numpy Arrays

Numpy provides powerful array-handling capabilities, especially for numerical operations.
 

import numpy as np

# Create a numpy array
arr = np.array([8, 3, 1, 6, 4])

# Vectorized operations
arr = arr * 2
print(arr)

Hashing in Python

Hashing uniquely identifies data using a hash function. It forms the backbone of efficient data retrieval in structures like dictionaries and sets.

Hash Tables (Dictionaries)

Python's dict (implementation of a hash table) offers quick access to values using keys.

# Creating a dictionary
hash_table = {
    'Beet root': 9,
    'Mango': 13,
    'Quava': 21
}

# Accessing elements
print(hash_table['Beet root'])  # Output: 9

# Adding elements
hash_table['Lemon'] = 6

# Removing elements
del hash_table['Mango']

print(hash_table)  # Output: {'beet root': 9, 'Quava': 21, 'Lemon': 6}

Hash Function Example

A hash function maps keys to indices in a hash table.

def simple_hash(key, size):
    return sum(ord(char) for char in key) % size

# Example usage
key = "apple"
hash_table_size = 10
index = simple_hash(key, hash_table_size)
print(index)  # Output: 0 (depends on the hash function and key)

Handling Collisions

Collisions occur when multiple keys hash to the same index.

Solutions to collisions include:~

1) chaining and
2) open addressing.

Chaining Example

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]
    
    def hash_function(self, key):
        return sum(ord(char) for char in key) % self.size
    
    def insert(self, key, value):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])
    
    def get(self, key):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None

# Usage
ht = HashTable()
ht.insert("mango", 10)
ht.insert("quava", 20)

print(ht.get("mango"))  # Output: 10
print(ht.get("quava"))  # Output: 20

Practical Applications

Two Sum Problem

This problem involves finding two values in a given array that add up to a target value.

def two_sum(nums, target):
    hash_table = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_table:
            return [hash_table[complement], i]
        hash_table[num] = i

# Usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

Anagrams Grouping

Group words that are anagrams by sorting their characters.

def group_anagrams(words):
    hash_table = {}
    for word in words:
        sorted_word = ''.join(sorted(word))
        if sorted_word not in hash_table:
            hash_table[sorted_word] = []
        hash_table[sorted_word].append(word)
    return list(hash_table.values())

# Usage
words = ["bat", "tab", "cat", "act", "dog"]
print(group_anagrams(words))  # Output: [['bat', 'tab'], ['cat', 'act'], ['dog']]

What's Next in Your Learning Journey?

Understanding arrays and hashing equips you with essential tools for problem-solving in Python & programming in general.

Continue to explore more complex data structures and algorithms to deepen your knowledge.

Put these concepts in real-world projects to solidify your expertise.

Ready to tackle more? Dive into sorting algorithms or tree data structures next to broaden your skill set.