HashMap的实现

转载：http://www.cnblogs.com/xwdreamer/archive/2012/05/14/2499339.html

今天内部转岗面试，运气太差，不过说一千道一万，还是自己的功底不够。

对其中一道面试题解决如下，谨记之。

面试题：如何用数组实现HashMap？

　　在参考转载文章后，记录如下。

数组：容易定位，但插入/删除难

链表：容易插入/删除，但难于定位

介于二者之间：哈希表（有多种实现方法），比如用拉链法（可理解为链表的数组）实现。

最直接方法分析：

  map.put(key, value)  <==>  list.add(value) / array[index]

  二者差别：key和下标/index。所以，用数组实现HashMap，想方设法将key值转变成下标/index。

  key的hashCode出现，并使用常用的散列法：取模，即key.hashCode()%length.

但最关键问题出现：

　　length有限，但我插入的value个数大于length；或者两个key对应的下标一致，必然造成value的覆盖现象。

解决方案：

　　array下标对应另一个list，该list中元素属性包括：key，value，下一个元素。如下：

class Entity<K, V>{
    private K key;
    private V value;
    private Entity<K,V> entity;
}

当put时，一旦出现下标冲突，会遍历子list中的Entity，通过key之间的判断进行类似map中的操作(覆盖/添加)

当get时，类似put操作中的逻辑。

具体实现代码如下：

public class Entity<K,V> {
    private K key;
    private V value;
    private Entity<K,V> next;

    public Entity(V value, K key, Entity<K, V> next) {
        this.next = next;
        this.value = value;
        this.key = key;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Entity<K, V> getNext() {
        return next;
    }

    /**
     * 以下重写方法，只针对Entity类，而非key,或者value
     */
    @Override
    public int hashCode() {
        return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Entity)){
            return false;
        }
        Entity e = (Entity)o;
        K eKey = (K)e.getKey();
        V eValue = (V)e.getValue();
        boolean keyStatus = (eKey == key || eKey!=null && eKey.equals(key));
        boolean valueStatus = (eValue == value || eValue!=null && eValue.equals(value));
        return keyStatus && valueStatus;
    }
}

public class MyHashMap<K,V> {
    private final int DEFAULT_LENGTH = 16;
    private int size = DEFAULT_LENGTH;
    private Entity[] entities;

    public MyHashMap(int... size){
        if (size != null && size.length == 1){
           this.size = size[0];
        }
        entities = new Entity[this.size];
    }

    /**
     *
     * @return map size
     */
    public int getSize(){
        return size;
    }

    /**
     * 添加元素
     * @param key
     * @param value
     * @return is put or not
     */
    public boolean put(K key, V value){
        if (key == null){
            return false;
        }
        int index = key.hashCode()%size;
        Entity<K,V> entity = null;

        if (entities[index] == null){
            //key not exist
            entity = new Entity<K, V>(value,key,null);
        } else {
            //equals key, the value will be covered.
            Entity e = entities[index];
            while(e != null){
                Object eKey = e.getKey();
                if (eKey == key || eKey.equals(key)){
                    e.setValue(value);
                    return true;
                }
                e = e.getNext();
            }
            //key not exist
            entity = new Entity<K, V>(value,key,entities[index]);
        }
        entities[index] = entity;
        return true;
    }

    /**
     * 获取元素
     * @param key
     * @return V value
     */
    public V get(K key){
        if (key == null){
            return null;
        }
        int index = key.hashCode()%size;
        Entity e = null;
        try {
            e = entities[index];
        } catch(Exception ex){
            return null;
        }
        while(e != null){
            Object eKey = e.getKey();
            if (eKey == key || eKey.equals(key)){
                return (V)e.getValue();
            }
            e = e.getNext();
        }
        return null;
    }
}

测试代码：

public class Main {
    public static void main(String[] args) {
        MyHashMap<String,String> map = new MyHashMap<String, String>(20);
        map.put("Ch","29");
        map.put("is","30");
        map.put("hehe","129");
        map.put("tete","jf");
        System.out.println(map.get("Ch"));
        System.out.println(map.get("isensdd"));
        System.out.println(map.get("tete"));
        map.put("tete","sdfwejf");
        System.out.println(map.get("tete"));

    }
}

总结：巧妙之处在于数组中的元素Entity的构成（key, value, nextEntity）!