Java 自定义 HashMap 实现

Custom HashMap implementation

提问by t0mcat

This question was asked to me in an interview. I think the only way to get best solution is SOF. So the question was "How would you implement a custom HashMap in java(Assume there is no such data structure called HashMap)". The only answer I could think of was by implementing Associative Arrays (but then again, Java doesnt have associative arrays). Could you experts please pour in your thoughts on this question?

这个问题是在一次采访中被问到的。我认为获得最佳解决方案的唯一方法是 SOF。所以问题是“您将如何在 java 中实现自定义 HashMap（假设没有这样的数据结构称为 HashMap）”。我能想到的唯一答案是实现关联数组（但话说回来，Java 没有关联数组）。各位专家能不能谈谈您对这个问题的看法？

采纳答案by willcodejavaforfood

Short Answer:

简答：

It would be an array of arrays (or Lists).

它将是一个数组（或列表）数组。

Object[][] map;

where map[bucketIndex]would return the 'bucket'.

哪里map[bucketIndex]会返回“桶”。

When inserting something you need a function to calculate bucketIndexthis would use the hashcodeof the inserted object.

当插入一些东西时，你需要一个函数来计算bucketIndex这将使用hashcode插入对象的 。

Boom done!

繁荣完成！

:)

:)

回答by Mike Axiak

Look at Cliff Click's nonblockinghahmapfor an example of a need for a hashmap implemented in java. Remember that an associated array is just another name for a hash map, so he's asking you how to implement it.

查看 Cliff Click 的nonblockinghahmap以了解需要在 java 中实现的 hashmap 的示例。请记住，关联数组只是哈希映射的另一个名称，因此他问您如何实现它。

Generally hashes are implemented using standard arrays (not lists or anything fancy for speed). The issue is what is inside each of these arrays... in the case of a hash collision do you want to use a LinkedList (chaining) or do you want to rehash and go to another array location (open addressing). Read some more computer science to learn the cost/benefit to doing both.

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

回答by java_mouse

You should use one dimensional array. Object[] arr.

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

The index of the array is the normalized hashcode from the Key object. The array holds the Pair.

数组的索引是来自 Key 对象的规范化哈希码。数组保存对。

The reason the value consists of both Key and Value is that if there is any hash collision , it has to go thru the list of keys inside the slot and find out which is the correct key (using equals on the key object).

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

回答by user2489036

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];

    }        

}

回答by bhargavi damodaran

References: - 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

参考资料： - 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());
    }


}

回答by Ashish Shetkar

adding just one more approach - how about if we use set instead of hashMap in this way

添加另一种方法 - 如果我们以这种方式使用 set 而不是 hashMap 怎么样

Create a custom class called pair -

创建一个名为 pair 的自定义类 -

public class Pair  {

    private String key;
    private Object Value;

    public Pair(String key, Object value) {
        this.key = key;
        Value = value;
    }

    public String getKey() {
        return key;
    }

    public Object getValue() {
        return Value;
    }


    @Override
    public int hashCode() {
        return key.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Pair other = (Pair) obj;
        if (key != other.getKey())
            return false;
        return true;
    }
}

and then you can directly use java Set as Hashmap

然后就可以直接使用java Set as Hashmap

 public static void main(String[] args) {

        Set<Pair> set = new HashSet<Pair>();

        set.add(new Pair("key1", "val1"));
        set.add(new Pair("key2", "val2"));
        set.add(new Pair("key1", "val3"));

        // you can advanced for loop for looping over set
        for (Pair pair : set) {

        }

        // with java 8 - you can also use streams over it

       // set.stream().filter
       // set.stream().anyMatch
        // and some more methods can be directly used


    }

With Java-8 Stream API - it will enable this to make some more operations easy and fast.

使用 Java-8 Stream API - 它将使更多操作变得简单快捷。

Just adding this as one more possible approach for custom hashmap -

只需将其添加为自定义哈希图的另一种可能方法 -

回答by Saurabh Verma

Whenever there is no value present at a particular index, we will directly place the Entry object at that index. Else, we will traverse the LinkedList until we reach the last entry of the list and place the new entry object as the next node of the last entry object. In the process, if we find the key already exists then we simply replace its value with the new one.

每当特定索引处没有值时，我们将直接将 Entry 对象放置在该索引处。否则，我们将遍历 LinkedList 直到到达列表的最后一个条目，并将新条目对象放置为最后一个条目对象的下一个节点。在这个过程中，如果我们发现键已经存在，那么我们只需用新的值替换它的值。

public void put(K key, V value){
        int index = index(key);
        Entry newEntry = new Entry(key, value, null);
        if(table[index] == null){
            table[index] = newEntry;
        }else {
            Entry previousNode = null;
            Entry currentNode = table[index];
            while(currentNode != null){
                if(currentNode.getKey().equals(key)){
                    currentNode.setValue(value);
                    break;
                }
                previousNode = currentNode;
                currentNode = currentNode.getNext();
            }
            if(previousNode != null)
                previousNode.setNext(newEntry);
            }
    }