Hash Maps & Hash Sets

class HashMap:
    def __init__(self, capacity=16):
        self._capacity = capacity
        self._size = 0
        # Each bucket is a list of (key, value) pairs
        self._buckets = [[] for _ in range(capacity)]
        self._load_threshold = 0.75

    def _hash(self, key):
        # Use Python's built-in hash, then constrain to our array size
        return hash(key) % self._capacity

    def put(self, key, value):
        if self._size / self._capacity >= self._load_threshold:
            self._resize()

        idx = self._hash(key)
        bucket = self._buckets[idx]

        # Check if key already exists — update if so
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        # New key — append to chain
        bucket.append((key, value))
        self._size += 1

    def get(self, key, default=None):
        idx = self._hash(key)
        for k, v in self._buckets[idx]:
            if k == key:
                return v
        return default

    def delete(self, key):
        idx = self._hash(key)
        bucket = self._buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self._size -= 1
                return True
        return False

    def contains(self, key):
        """Check if key exists — O(1) average."""
        idx = self._hash(key)
        return any(k == key for k, v in self._buckets[idx])

    def keys(self):
        """Iterate all keys — O(n)."""
        for bucket in self._buckets:
            for k, v in bucket:
                yield k

    def _resize(self):
        # Double capacity and rehash everything
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]
        self._size = 0
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)


# Usage
m = HashMap()
m.put("name", "Alice")
m.put("age", 30)
print(m.get("name"))    # "Alice"
m.delete("age")
print(m.get("age"))     # None

class HashMap {
  constructor(capacity = 16) {
    this._capacity = capacity;
    this._size = 0;
    this._buckets = Array.from({ length: capacity }, () => []);
    this._loadThreshold = 0.75;
  }

  _hash(key) {
    // Simple string hash — multiply-and-add with prime 31
    let h = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      // The "| 0" forces 32-bit integer to prevent float overflow
      h = (h * 31 + str.charCodeAt(i)) | 0;
    }
    return Math.abs(h) % this._capacity;
  }

  put(key, value) {
    if (this._size / this._capacity >= this._loadThreshold) {
      this._resize();
    }
    const idx = this._hash(key);
    const bucket = this._buckets[idx];

    // Update existing key if found
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    bucket.push([key, value]);
    this._size++;
  }

  get(key) {
    const idx = this._hash(key);
    for (const [k, v] of this._buckets[idx]) {
      if (k === key) return v;
    }
    return undefined;
  }

  delete(key) {
    const idx = this._hash(key);
    const bucket = this._buckets[idx];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        this._size--;
        return true;
      }
    }
    return false;
  }

  _resize() {
    const oldBuckets = this._buckets;
    this._capacity *= 2;
    this._buckets = Array.from({ length: this._capacity }, () => []);
    this._size = 0;
    for (const bucket of oldBuckets) {
      for (const [k, v] of bucket) {
        this.put(k, v);
      }
    }
  }

  get size() { return this._size; }
}

class OpenAddressHashMap:
    """Hash map using open addressing with linear probing.
    
    Instead of chains, collisions are resolved by probing
    for the next empty slot in the array. Deletions use a
    sentinel value (DELETED) to avoid breaking probe chains.
    
    This is closer to how Python's built-in dict actually works
    (though Python uses a more sophisticated probing sequence).
    """
    EMPTY = object()    # Sentinel for never-used slots
    DELETED = object()  # Sentinel for deleted slots (tombstone)

    def __init__(self, capacity=16):
        self._capacity = capacity
        self._size = 0
        self._keys = [self.EMPTY] * capacity
        self._values = [None] * capacity

    def _hash(self, key):
        return hash(key) % self._capacity

    def put(self, key, value):
        if self._size >= self._capacity * 0.5:  # lower threshold for open addressing
            self._resize()

        idx = self._hash(key)
        while True:
            if self._keys[idx] is self.EMPTY or self._keys[idx] is self.DELETED:
                self._keys[idx] = key
                self._values[idx] = value
                self._size += 1
                return
            if self._keys[idx] == key:
                self._values[idx] = value  # update existing
                return
            idx = (idx + 1) % self._capacity  # linear probe

    def get(self, key, default=None):
        idx = self._hash(key)
        while self._keys[idx] is not self.EMPTY:
            if self._keys[idx] == key:
                return self._values[idx]
            idx = (idx + 1) % self._capacity
        return default

    def delete(self, key):
        idx = self._hash(key)
        while self._keys[idx] is not self.EMPTY:
            if self._keys[idx] == key:
                # Mark as deleted (tombstone) — don't use EMPTY
                # because that would break probe chains for other keys
                self._keys[idx] = self.DELETED
                self._values[idx] = None
                self._size -= 1
                return True
            idx = (idx + 1) % self._capacity
        return False

    def _resize(self):
        old_keys, old_values = self._keys, self._values
        self._capacity *= 2
        self._keys = [self.EMPTY] * self._capacity
        self._values = [None] * self._capacity
        self._size = 0
        for i, k in enumerate(old_keys):
            if k is not self.EMPTY and k is not self.DELETED:
                self.put(k, old_values[i])

from collections import Counter
import re

def analyze_text(text):
    """Analyze word frequency in text.
    
    Real-world uses:
    - Search engine indexing (TF-IDF scoring)
    - Spam detection (count suspicious words)
    - Plagiarism detection (compare frequency profiles)
    - Natural language processing (bag-of-words model)
    """
    # Normalize: lowercase, extract words only
    words = re.findall(r'[a-z]+', text.lower())

    # Counter is a dict subclass optimized for counting
    freq = Counter(words)

    # Most common words
    print("Top 5 words:")
    for word, count in freq.most_common(5):
        bar = "█" * count
        print(f"  {word:>12}: {bar} ({count})")

    # Unique word count
    print(f"\nTotal words: {len(words)}")
    print(f"Unique words: {len(freq)}")
    print(f"Vocabulary richness: {len(freq) / len(words):.2%}")

    return freq

# Example
sample = """
The quick brown fox jumps over the lazy dog.
The dog barked at the fox. The fox ran away.
The quick fox was too quick for the lazy dog.
"""
freq = analyze_text(sample)

# Check if two texts are similar (cosine similarity)
def text_similarity(freq1, freq2):
    """Compare two frequency maps using cosine similarity.
    
    Returns 0.0 (completely different) to 1.0 (identical).
    This is the basis for document similarity in search engines.
    """
    # Only consider words that appear in both texts
    common = set(freq1.keys()) & set(freq2.keys())
    if not common:
        return 0.0

    dot_product = sum(freq1[w] * freq2[w] for w in common)
    mag1 = sum(v**2 for v in freq1.values()) ** 0.5
    mag2 = sum(v**2 for v in freq2.values()) ** 0.5

    return dot_product / (mag1 * mag2)