Handling Collisions

class HashMap:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]

    def _idx(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._idx(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:            # update existing
                bucket[i] = (key, value)
                return
        bucket.append((key, value)) # new collision → append

    def get(self, key):
        for k, v in self.buckets[self._idx(key)]:
            if k == key:
                return v
        return None

class HashMap<V> {
  private buckets: [string, V][][];

  constructor(size = 8) {
    this.buckets = Array.from({ length: size }, () => []);
  }

  private idx(key: string): number {
    let h = 7;
    for (const ch of key) h = (Math.imul(h, 31) + ch.charCodeAt(0)) | 0;
    return (h >>> 0) % this.buckets.length;
  }

  put(key: string, value: V): void {
    const bucket = this.buckets[this.idx(key)];
    const hit = bucket.find(([k]) => k === key);
    if (hit) hit[1] = value;          // update existing
    else bucket.push([key, value]);   // new collision → append
  }

  get(key: string): V | undefined {
    return this.buckets[this.idx(key)].find(([k]) => k === key)?.[1];
  }
}

import java.util.*;

class HashMapChained<V> {
    private final List<List<Map.Entry<String, V>>> buckets;

    HashMapChained(int size) {
        buckets = new ArrayList<>();
        for (int i = 0; i < size; i++) buckets.add(new ArrayList<>());
    }

    private int idx(String key) {
        return Math.floorMod(key.hashCode(), buckets.size());
    }

    void put(String key, V value) {
        var bucket = buckets.get(idx(key));
        for (var e : bucket) {
            if (e.getKey().equals(key)) { e.setValue(value); return; }
        }
        bucket.add(new AbstractMap.SimpleEntry<>(key, value));
    }

    V get(String key) {
        for (var e : buckets.get(idx(key))) {
            if (e.getKey().equals(key)) return e.getValue();
        }
        return null;
    }
}

#include <string.h>
#include <stdlib.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

#define SIZE 8
Node *buckets[SIZE];

static unsigned idx(const char *key) {
    unsigned h = 7;
    for (const char *p = key; *p; p++) h = h * 31u + (unsigned char)*p;
    return h % SIZE;
}

void put(const char *key, int value) {
    unsigned i = idx(key);
    for (Node *n = buckets[i]; n; n = n->next)
        if (strcmp(n->key, key) == 0) { n->value = value; return; }
    Node *n = malloc(sizeof(Node));      /* new collision → prepend */
    n->key = strdup(key); n->value = value; n->next = buckets[i];
    buckets[i] = n;
}

int get(const char *key, int *found) {
    for (Node *n = buckets[idx(key)]; n; n = n->next)
        if (strcmp(n->key, key) == 0) { *found = 1; return n->value; }
    *found = 0; return 0;
}

#include <string>
#include <vector>
#include <list>
#include <optional>

class HashMap {
    std::vector<std::list<std::pair<std::string, int>>> buckets;

    std::size_t idx(const std::string &key) const {
        unsigned h = 7;
        for (unsigned char ch : key) h = h * 31u + ch;
        return h % buckets.size();
    }

public:
    explicit HashMap(std::size_t size = 8) : buckets(size) {}

    void put(const std::string &key, int value) {
        auto &bucket = buckets[idx(key)];
        for (auto &e : bucket)
            if (e.first == key) { e.second = value; return; }
        bucket.emplace_back(key, value); // new collision → append
    }

    std::optional<int> get(const std::string &key) const {
        for (const auto &e : buckets[idx(key)])
            if (e.first == key) return e.second;
        return std::nullopt;
    }
};