java自定义HashMap实现

Question

这个问题是在一次采访中问我的。我认为获得最佳解决方案的唯一方法是SOF。所以问题是“如何在java中实现自定义HashMap（假设没有名为HashMap的数据结构）”。我能想到的唯一答案是实现关联数组（不过，Java没有关联数组）。 请专家们就这个问题倾诉一下你的想法好吗

Answer 1

你应该使用一维数组。对象[]arr

数组的索引是键对象的标准化哈希代码。阵列容纳这对

值由Key和value组成的原因是，如果存在任何哈希冲突，它必须遍历插槽中的键列表，找出哪个键是正确的键（在Key对象上使用equals）

Answer 2

public class ArrayAsHashMap {

    Object [][] hashArr  = new Object [10] [2];

    public void put(HashObject key, String value){
        int index = key.hashCode();
        Object [] arr = {key, value};
        hashArr[index] = arr;
    }

    public String get(HashObject key){
        int index = key.hashCode();
        Object [] arr = hashArr[index];
        return (String)arr[1];

    }        

}

Answer 3

请看Cliff Click的nonblockinghahmap，以获取一个需要用java实现的hashmap的示例。 记住，关联数组只是哈希映射的另一个名称，所以他在问你如何实现它

通常，哈希是使用标准数组实现的（而不是列表或任何追求速度的东西）。问题是每个阵列中都有什么。。。在哈希冲突的情况下，是要使用LinkedList（链接），还是要重新哈希并转到另一个数组位置（开放寻址）。阅读更多的计算机科学，了解两者的成本/收益

Answer 4

参考资料： -http://javarevisited.blogspot.sg/2011/10/override-hashcode-in-java-example.html -http://javarevisited.blogspot.in/2011/02/how-to-write-equals-method-in-java.html

class Entry<K, V> {
    K key;
    V val;

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getVal() {
        return val;
    }

    public void setVal(V val) {
        this.val = val;
    }

    @Override
    public int hashCode() {
        int prime = 13;
        int mul = 11;
        if (key != null) {
            int hashCode = prime * mul + key.hashCode();
            return hashCode;
        }
        return 0;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || this.getClass().getName() != o.getClass().getName()) {
            return false;
        }
        Entry e = (Entry) o;
        if (this.key == e.key) {
            return true;
        }
        return false;
    }
}

public class HashMapImpl<K, V> {
    private float loadfactor = 0.75f;
    private int capacity = 100;
    private int size = 0;
    private Entry<K, V> table[] = new Entry[capacity];

    private int Hashing(int hashCode) {
        int location = hashCode % capacity;
        System.out.println("Location:"+location);
        return location;
    }

    public int size() {
        // TODO Auto-generated method stub
        return this.size;
    }

    public boolean isEmpty() {
        if(this.size == 0) {
            return true;
        }
        return false;
    }

    public boolean containsKey(Object key) {
        if(key == null) {
            if(table[0].getKey() == null) {
                return true;
            }
        }
        int location = Hashing(key.hashCode());
        Entry e = null;
        try {
            e = table[location];
        }catch(NullPointerException ex) {

        }
        if(e!= null && e.getKey() == key) {
            return true;
        }
        return false;
    }

    public boolean containsValue(Object value) {
        for(int i=0; i<table.length;i++) {
            if(table[i] != null && table[i].getVal() == value) {
                return true;
            }
        }
        return false;
    }

    public V get(K key) {
        V ret = null;
        if(key == null) {
            Entry<K, V> e = null;
            try{
                e = table[0];
            }catch(NullPointerException ex) {

            }
            if(e != null) {
                return (V) e.getVal();
            }
        } else {
            int location = Hashing(key.hashCode());
            Entry<K, V> e = null;
            try{
            e = table[location];
            }catch(NullPointerException ex) {

            }
            if(e!= null && e.getKey() == key) {
                return (V)e.getVal();
            }
        }
        return ret;
    }

    public V put(K key, V val) {
        V ret = null;
        if (key == null) {
            ret = putForNullKey(val);
            return ret;
        } else {
            int location = Hashing(key.hashCode());
            if(location >= capacity) {
                System.out.println("Rehashing required");
                return null;
            }
            Entry<K, V> e = null;
            try{
            e = table[location];
            }catch(NullPointerException ex) {

            }
            if (e!= null && e.getKey() == key) {
                ret = (V) e.getVal();
            } else {
                Entry<K, V> eNew = new Entry<K,V>();
                eNew.setKey(key);
                eNew.setVal(val);
                table[location] = eNew;
                size++;
            }
        }
        return ret;
    }

    private V putForNullKey(V val) {
        Entry<K, V> e = null;
        try {
            e = table[0];
        }catch(NullPointerException ex) {

        }
        V ret = null;
        if (e != null && e.getKey() == null) {
            ret = (V) e.getVal();
            e.setVal(val);
            return ret;
        } else {
            Entry<K, V> eNew = new Entry<K,V>();
            eNew.setKey(null);
            eNew.setVal(val);
            table[0] = eNew;
            size++;
        }
        return ret;
    }

    public V remove(K key) {
        int location = Hashing(key.hashCode());
        V ret = null;
        if(table[location].getKey() == key) {
            for(int i=location; i<table.length;i++) {
                table[i] = table[i+1];
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        HashMapImpl<Integer, String> hashMap = new HashMapImpl<Integer, String>();
        hashMap.put(10, "Apple");
        hashMap.put(1, "Orange");
        hashMap.put(79, "Grape");
        System.out.println("Val at 79 "+hashMap.get(79));
        System.out.println("Val at 1 "+hashMap.get(1));
        System.out.println("Val at 10 "+hashMap.get(10));
        System.out.println("Val at 2 "+hashMap.get(2));
        hashMap.put(null, "Pear");
        System.out.println("Val at null "+hashMap.get(null));
        System.out.println("Hashmap has key at null:"+hashMap.containsKey(null));
        System.out.println("Hashmap has value at null:"+hashMap.containsValue("Pear"));
        System.out.println("Size of Map:"+hashMap.size());
    }


}