Java HashMap简单实现原理的理解

正常情况下，Map的key和Value都可以用数组实现，一边ArrayList是key的keys，另一边是ArrayList value的values。

通过key获取value的方式是这样的values.get(keys.indexOf(key)).

然而，数组的长度是有限的。不符合map可以无限放入元素的要求。所以要对这个数组进行特殊的要求。

那就是同一个数组的index可以存放多个值，只是这些相同index的hascode值不同，这样就能把他们却别开了。同时也就实现无限个元素要求了（用数组实现主要是性能的优势）。那么要确定value就要计算hascode和数组下标。

数组不直接执行value的值，而是用equals()方法线性的查找；正常情况下这样的查找方式也会慢，但是只要hascode方法设计的合理，每个插槽将会只有少量的value.这样查找也就快很多；

import java.util.Map;    public class MapEntry<K,V> implements Map.Entry<K, V> {   private K key;   private V value;   public MapEntry(K key, V value) {    this.key = key;    this.value = value;   }   @Override   public K getKey() {    return key;   }   @Override   public V getValue() {    return value;   }   @Override   public V setValue(V value) {    V result = this.value;    this.value =value;    return result;   }   @Override   public int hashCode() {    return (key == null ? 0:key.hashCode())^(value == null ? 0: value.hashCode());   }   @Override   public boolean equals(Object obj) {    if(!(obj instanceof MapEntry)) {     return false;    }    MapEntry me = (MapEntry)obj;    return (key ==null ? me.getKey() == null : key.equals(me.getKey())) &&      (value == null ? me.getValue()==null : value.equals(me.getValue()));   }   @Override   public String toString() {    return key+"="+value;   }  }

import java.util.AbstractMap;  import java.util.HashSet;  import java.util.LinkedList;  import java.util.ListIterator;  import java.util.Map;  import java.util.Set;    public class SimpleHashMap<K,V> extends AbstractMap<K, V> {   static final int SIZE = 997;   /**集合类型数组,数组的每个元素都是一个List集合类型**/   LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];   public V put(K key, V value) {    V oldValueV = null;    /**根据hascode对数组长度求模，计算得出应该放入数组的index位置**/    int index = Math.abs(key.hashCode())%SIZE;    if(buckets[index] == null) {     /**如果该下标下还没有集合，则创建**/     buckets[index] = new LinkedList<MapEntry<K, V>>();    }    LinkedList<MapEntry<K, V>> bucket = buckets[index];    /**把传进来的key和value封装为MapEntry类型**/    MapEntry<K, V> pair = new MapEntry<K, V>(key, value);    /**假设在该数组index下的机会里找不到与pair对应的值**/    boolean found = false;    ListIterator<MapEntry<K, V>> it = bucket.listIterator();    while(it.hasNext()) {     MapEntry<K, V> iPair = it.next();     if(iPair.getKey().equals(key)) {      /**如果已经存在,则替换掉**/      oldValueV = iPair.getValue();      it.set(pair);      found = true;      break;     }    }    if(!found) {     /**如果不存在，则把封装后的MapEntry对象加入的集合中**/     buckets[index].add(pair);    }    return oldValueV;   }   public V ge(Object key) {    /**已同样的方式计算出应该的index**/    int index = Math.abs(key.hashCode())%SIZE;    if(buckets[index]==null) {     /**对应的index里没有机会**/     return null;    }    for(MapEntry<K, V> iPair : buckets[index]) {     if(iPair.getKey().equals(key)) {      /**对该index下的机会进行查找，比较MapEntr的key值**/      return iPair.getValue();     }    }    return null;   }   @Override   public Set<Map.Entry<K, V>> entrySet() {    Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K,V>>();    for(LinkedList<MapEntry<K, V>> bucket : buckets) {     if(bucket == null) continue;     for(MapEntry<K, V> mpair : bucket) {      /**用2个for循环，遍历这个二维的集合，把遍历到的每个值放到Set里**/      set.add(mpair);     }    }    return set;   }   public static void main(String[] args) {    SimpleHashMap<String, String> mMap = new SimpleHashMap<String,String>();    mMap.put("YYY", "yyy");    mMap.put("QQQ", "qqq");    mMap.put("AAA", "aaa");    mMap.put("GGG", "ggg");    System.out.println(mMap);    System.out.println(mMap.get("GGG"));    System.out.println(mMap.entrySet());   }  }

摘自thinking in java