HashMap源码理解
看看HashMap对应的源码。
1.类、接口关系public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
克隆和序列化不懂，先看Map。
2.实现的接口 Map
public interface Map<K,V> { //这些方法就不用写注释了吧，一看就懂。 int size(); boolean isEmpty(); boolean containsKey(Object key); boolean containsValue(Object value); V get(Object key); V put(K key, V value); V remove(Object key); void putAll(Map<? extends K, ? extends V> m); void clear(); //这里是返回的不重复的集合 Set<K> keySet(); //这里返回的是一个集合 Collection<V> values(); Set<Map.Entry<K, V>> entrySet(); boolean equals(Object o); int hashCode(); //还有一个内部的接口，这个相当于一个key-value数据。 interface Entry<K,V> { K getKey(); V getValue();V setValue(V value); boolean equals(Object o);int hashCode(); }}3.继承的抽象类AbstractMap这个方法有700行，我就挑出几个说一说
3.1构造方法public abstract class AbstractMap<K,V> implements Map<K,V> { protected AbstractMap() { }}3.2 几个方法简单介绍几个，都没什么实际意思。
//声明了抽象变量，里面直接是Map的内部类，这个Set包含着所有的数据key+valuepublic abstract Set<Entry<K,V>> entrySet();//Map长度public int size() { return entrySet().size();}//是否为空public boolean isEmpty() {return size() == 0;}//是否包含某个值public boolean containsValue(Object value) { //要查找出是否包含，于是开始遍历这个Set。 //这里可以使用 for each，但是这个方法写于jdk1.2，所以当时还没有。遍历的过程很简单。Iterator<Entry<K,V>> i = entrySet().iterator(); //这里还有一个判空。if (value==null) { while (i.hasNext()) {Entry<K,V> e = i.next();if (e.getValue()==null) return true; }} else { while (i.hasNext()) {Entry<K,V> e = i.next(); //注意：比较用的是equals，而不是==if (value.equals(e.getValue())) return true; }}return false;}//查找这个值，一样遍历Setpublic V get(Object key) {Iterator<Entry<K,V>> i = entrySet().iterator();if (key==null) { while (i.hasNext()) {Entry<K,V> e = i.next();if (e.getKey()==null) return e.getValue(); }} else { while (i.hasNext()) {Entry<K,V> e = i.next();if (key.equals(e.getKey())) return e.getValue(); }}return null;}//这个方法是要求重写的。public V put(K key, V value) {throw new UnsupportedOperationException();}//删除某个键值对public V remove(Object key) {Iterator<Entry<K,V>> i = entrySet().iterator();Entry<K,V> correctEntry = null; //key值可以为null，查出相应key值所对应的键值对。if (key==null) { while (correctEntry==null && i.hasNext()) {Entry<K,V> e = i.next();if (e.getKey()==null) correctEntry = e; }} else { while (correctEntry==null && i.hasNext()) {Entry<K,V> e = i.next();if (key.equals(e.getKey())) correctEntry = e; }} //这里开始删除操作V oldValue = null;if (correctEntry !=null) { oldValue = correctEntry.getValue(); //用迭代器的删除方法。 i.remove();} //返回删除的value。return oldValue;}//添加一个Map操作，直接循环添加public void putAll(Map<? extends K, ? extends V> m) { for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) put(e.getKey(), e.getValue());}//直接使用了set的clear方法public void clear() {entrySet().clear();}AbstractMap就看到这里，毕竟主要是看HashMap。
4.HashMap4.0文字介绍HashMap首先会开辟一个16空间的Entry（键值对）数组，
Entry类中包括
final K key;V value;Entry<K,V> next;final int hash;?
然后对存入的key进行hash运算，算到一个数字（1-15），存入对应位置。
如果对应位置一有数据，则替代当前数据，然后将原数据的引用给新数据，即赋值给next。当存到一定的值后，会扩展空间。
查询的时候将key进行计算得到（1-15），然后查询对应位置，一直去next，知道取到数据或结束。
4.1构造函数。public HashMap() { //一个倍数 0.75f this.loadFactor = DEFAULT_LOAD_FACTOR; //临界值 16*0.75=12，表示存了12个值以后要开辟新的空间 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); //初始空间16 table = new Entry[DEFAULT_INITIAL_CAPACITY]; //init里面没有内容。 init();}4.2 put方法public V put(K key, V value) { //如果key为空，单独做插入操作。 if (key == null) //插入key为null的值，返回之前此处的值。 return putForNullKey(value); //计算hash值，下面的两个方法 int hash = hash(key.hashCode()); //根据hash值获得在数组中的位置 int i = indexFor(hash, table.length); //循环位置。直到为空位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果包含key值和hash值都相等。 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //将原有的键值对的value值替换。 V oldValue = e.value; e.value = value; //这是替换要执行的方法，现在内部还没有处理。 e.recordAccess(this); //将就得value返回。 return oldValue; } } //这里代表这个key值要新加入这个map。 //修改次数 ?modCount++; //加入 addEntry(hash, key, value, i); return null;}//添加一个空的key。添加到数组的0位置。private V putForNullKey(V value) { //判断对应位置时候为空， for (Entry<K,V> e = table[0]; e != null; e = e.next) { //对应key值不为空 if (e.key == null) { //更新数据。 V oldValue = e.value; e.value = value; e.recordAccess(this); //返回被替换掉的值。 return oldValue; } } modCount++; //添加一个0位置的。 addEntry(0, null, value, 0); return null;}//添加一个键值对，传入对应hash值和数组位置。void addEntry(int hash, K key, V value, int bucketIndex) { //将这个位置的原有值取出来，Entry<K,V> e = table[bucketIndex]; //新建一个，传入hash值，还有它的下一个键值对。所以同一个位置，后面插入的数据会查询快一点点。 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //如果size大于临界值。 if (size++ >= threshold) //将原来空间扩大为两倍 resize(2 * table.length);}//开辟新空间void resize(int newCapacity) { Entry[] oldTable = table; //旧数组的长度 int oldCapacity = oldTable.length; //最大空间数。 if (oldCapacity == MAXIMUM_CAPACITY) { //边界值为int的最大值。 threshold = Integer.MAX_VALUE; //结束。 return; } //新建一个数组,大小为传入的数字。 Entry[] newTable = new Entry[newCapacity]; //转移新数组 transfer(newTable); //给table赋值。 table = newTable; //边界值更新。 threshold = (int)(newCapacity * loadFactor);}//将数据全部重新插入新数组，规则使用新得数组空间值计算。void transfer(Entry[] newTable) { //这里用的是旧数组。 Entry[] src = table; int newCapacity = newTable.length; //遍历旧的数组， for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; //为空的键值对不用另外做处理 if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; //根据hash值获取对应数组位置。 int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } }}4.3 get方法//获取key值对应信息。public V get(Object key) { //key为null时候 if (key == null) //直接从0号位置开始查。 return getForNullKey(); //计算key值对应hash。 int hash = hash(key.hashCode()); //使用indexFor计算出对应table的位置，然后开始遍历。直到找到或者结束。 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null;}//获取key值为null的value。private V getForNullKey() { //先查找0号位，然后依次找next，直到找到key为null的值或键值对为空，返回。 for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null;}4.4一些常用的方法4.4.1 public boolean containsKey(Object key)将key进行hash计算，然后找到键值对，然后返回结果
4.4.2 public boolean containsValue(Object value)遍历数组，知道找到value。很费性能。
4.4.3? public void clear()遍历数组，全部置为null。
4.4.4 public V remove(Object key)找出对应key，去掉，更新关联值。
4.4.5 public Set<K> keySet()将整个数组返回，这个Set是单独实现的一个类，里面重新实现了迭代器，size，包含，清除，将迭代的结果返回Map的key。其实就是返回了完整的Map内容。没有开辟任何多余空间，所以这个方法会很快。
4.4.6 public Collection<V> values()这个和上面的一样，直接返回的是Map的整体数据，将Collection实现了迭代器，size，包含，清除，将迭代的结果返回Map的value。
?
5.使用的hash算法int hash = hash(key.hashCode());int i = indexFor(hash, table.length);static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}static int indexFor(int h, int length) { return h & (length-1);}计算都是通过hashCode来计算，所以存入HashMap的对象最好不要将hashCode写成一个值。hashCode各个类都有自己的生成方法，似乎Object默认的是内存位置，但是刚刚观察Integer和String都覆写了的。
int占32位，无符号左移20位，空位补0，无符号右移20位。算了，这个二进制运算符要系统的看，先这样把。
6.结束看到这里都差不多了，主要是理解HashMap的结构和hash算法。
同时产生了两个疑问，先记下来。
疑问一：只实现抽象类AbstractMap不行么？为什么还要implements Map ，不重复吗？
疑问二：transient volatile 这样声明变量是为什么？
?