# Hash Tables

## Runtime analysis

1. Insert: $$O(1)$$
2. Search: $$O(1)$$
3. Delete: $$O(1)$$
4. Update: $$O(1)$$

## Take note…

1. Do we need a custom hashing function?

## Techniques

### Anagram hashing

This technique is particularly when trying to detect all anagrams and store them in buckets of same anagrams

* Multiplicative hash with prime numbers (3 onwards)
* Assign each character a prime number and calculate the hash
* Hash will be unique per anagram
* Does not scale well if more than 52 characters possible or $$n > 5000$$

```python
primes = [3, 5, 7, ...]
def hash(string):
	value = 1
	for ch in string:
		value *= primes[ord(ch) - ord('a')]
	return value
```

### Fingerprint hash tables/arrays over hash tables

I would recommend using these over hash tables where possible as they can represent the same information while reducing the complexity of the code

```python
freq = [0] * 26
# is the same as 
freq = {}
for ch in s:
    if ch not in freq:
        freq[ch] = 0
```

### Duplicate checking using bitmasks

This is a slight optimization over using hash tables/sets if the only thing that needs to be done is duplicate detection

* Not feasible if the numbers can be very large as size grows by powers of 2

```python
acc = 0
for ch in string:
	mask = 1 << (ord(ch) - ord('a'))
	if acc ^ mask < acc: # duplicate found
		return False
	acc |= mask
```

### Multiplicative hashing

$$
h(k) = \lfloor m(\phi \times k - \lfloor \phi \times k \rfloor) \rfloor
$$

* Where $$k$$ is the key to hash, $$\phi$$ is the golden ratio = $$\sqrt{5} - \frac{1}{2}$$

### Pairing with another data structure

Often used to improve performance at the cost of using more space to store the hash table

* Use [Linked Lists](/data-structures/linked-lists.md) to optimize to quickly delete/insert nodes in a certain order
  * Hash table has pointers to the nodes of the linked list

## Types of hashing

1. Chaining (linked list per bucket)
2. Open addressing (probing for a blank spot if current bucket is filled)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://interviews.woojiahao.com/data-structures/hash-tables.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.