class Node {
    Object key;
    Object value;
    Node next;

    // 構(gòu)造方法：初始化鍵值對(duì)，next默認(rèn)null
    public Node(Object key, Object value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

class LinkList {
    // 鏈表頭節(jié)點(diǎn)
    private Node head;

    // 添加/覆蓋鍵值對(duì)：存在相同key則覆蓋value，不存在則新增節(jié)點(diǎn)
    public void add(Object key, Object value) {
        // 頭節(jié)點(diǎn)為空，直接創(chuàng)建新節(jié)點(diǎn)作為頭節(jié)點(diǎn)
        if (head == null) {
            head = new Node(key, value);
            return;
        }

        // 遍歷鏈表，查找是否存在相同key
        Node current = head;
        while (current != null) {
            // key相等（處理null key），覆蓋value
            if (equals(key, current.key)) {
                current.value = value;
                return;
            }
            // 到鏈表尾部，退出循環(huán)
            if (current.next == null) {
                break;
            }
            current = current.next;
        }

        // 無(wú)相同key，在鏈表尾部新增節(jié)點(diǎn)
        current.next = new Node(key, value);
    }

    // 根據(jù)key獲取對(duì)應(yīng)value，無(wú)則返回null
    public Object get(Object key) {
        Node current = head;
        while (current != null) {
            // 匹配key（處理null key）
            if (equals(key, current.key)) {
                return current.value;
            }
            current = current.next;
        }
        // 未找到對(duì)應(yīng)key
        return null;
    }

    // 輔助方法：判斷兩個(gè)key是否相等（處理null值）
    private boolean equals(Object k1, Object k2) {
        if (k1 == null && k2 == null) {
            return true;
        }
        if (k1 == null || k2 == null) {
            return false;
        }
        return k1.equals(k2);
    }
}

public class MyHashMap {
    //定義保存鏈表的數(shù)組
    public LinkList[] linkLists;
    public static int len = 16;

    //自定義長(zhǎng)度
    public MyHashMap(int len) {
        linkLists = new LinkList[len];
        //初始化數(shù)組，每個(gè)位置都創(chuàng)建空鏈表
        for(int i=0;i<len;i++){
            linkLists[i] = new LinkList();
        }
    }

    //默認(rèn)長(zhǎng)度
    public MyHashMap() {
        this(len);
    }

    //put數(shù)據(jù)：存儲(chǔ)鍵值對(duì)，鍵重復(fù)則覆蓋值
    public void put(Object key, Object value) {
        //根據(jù)當(dāng)前key,利用哈希函數(shù)計(jì)算位置
        int index = hash(key);
        //取出對(duì)應(yīng)鏈表,保存鍵值對(duì)（處理重復(fù)鍵覆蓋）
        linkLists[index].add(key, value);
    }

    //get 取出數(shù)據(jù)：根據(jù)key獲取對(duì)應(yīng)value，無(wú)則返回null
    public Object get(Object key){
        int index = hash(key);
        return linkLists[index].get(key);
    }

    //哈希函數(shù)(散列函數(shù))：計(jì)算key在數(shù)組中的索引，處理負(fù)數(shù)哈希值
    public int hash(Object key) {
        if (key == null) {
            return 0; // null鍵固定放在索引0位置
        }
        int hashCode = key.hashCode();
        // 處理負(fù)數(shù)哈希值，保證索引非負(fù)
        return (hashCode & 0x7FFFFFFF) % linkLists.length;
    }

    public static void main(String[] args) {
        MyHashMap hm = new MyHashMap();
        hm.put("a",10);
        hm.put("a",20); // 重復(fù)key，覆蓋值
        hm.put("c",null);
        hm.put(null, 99); 

        System.out.println(hm.get("a"));  
        System.out.println(hm.get("c"));  
        System.out.println(hm.get(null)); 
        System.out.println(hm.get("d"));  
    }
}