Question

Solution

题目大意:构造一个hashmap

思路:讨个巧,只要求key是int,哈希函数选择f(x)=x,规定key最大为1000000,那构造一个1000000的数组

Java实现:

class MyHashMap {    int[] table;        /** Initialize your data structure here. */    public MyHashMap() {        table = new int[1000000];        Arrays.fill(table, -1);    }        /** value will always be non-negative. */    public void put(int key, int value) {        table[key] = value;    }        /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */    public int get(int key) {        return table[key];    }        /** Removes the mapping of the specified value key if this map contains a mapping for the key */    public void remove(int key) {        table[key] = -1;    }}/** * Your MyHashMap object will be instantiated and called as such: * MyHashMap obj = new MyHashMap(); * obj.put(key,value); * int param_2 = obj.get(key); * obj.remove(key); */

参考别人的

class MyHashMap {    final Bucket[] buckets = new Bucket[10000];    public void put(int key, int value) {        int i = idx(key);        if (buckets[i] == null)            buckets[i] = new Bucket();        ListNode prev = find(buckets[i], key);        if (prev.next == null)            prev.next = new ListNode(key, value);        else prev.next.val = value;    }    public int get(int key) {        int i = idx(key);        if (buckets[i] == null)            return -1;        ListNode node = find(buckets[i], key);        return node.next == null ? -1 : node.next.val;    }    public void remove(int key) {        int i = idx(key);        if (buckets[i] == null) return;        ListNode prev = find(buckets[i], key);        if (prev.next == null) return;        prev.next = prev.next.next;    }    int idx(int key) { return Integer.hashCode(key) % buckets.length;}    ListNode find(Bucket bucket, int key) {        ListNode node = bucket.head, prev = null;        while (node != null && node.key != key) {            prev = node;            node = node.next;        }        return prev;    }}class Bucket {    final ListNode head = new ListNode(-1, -1);}class ListNode {    int key, val;    ListNode next;    ListNode(int key, int val) {        this.key = key;        this.val = val;    }}